查看“︁单机调度”︁的源代码

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

单机调度问题是同机调度问题的特殊情况，而同机调度又是最优作业调度的特殊情况。许多常见的[[NP困难]]问题在单机调度问题中都可以在多项式时间内解决。<ref name=":0">{{Cite journal|last=Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys|date=1993-01-01|title=Chapter 9 Sequencing and scheduling: Algorithms and complexity|url=https://www.sciencedirect.com/science/article/abs/pii/S0927050705801896|journal=Handbooks in Operations Research and Management Science|language=en|volume=4|pages=445–522|doi=10.1016/S0927-0507(05)80189-6|issn=0927-0507|access-date=2022-02-23|archive-date=2022-02-23|archive-url=https://web.archive.org/web/20220223032800/https://www.sciencedirect.com/science/article/abs/pii/S0927050705801896|dead-url=no}}</ref>{{Rp|10-20}}

在最优作业调度问题的标准三字段表示法中，单机变量在第一个字段中用'''1'''表示。例如<math>1||\sum C_j</math>可以用来表示无约束的同机调度问题，其目标是最小化完成时间的总和。
==变体==
最小化[[加工周期]]问题<math>1||\sum C_{\max}</math>在多机调动中经常被当成目标函数，但在单机调度中意义不大。在单机调度中，我们经常选择一些其他的目标函数进行研究：<ref name=":1">{{Cite web|last=Grinshpoun|first=Tal|date=2020|title=Subjects in Scheduling|url=https://www.youtube.com/user/grinshpo|url-status=no|access-date=2021-09-12|website=www.youtube.com|archive-date=2022-03-03|archive-url=https://web.archive.org/web/20220303062918/https://www.youtube.com/user/grinshpo}}</ref>
*<math>1|| \sum C_j</math>是最小化完工时间总和的问题，该问题可用最短处理时间优先（{{lang-en|Shortest Processing Time First}}，'''SPT'''）原则来解决，即优先解决处理时间短的任务。
**<math>1|| \sum w_j C_j</math>是最小化加权完工时间总和的问题，该问题可用加权最短处理时间优先（{{lang-en|Weighted Shortest Processing Time First}}，'''WSPT'''）原则来解决，即优先解决权重和处理时间之比（<math>p_j/w_j</math>）更大的任务。<ref name=":1" />{{Rp|lecture 1, part 2}}
**<math>1|chains| \sum w_j C_j</math>是在具有任务顺序限制的情况下最小化加权完工时间总和的问题，这类问题可以通过泛化的加权最短处理时间优先原则来解决。<ref name=":1" />{{Rp|lecture 1, part 3}}
*<math>1||L_{\max}</math>是最小化最大延迟时间的问题，在这类问题中，每个工作<math>j</math>都存在一个截止日期<math>d_j</math>，如果在截止日期之后才完成任务，那么就会产生一个[[延遲 (排程)|延迟]]，延迟的定义是<math>L_j := C_j - d_j </math>。这类问题可以用最早截止日期优先（{{lang-en|Earliest Due Date First}}，'''EDD'''）原则来解决，即优先解决<math>d_j</math>靠前的任务。<ref name=":1" />{{Rp|lecture 2, part 2}}
**<math>1|prec|h_{\max}</math>问题是<math>1||L_{\max}</math>问题的泛化。这个问题允许对任务设定前后顺序，并且允许对每个任务的延迟都设定一个成本函数<math>h_j</math>。这一目标函数可以通过一种被称为[[劳勒算法]]的[[贪心算法]]进行最小化。<ref name=":1" />{{Rp|lecture 2, part 1}}
**<math>1|r_j|L_{\max}</math>问题也是<math>1||L_{\max}</math>问题的泛化。这一问题允许对每一项任务设定推出时间<math>r_j</math>，每项任务都不得在推出时间之前进行，这就导致了机器可能处于闲置状态。这是一个NP难度的问题，但是可以采取[[分支定界]]算法进行优化。<ref name=":1" />{{Rp|lecture 2, part 3}}
*<math>1||\sum U_j</math>是最小化迟到任务数量的问题，但是不考虑每个迟到任务的延迟。这一问题可以使用霍奇森-摩尔算法进行优化。<ref>{{Cite journal|date=1994-07-01|title=Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the ‘tower of sets’ property|url=https://www.sciencedirect.com/science/article/pii/0895717794902097|journal=Mathematical and Computer Modelling|language=en|volume=20|issue=2|pages=91–106|doi=10.1016/0895-7177(94)90209-7|issn=0895-7177|doi-access=free|access-date=2022-03-03|archive-date=2022-03-11|archive-url=https://web.archive.org/web/20220311221931/https://www.sciencedirect.com/science/article/pii/0895717794902097|dead-url=no}}</ref><ref name=":1" />{{Rp|lecture 3, part 1}}
**<math>1||\sum w_j U_j</math>是最小化加权后迟到任务数量的问题。这是一个NP难度的问题，因为在每个任务的截止时间都相等（<math>1|d_j=d|\sum w_j U_j</math>）的特殊情况下，这一问题等价于[[背包问题]]。<ref name=":1" />{{Rp|lecture 3, part 2}}
*现假定在截止时间之前完成任务就能得到<math>p_j</math>的收益，反之则无收益。问题的目标是最大化收益。这一问题属于NP困难的问题，计算机科学家薩爾塔伊·薩尼找出了[[指數時間]]的准确算法和多项式时间的[[近似算法]]。<ref>{{Cite journal|last=Sahni|first=Sartaj K.|date=1976-01-01|title=Algorithms for Scheduling Independent Tasks|url=https://doi.org/10.1145/321921.321934|journal=Journal of the ACM|volume=23|issue=1|pages=116–127|doi=10.1145/321921.321934|issn=0004-5411}}</ref>

==参考文献==
{{reflist}}

{{调度问题}}
{{Authority control}}
[[Category:最佳排程]]