有效地减少时间约束任务之间的等待时间

Efficiently minimize wait time between time-constrained tasks

本文关键字：之间 等待时间 任务 时间约束 有效地      更新时间：2023-09-26

我有一个任务数组，其中每个任务是一个具有以下属性的对象:

  • startTime:任务启动时间(previous finishTime + travelTime)
  • serviceTime:任务完成所需的时间
  • waitTime:空闲时间(目标)
    • finishTime: sum(starTime, serviceTime, waitTime)
  • travelTime: time to get to next task
  • earlyStart:任务可能不会在此时间之前启动
  • lateStart:任务可能不迟于此时间

在LP术语中(忽略无聊的东西):

  • 目标:最小化waitTime
  • 主题:
    • earlyStart <= startTime
    • startTime <= lateStart

顺序固定&所有作业必须按顺序一次执行一个。如果没有找到可行的解决方案，我就不返回任何东西，尽管在大多数情况下，我从一个可行的解决方案开始，但它不一定是最优的。我的尝试花了O(n!)时间，所以我很确定有更好的方法，只是我没有考虑。这似乎是一个相当普遍的问题& &;我很确定它甚至不是np完备的，但我找不到它的名字来进一步研究。我是用JavaScript写的，但是任何想法、链接、伪代码或高性能的c++实现都是欢迎的!

这个问题相当于最小化最后一个任务的开始时间与第一个任务的开始时间之差。等效性源于这样一个事实，即如果您将任何任务的开始时间推到中间，则总体等待时间不会改变(任务扩展后的等待时间减少的量与任务扩展前的等待时间相同)。

一个简单的O(n^2)算法如下:
  • 让第一个任务越晚越好。
  • 迭代剩余的任务
    • 根据前面的任务查找尽可能早的开始时间
    • 如果不可能(因为此时间晚于lateStart)，则尽可能少地将前一个任务推到开始位置。如果它与前一个任务发生冲突，则在那里执行相同的操作，依此类推。
    • 如果您需要在earlyStart之前推送第一个任务，则没有解决方案。

如果可能将所有任务(或同时包含第一个和最后一个任务的子集或两者都不包含的子集)按恒定的时间推入，则可能没有唯一的解决方案。

相关文章：