单机调度
外观
单机调度也被称为单资源调度,是计算机科学和运筹学中的一个最佳化问题。在这一问题中,我们有从到这个工作,每项工作所需处理时间都不尽相同。我们所需要做的便是将这些工作在机器上进行排程,使其目标函数(诸如吞吐量)实现最佳化。
单机调度问题是同机调度问题的特殊情况,而同机调度又是最优作业调度的特殊情况。许多常见的NP困难问题在单机调度问题中都可以在多项式时间内解决。[1]:10-20
在最优作业调度问题的标准三字段表示法中,单机变量在第一个字段中用1表示。例如可以用来表示无约束的同机调度问题,其目标是最小化完成时间的总和。
变体
[编辑]最小化加工周期问题在多机调动中经常被当成目标函数,但在单机调度中意义不大。在单机调度中,我们经常选择一些其他的目标函数进行研究:[2]
- 是最小化完工时间总和的问题,该问题可用最短处理时间优先(英语:Shortest Processing Time First,SPT)原则来解决,即优先解决处理时间短的任务。
- 是最小化最大延迟时间的问题,在这类问题中,每个工作都存在一个截止日期,如果在截止日期之后才完成任务,那么就会产生一个延迟,延迟的定义是。这类问题可以用最早截止日期优先(英语:Earliest Due Date First,EDD)原则来解决,即优先解决靠前的任务。[2]:lecture 2, part 2
- 是最小化迟到任务数量的问题,但是不考虑每个迟到任务的延迟。这一问题可以使用霍奇森-摩尔算法进行优化。[3][2]:lecture 3, part 1
- 现假定在截止时间之前完成任务就能得到的收益,反之则无收益。问题的目标是最大化收益。这一问题属于NP困难的问题,计算机科学家萨尔塔伊·萨尼找出了指数时间的准确算法和多项式时间的近似算法。[4]
参考文献
[编辑]- ^ 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.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).
- ^ 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) (英语).
- ^ 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.
|