实现动态多时间线queu

Question

简介

我想实现一个动态多时间线队列。这里的上下文通常是调度。在

什么是时间线队列？在

这仍然很简单：它是一个任务时间表，其中每个事件都有其开始和结束时间。任务按作业分组。这组任务需要保持其顺序，但可以作为一个整体及时移动。例如，它可以表示为：

 --t1--   ---t2.1-----------t2.2-------
 '    '   '        '                  '
20    30  40       70                120 

我将使用一些附加约束将其实现为heap queue。Python^{}模块在这方面有一些基本的方法。在

定义多时间线队列

一个队列代表一个资源，一个任务需要一个资源。图形示例：

^{pr2}$

解释“动态”

当一个任务可以使用多个资源中的一个时，它就变得有趣了。另一个限制是，可以在同一资源上运行的连续任务必须使用相同的资源。在

示例：如果任务t1.3可以在R1或{}上运行，那么队列应该如下所示：

R1  --t1.1----- --t2.2-----      
            /  \                
R2  --t2.1--     ------t1.2----------t1.3--    

功能（按优先顺序）

• FirstFreeSlot（duration，start）：从start开始查找第一个空闲时隙，其中duration有空闲时间（见末尾的详细说明）。在
• 通过考虑约束条件（主要是：任务的正确顺序、同一资源上的连续任务）和使用FirstFreeSlot，尽可能早地在多个资源上排队。在
• 将一个作业放在特定的时间，并将尾部向后移动
• 删除工作
• 重新计算：删除后，测试是否可以提前执行某些任务。在

关键问题

问题是：我如何表示这些信息来有效地提供功能？执行由我决定；-）

更新：另一个需要考虑的问题：典型的区间结构关注的是“X点是什么？”但在本例中，enqueue和问题“duration D的第一个空槽在哪里？”更重要的是。因此，在这个方向上使用段/间隔树或其他东西可能不是正确的选择。在

进一步用空闲时隙来阐述这一点：由于我们有多个资源以及分组任务的限制，在某些资源上可能存在空闲时隙。简单的例子：t1.1在R1上运行40次，然后在R2上运行t1.2。因此在R2上有一个空的间隔[0, 40]，可以由下一个作业来填充。在

---

更新2：有一个interesting proposal in another SO question。如果有人能把它移植到我的问题上，并证明它在这个案例中起作用（特别是对多个资源进行了详细阐述），这可能是一个有效的答案。在

Answer 1

class Task:
    name=''
    duration=0
    resources=list()

class Job:
    name=''
    tasks=list()

class Assignment:
    task=None
    resource=None
    time=None

class MultipleTimeline:
    assignments=list()
    def enqueue(self,job):
        pass
    def put(self,job):
        pass
    def delete(self,job):
        pass
    def recalculate(self):
        pass

这是朝着您所寻找的方向迈出的第一步，即用Python编写的数据模型吗？在

更新：

因此，我的更高效模型：

它基本上把所有任务放在一个按结束时间排序的链表中。在

^{pr2}$

由于enqueue和put的更新，我决定不使用树。 因为put它可以在时间上移动任务，所以我决定不使用绝对时间。在

FirstFreeSlot不仅返回具有空闲时隙的任务，还返回其他正在运行的任务及其结束时间。在

enqueue的工作原理如下： 我们通过FirstFreeSlot来寻找空闲时间，并在此处安排任务。 如果有足够的空间来完成下一个任务，我们也可以把它安排进去。 如果没有：看看其他正在运行的任务是否有空闲空间。 如果没有：运行FirstFreeSlot，参数为这个时间和正在运行的任务。在

改进： 如果put不是经常使用，并且enqueue是从时间零点开始的，我们可以通过在每个包含其他正在运行的任务的任务中包含dict（）来跟踪重叠的任务。然后，还可以很容易地为每个资源保留一个list（），其中包含按endtime排序的该资源的绝对时间的计划任务。只包括那些时间间隔比以前大的任务。现在我们可以更容易地找到一个空位。在

问题： 此时是否需要执行put计划的任务？ 如果是：如果要按put计划的另一个任务重叠，该怎么办？ 所有资源执行任务的速度都一样快吗？在

