并行设备上的差异作业批调度问题及多项式算法

摘要

考虑了一类作业尺寸有差异的批调度问题,加工环境为并行批处理设备.以制造跨度为优化目标,建立了基于整数规划的数学模型；分析了制造跨度最小化问题的计算复杂性,给出问题可行解规模的上下界；然后设计了一种基于LPT规则和Batch First Fit规则的近似算法,证明了算法的时间性能为O(nlogn),算法在优化制造跨度时的最坏性能比为(8/3～2/3m).