考虑机器数量增加的多处理机工件调度优化
来源：计算机集成制造系统杂志2025年第3期北京时间：
作者：孙涛, 王军强, 黄永兴
单位：1.西北工业大学生产与运作系统性能分析中心2.西北工业大学机电学院工业工程系
摘要：多处理机工件是在同一时刻由多台处理机并行加工的工件。面向以最小化最大完工时间为目标的多处理机工件调度,分析了机器数量增加对最大完工时间的影响,证明了最优调度方案和所提近似调度方案的最好情形影响比,揭示了最大完工时间随着机器数量增加而减少并趋于稳定的规律。分析了机器数量增加的影响,一方面改善了调度目标,另一方面增加了机器投入成本。权衡最大完工时间减少和机器成本增加两方面影响,以最小化最大完工时间与机器成本加权和为目标决策机器数量。基于降序首次适应算法设计了近似算法,给出了调度优化方案,并证明了所提算法的最差性能比不超过2。通过仿真实验,验证了所提算法的最好情形影响比及算法的有效性。
关键词：多处理机工件调度,资源扩充,最好情形影响比,近似算法,最差性能比
基金资助：国家自然科学基金资助项目(52075453,71931007);国家留学基金委资助项目(202206290105)。
