实现动态多时间轴队列

Question

介绍

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

什么是时间表队列？

这仍然很简单:它是任务的时间轴,每个事件都有其开始和结束时间.任务被分组为作业.这组任务需要保持其顺序,但可以在整体上及时移动.例如,它可以表示为:

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

我会将其实现为具有一些额外约束的堆队列.Python sched模块在这方面有一些基本的方法.

定义多个时间轴队列

一个队列代表资源,任务需要资源.图形示例:

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

解释" 动态 "

当任务可以使用多个资源中的一个时,它变得有趣.另一个约束是可以在同一资源上运行的连续任务必须使用相同的资源.

示例:如果(从上面)任务t1.3可以运行R1或R2,队列应如下所示:

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

功能(优先顺序)

• FirstFreeSlot(持续时间,开始):找到第一个空闲时隙从开始start哪里有空闲时间duration(见末详细的说明).
• 通过考虑约束(主要是:任务的正确顺序,同一资源上的连续任务)和使用,尽可能在多个资源上尽可能地排队作业FirstFreeSlot.
• 把工作在特定的时间和向后移动的尾巴
• 删除一份工作
• 重新计算:删除后,测试是否可以提前执行某些任务.

关键问题

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

更新:需要考虑的另一点:典型的区间结构侧重于"X点是什么？" 但在这种情况下enqueue,因此问题是"持续时间D的第一个空槽在哪里？" 更重要的是.因此,段/间隔树或此方向上的其他内容可能不是正确的选择.

进一步详细说明空闲时隙:由于我们有多个资源和分组任务的约束,因此某些资源上可以有空闲时隙.简单示例:t1.1在R1上运行40,然后t1.2在R2上运行.因此[0, 40],R2上有一个空的间隔,可以由下一个作业填充.

---

更新2:在另一个SO问题中有一个有趣的提议.如果有人可以将它移植到我的问题并显示它适用于这种情况(特别是详细说明了多个资源),这可能是一个有效的答案.

Answer 1

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