17

介绍

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

什么是时间线队列？

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

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

我会将其实现为带有一些额外约束的堆队列。Pythonsched模块在这个方向上有一些基本的方法。

定义多时间线队列

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

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


解释“动态”

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

示例：如果（从上面）任务t1.3可以在R1or上运行R2，则队列应如下所示：

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


功能（按优先顺序）

  • FirstFreeSlot(duration, start)start ：从有空闲时间的地方开始查找第一个空闲时隙duration（详细说明见文末）。
  • 通过考虑约束（主要是：任务的正确顺序、同一资源上的连续任务）和使用FirstFreeSlot.
  • 在特定时间放置工作并向后移动尾巴
  • 删除作业
  • 重新计算：删除后，测试是否可以更早地执行某些任务。


关键问题

关键是：我如何表示这些信息以有效地提供功能？实施取决于我;-)

更新：要考虑的另一点：典型的区间结构关注“X点是什么？” 但在这种情况下enqueue，因此问题是“持续时间 D 的第一个空槽在哪里？” 重要得多。所以这个方向的段/区间树或其他东西可能不是正确的选择。

进一步用空闲时隙详细说明这一点：由于我们有多个资源和分组任务的限制，某些资源上可以有空闲时隙。简单示例：t1.1在 R1 上运行 40，然后t1.2在 R2 上运行。所以[0, 40]R2 上有一个空白区间，可以由下一个作业填充。

更新 2 ：在另一个 SO question 中有一个有趣的建议。如果有人可以将它移植到我的问题并表明它适用于这种情况（特别是针对多种资源进行详细说明），那么这可能是一个有效的答案。

4

4 回答 4

2 
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 编写的数据模型吗？

更新：

特此我更有效的模型：

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

class Task:
    name=''
    duration=0    # the amount of work to be done
    resources=0   # bitmap that tells what resources this task uses
# the following variables are only used when the task is scheduled
    next=None     # the next scheduled task by endtime
    resource=None # the resource this task is scheduled
    gap=None      # the amount of time before the next scheduled task starts on this resource

class Job:
    id=0
    tasks=list() # the Task instances of this job in order 

class Resource:
    bitflag=0       # a bit flag which operates bitwisely with Task.resources
    firsttask=None  # the first Task instance that is scheduled on this resource
    gap=None        # the amount of time before the first Task starts

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

由于更新enqueue，put我决定不使用树。由于put这会及时移动任务，我决定不使用绝对时间。

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

enqueue工作原理如下：我们FirstFreeSlot在这里寻找空闲槽并安排任务。如果下一个任务有足够的空间，我们也可以安排它。如果没有：查看正在运行的其他任务是否有可用空间。如果不是：FirstFreeSlot使用本次参数运行并运行任务。

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

问题：调度的任务put需要在那个时候执行吗？如果是：如果 put 安排的另一个任务重叠怎么办？是否所有资源都以同样快的速度执行任务？

于 2012-06-25T17:36:56.843 回答
2

让我们首先将自己限制在最简单的情况下：找到一个允许快速实现FirstFreeSlot()的合适数据结构。

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

最小秒：d >= D

如果我们将 s 和 d 视为笛卡尔空间 (d=x, s=y)，这意味着找到以垂直线为界的子平面中的最低点。四叉树，可能在每个节点中都有一些辅助信息（即所有叶子上的 min s），将有助于有效地回答这个查询。

对于Enqueue()面对资源限制，考虑为每个资源维护一个单独的四叉树。四叉树还可以回答如下查询

最小 s: s >= S & d >= D

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

Put()和Delete()是四叉树的简单更新操作。

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

更笼统地说，我相信您知道大多数类型的调度问题，尤其是那些有资源限制的调度问题，至少是 NP 完全的。因此，在一般情况下，不要指望具有良好运行时间的算法。

于 2012-06-29T01:17:18.580 回答
1

在花一些时间思考这个问题之后。我认为分段树可能更适合于对这个时间线队列进行建模。作业概念就像一个 LIST 数据结构。

我假设任务可以像这样建模（伪代码）。作业中任务的顺序可以通过 start_time 来保证。

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 表示它在它的前任之后立即启动
  • 向树中插入一个段，该段由 start_time 和 duration 指示。
  • 删除 删除树中的段，必要时更新其后继节点（例如，如果删除的节点确实存在 _seg_start_time ）
  • 重新计算再次调用 get_starttime() 将直接得到它的最早开始时间。

示例（不考虑工作限制）

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

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

                    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

每个资源都可以使用这个间隔树蛋的 1 个实例来表示。

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

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_time，从链表中获取它的_job_start_time，比较这两个时间，那么它可以运行的实际最早时间可以是衍生的。

于 2012-06-27T04:38:49.203 回答
0

最后，我只为队列项使用了一个简单的列表，并使用内存中的 SQLite 数据库来存储空槽，因为使用 SQL 进行多维查询和更新非常有效。我只需要将字段start、duration和index存储在表中。

于 2012-11-09T07:03:09.287 回答