带恶化工件的不相关并行机调度优化

Optimization for Unrelated Parallel Machine Scheduling with Deteriorating Jobs

研究了以最小化最大完工时间为目标的不相关并行机环境下带恶化工件的车间调度问题,工件的加工时间随着开始时间的不同而改变,将其表示为开始时间的增函数,假设每个工件在不同机器上有各自的恶化系数。针对该NP-hard问题,建立数学规划模型,设计基于两段式编码和遗传参数自适应调节策略的改进遗传算法以合理地进行工件排序及机器分配。通过测试不同规模问题的仿真实验,对比结果表明所设计的算法在求解时间和求解质量上均具有较大优势。

Unrelated parallel machine scheduling problem with deteriorating jobs is studied with the objective of minimizing the maximum completion time.The processing time of a job varies with its beginning time which is denoted as an increasing function of its starting time.It is assumed that each job has its own different deterioration rate on each machine.A mathematical programming model is formulated for the NP-hard problem.An improved genetic algorithm based on two segment coding and self-adaptive adjustment of genetic parameters is then designed to make job scheduling and machine allocation more reasonable.Through the simulation experiments of different sized problems,the results show that the proposed algorithm has more advantages in both resolution time and solution quality.