Answer 2

经过一段时间的思考。我认为段树可能更适合对这个时间轴队列建模。工作概念就像一个列表数据结构。在

我假设任务可以这样建模（伪代码）。作业中的任务顺序可以由开始时间确定。在

class Task:
    name=''

    _seg_starttime=-1; 
    #this is the earliest time the Task can start in the segment tree, 
    #a lot cases this can be set to -1, which indicates its start after its predecessor,
    #this is determined by its predecessor in the segment tree.
    #if this is not equal -1, then means this task is specified to start at that time
    #whenever the predecessor changed this info need to be taken care of

    _job_starttime=0; 
    #this is the earliest time the Task can start in the job sequence, constrained by job definition

    _duration=0;      
    #this is the time the Task cost to run

    def get_segstarttime():
       if _seg_starttime == -1 :
           return PREDESSOR_NODE.get_segstarttime() + _duration
       return __seg_startime + _duration

    def get_jobstarttime():
       return PREVIOUS_JOB.get_endtime()

    def get_starttime():
       return max( get_segstarttime(), get_jobstarttime() )

• 排队这仅仅是将一个任务节点追加到段树中，请注意将_seg_startime设置为-1，以指示它将在其前一个任务节点之后立即启动
• 放入在树中插入一个段，该段由开始时间和持续时间表示。在
• 删除删除树中的段，必要时更新其后续节点（假设删除的节点确实存在一个_seg_start_time）
• 重新计算再次调用get_starttime（）将直接获得其最早的开始时间。在

示例（不考虑工作限制）

^{pr2}$

如果我们做一个看跌期权：

                    t1.1( _segst = 10, du = 10 )
                        \
                        t2.2( _segst = -1, du = 10 ) meaning the st=20+10=30
                        /  \
t2.3(_segst = 20, du = 10)  t1.3 (_segst = -1, du = 10 ) meaning the st = 30+10 = 30

如果我们删除t1.1到原始场景

                      t2.2( _segst = 20, du = 10 ) 
                        \
                        t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30

每个资源可以用这个间隔树的一个实例来表示 鸡蛋。在

从段树（时间轴）的角度来看：

t1.1                      t3.1
  \                        / \
  t2.2                  t2.1  t1.2

从工作角度来看：

t1.1 <- t1.2
t2.1 <- t2.2
t3.1

t2.1和t2.2是用链表连接起来的，如前所述：t2.2从段树中获取它的_sg_start_时间，从链表中获取它的_job_start_时间，比较这两个时间，就可以得出它可以运行的实际最早时间。在

Answer 3

让我们先把自己限制在最简单的情况下：找到一个合适的数据结构，它允许快速实现FirstFreeSlot（）。在

自由时隙存在于二维空间中：一个维度是开始时间s，另一个维度是长度d。FirstFreeSlot（d）有效地回答了以下查询：

最小s:d>；=d

如果我们把s和d看作笛卡尔空间（d=x，s=y），这意味着要找到一条垂直线包围的子平面上的最低点。一个quad-tree，可能在每个节点中有一些辅助信息（即，所有叶的最小值），将有助于有效地回答这个查询。在

对于Enqueue（）在资源限制的情况下，考虑为每个资源维护一个单独的四叉树。四叉树还可以回答以下查询

最小s:s>；=s&d>；=d

（限制起始数据所必需的）以类似的方式：现在一个矩形（在左上角打开）被切掉，我们在该矩形中寻找min s。在

Put（）和Delete（）是四叉树的简单更新操作。在

重新计算（）可以通过Delete（）+Put（）实现。为了节省不必要操作的时间，定义触发重新计算的足够（或者，理想情况下，足够+必要）条件。Observer模式在这里可能有帮助，但请记住，将重新调度的任务放入FIFO队列或按开始时间排序的优先级队列中。（您希望在接管下一个任务之前完成对当前任务的重新安排。）

更一般地说，我相信您已经意识到大多数类型的调度问题，特别是那些有资源限制的问题，至少是NP完全的。所以在一般情况下，不要期望一个运行时良好的算法。在