同机调度是计算机科学和运筹学中的一个优化问题。在这一问题中，我们有从J_1到J_n这n个不同执行时间的工作需要完成。除此之外，我们有m个完全相同的机器。在这一问题中，我们需要对特定的目标函数（如加工周期）进行优化。
同机调度是统一机器调度的一种特殊情况，而统一机器调度本身也是最优作业调度的一种特殊情况。两者的区别在于同机调度中所有的机器完全一样，而在统一机器调度中不同的机器执行相同的任务所需时间可能会有所不同。单机调度也可以视为一种特殊的同机调度。在最优作业调度问题的标准三字段表示法中，同机变量在第一个字段中用字母P表示。例如P||C_max可以用于表示无约束条件的同机调度问题，其目标是最小化最大完工时间。
算法
最小化平均和加权平均完工时间
最小化平均完成时间（P||\sum C_j）可以在多项式时间内完成。可以采用最短完工时间优先算法，先对所有工作的按完工时间从小到大进行排序，然后再将这些工作按此顺序分配给目前结束时间最早的机器。该算法的时间复杂度为O(nlogn)。
*寻找最小完工时间问题属于NP困难问题。
即使在完全相同的机器上，最小化加权平均完成时间也属于NP困难问题，因为这类问题可以转化为背包问题。对于任何的m，该上界都存在严格约束，该算法所需时间为O(n)。
*最长处理时间优先算法是一种特殊的列表调度算法，这些工作按作业时长的降序进行排序，对于相同的机器而言，具有4/3-1/3m的近似。
科夫曼、格里和约翰逊提出了multifit算法，该算法使用了集装优化中所使用的方法，其近似因子为13/11≈1.182。
参考文献
评论 (0)