考虑机器数量增加的多处理机工件调度优化  

Multi-processor job scheduling with increasing the number of machines

作　　者：孙涛[1,2] 王军强 黄永兴[1,2] SUN Tao;WANG Junqiang;HUANG Yongxing(Performance Analysis Center of Production and Operations Systems,NorthwesternPolytechnical University,Xi'an 710072,China;Department of Industrial Engineering,School of Mechanical Engineering,NorthwesternPolytechnical University,Xi'an 710072,China)

机构地区：[1]西北工业大学生产与运作系统性能分析中心,陕西西安710072 [2]西北工业大学机电学院工业工程系,陕西西安710072

出　　处：《计算机集成制造系统》2025年第3期924-938,共15页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(52075453,71931007);国家留学基金委资助项目(202206290105)。

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

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

分 类 号：TH186[机械工程—机械制造及自动化]