单机调度

单机调度也被称为单资源调度,是计算机科学运筹学中的一个最佳化問題。在这一问题中,我们有从个工作,每项工作所需处理时间都不尽相同。我们所需要做的便是将这些工作在机器上进行排程,使其目标函数(诸如吞吐量)实现最佳化。

单机调度问题是同机调度问题的特殊情况,而同机调度又是最优作业调度的特殊情况。许多常见的NP困难问题在单机调度问题中都可以在多项式时间内解决。[1]:10-20

在最优作业调度问题的标准三字段表示法中,单机变量在第一个字段中用1表示。例如可以用来表示无约束的同机调度问题,其目标是最小化完成时间的总和。

变体

最小化加工周期问题 在多机调动中经常被当成目标函数,但在单机调度中意义不大。在单机调度中,我们经常选择一些其他的目标函数进行研究:[2]

  •  是最小化完工时间总和的问题,该问题可用最短处理时间优先(英語:Shortest Processing Time FirstSPT)原则来解决,即优先解决处理时间短的任务。
    •  是最小化加权完工时间总和的问题,该问题可用加权最短处理时间优先(英語:Weighted Shortest Processing Time FirstWSPT)原则来解决,即优先解决权重和处理时间之比( )更大的任务。[2]:lecture 1, part 2
    •  是在具有任务顺序限制的情况下最小化加权完工时间总和的问题,这类问题可以通过泛化的加权最短处理时间优先原则来解决。[2]:lecture 1, part 3
  •  是最小化最大延迟时间的问题,在这类问题中,每个工作 都存在一个截止日期 ,如果在截止日期之后才完成任务,那么就会产生一个延迟,延迟的定义是 。这类问题可以用最早截止日期优先(英語:Earliest Due Date FirstEDD)原则来解决,即优先解决 靠前的任务。[2]:lecture 2, part 2
    •  问题是 问题的泛化。这个问题允许对任务设定前后顺序,并且允许对每个任务的延迟都设定一个成本函数 。这一目标函数可以通过一种被称为劳勒算法贪心算法进行最小化。[2]:lecture 2, part 1
    •  问题也是 问题的泛化。这一问题允许对每一项任务设定推出时间 ,每项任务都不得在推出时间之前进行,这就导致了机器可能处于闲置状态。这是一个NP难度的问题,但是可以采取分支定界算法进行优化。[2]:lecture 2, part 3
  •  是最小化迟到任务数量的问题,但是不考虑每个迟到任务的延迟。这一问题可以使用霍奇森-摩尔算法进行优化。[3][2]:lecture 3, part 1
    •  是最小化加权后迟到任务数量的问题。这是一个NP难度的问题,因为在每个任务的截止时间都相等( )的特殊情况下,这一问题等价于背包问题[2]:lecture 3, part 2
  • 现假定在截止时间之前完成任务就能得到 的收益,反之则无收益。问题的目标是最大化收益。这一问题属于NP困难的问题,计算机科学家薩爾塔伊·薩尼找出了指數時間的准确算法和多项式时间的近似算法[4]

参考文献

  1. ^ Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys. Chapter 9 Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science. 1993-01-01, 4: 445–522 [2022-02-23]. ISSN 0927-0507. doi:10.1016/S0927-0507(05)80189-6. (原始内容存档于2022-02-23) (英语). 
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 Grinshpoun, Tal. Subjects in Scheduling. www.youtube.com. 2020 [2021-09-12]. (原始内容存档于2022-03-03). 
  3. ^ Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the ‘tower of sets’ property. Mathematical and Computer Modelling. 1994-07-01, 20 (2): 91–106 [2022-03-03]. ISSN 0895-7177. doi:10.1016/0895-7177(94)90209-7 . (原始内容存档于2022-03-11) (英语). 
  4. ^ Sahni, Sartaj K. Algorithms for Scheduling Independent Tasks. Journal of the ACM. 1976-01-01, 23 (1): 116–127. ISSN 0004-5411. doi:10.1145/321921.321934.