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

{{Tone|time=2022-03-19T05:12:03+00:00}}
'''同机调度'''是[[计算机科学]]和[[运筹学]]中的一个优化问题。在这一问题中，我们有从<math>J_1</math>到<math>J_n</math>这n个不同执行时间的工作需要完成。除此之外，我们有m个完全相同的机器。在这一问题中，我们需要对特定的目标函数（如[[加工周期]]）进行优化。

同机调度是[[统一机器调度]]的一种特殊情况，而统一机器调度本身也是最优作业调度的一种特殊情况。两者的区别在于同机调度中所有的机器完全一样，而在统一机器调度中不同的机器执行相同的任务所需时间可能会有所不同。[[单机调度]]也可以视为一种特殊的同机调度。在最优作业调度问题的标准三字段表示法中，同机变量在第一个字段中用字母'''P'''表示。例如<math>P||C_max</math>可以用于表示无约束条件的同机调度问题，其目标是最小化最大完工时间。
==算法==
===最小化平均和加权平均完工时间===
最小化平均完成时间（<math>P||\sum C_j</math>）可以在多项式时间内完成。可以采用最短完工时间优先算法，先对所有工作的按完工时间从小到大进行排序，然后再将这些工作按此顺序分配给目前结束时间最早的机器。该算法的时间复杂度为<math>O(nlogn)</math>。<ref name=":0">{{Cite journal|last1=Horowitz|first1=Ellis|last2=Sahni|first2=Sartaj|date=1976-04-01|title=Exact and Approximate Algorithms for Scheduling Nonidentical Processors|url=https://doi.org/10.1145/321941.321951|journal=Journal of the ACM|volume=23|issue=2|pages=317–327|doi=10.1145/321941.321951|s2cid=18693114|issn=0004-5411}}</ref>
*寻找最小完工时间问题属于[[NP困难]]问题。

即使在完全相同的机器上，最小化加权平均完成时间也属于NP困难问题，因为这类问题可以转化为[[背包问题]]。<ref name=":0" />即使将机器数量限定在两台，该类问题也属于NP困难问题，因为此类问题相当于[[分区问题]]。
===最小化最大完成时间===
最小化最大完成时间问题（<math>P||C_{max}</math>）属于NP困难问题，因为这类问题等同于分区问题。对这类问题，目前已经有人给出了多种精确以及近似算法。

[[葛立恒]]给出的证明如下：
*任何列表调度算法（一种以任意固定顺序处理工作的算法，并将每个作业调度到第一个可用的机器上）都在同机调度问题上具有<math>2-1/m</math>的近似。<ref name=":2">{{Cite journal|last=Graham|first=Ron L.|author-link=葛立恒|date=1966|title=Bounds for Certain Multiprocessing Anomalies|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1966.tb01709.x|journal=Bell System Technical Journal|language=en|volume=45|issue=9|pages=1563–1581|doi=10.1002/j.1538-7305.1966.tb01709.x|issn=1538-7305|access-date=2022-03-15|archive-date=2022-03-15|archive-url=https://web.archive.org/web/20220315084226/https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1966.tb01709.x}}</ref>对于任何的m，该上界都存在严格约束，该算法所需时间为<math>O(n)</math>。
*最长处理时间优先算法是一种特殊的列表调度算法，这些工作按作业时长的降序进行排序，对于相同的机器而言，具有<math>4/3-1/3m</math>的近似。<ref name=":1">{{Cite journal|last=Graham|first=Ron L.|author-link=葛立恒|date=1969-03-01|title=Bounds on Multiprocessing Timing Anomalies|url=https://epubs.siam.org/doi/abs/10.1137/0117039|journal=SIAM Journal on Applied Mathematics|volume=17|issue=2|pages=416–429|doi=10.1137/0117039|issn=0036-1399|access-date=2022-03-15|archive-date=2021-10-28|archive-url=https://web.archive.org/web/20211028071142/https://epubs.siam.org/doi/abs/10.1137/0117039}}</ref>{{Rp|sec.5}}

科夫曼、格里和约翰逊提出了multifit算法，该算法使用了[[集装优化]]中所使用的方法，其近似因子为13/11≈1.182。

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

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