Abstract: A multi-processor job is the job that requires simultaneously more than one machine for its processing.For the multi-processor job scheduling problem with minimizing the makespan,the impact of increasing the number of machines on the makespan was analyzed,the best-case impact ratio for the optimal schedule and that for approximation schedules were proved,and the law that the makespan decreases and trends toward stabilization as the number of machines increases was revealed.Furthermore,increasing the number of machines results in a decrease in the makespan but  an increase in the machine costs.The trade-off between the decrease in the makespan and increase in the machine costs was analyzed,and the number of machines was determined to minimize the weighted sum of the makespan and the machine costs.An approximation algorithm based on the first fit decreasing algorithm was designed to obtain the schedule.The worst-case performance ratio of the approximation algorithm was proved to be no greater than 2.The simulation results show the effectiveness of the best-case impact ratios for the approximation schedules and the worst-case performance ratio of the designed approximation algorithm.

Key words: multi-processor job scheduling, resource augmentation, best-case impact ratio, approximation algorithm, worst-case performance ratio

摘要： 多处理机工件是在同一时刻由多台处理机并行加工的工件。面向以最小化最大完工时间为目标的多处理机工件调度,分析了机器数量增加对最大完工时间的影响,证明了最优调度方案和所提近似调度方案的最好情形影响比,揭示了最大完工时间随着机器数量增加而减少并趋于稳定的规律。分析了机器数量增加的影响,一方面改善了调度目标,另一方面增加了机器投入成本。权衡最大完工时间减少和机器成本增加两方面影响,以最小化最大完工时间与机器成本加权和为目标决策机器数量。基于降序首次适应算法设计了近似算法,给出了调度优化方案,并证明了所提算法的最差性能比不超过2。通过仿真实验,验证了所提算法的最好情形影响比及算法的有效性。

关键词: 多处理机工件调度, 资源扩充, 最好情形影响比, 近似算法, 最差性能比