带恶化工件的PFS调度的混合遗传算法

A Hybrid Genetic Algorithm for Permutation Flowshop Scheduling with Deteriorating Jobs

研究了带恶化工件的置换流水车间调度问题,其中工件的加工时间是与开始时间有关的线性函数,考虑不同工件在不同机器上具有不同的恶化率,以最小化最大完工时间为目标,建立数学规划模型,进而提出了一种混合遗传算法来求解。该算法引入一种启发式规则以产生m-1条染色体改进初始种群的40%,结合遗传算法的初始种群产生方法共同生成种群,设计遗传参数自适应调节。仿真实验测试和对比了启发式法、遗传算法和混合遗传算法三种求解方法,实验结果表明所提出的混合遗传算法能更有效地求解这类NP-hard问题。

Permutation flowshop scheduling problem with deteriorating jobs was studied where the processing time of a job is a linear function of its starting time. Each job has its own deterioration rate on each machine. A mathematical model was then formulated with the objective of minimizing the maximum completion time and a hybrid genetic algorithm was proposed to solve it. In this algorithm, a heuristic rule is introduced to generate m-1 chromosome in order to improve 40% of the initial population. Further, it is applied to produce the population together with the generation method of the initial population of genetic algorithm. Adaptive adjustment of genetic parameters was designed. Simulation experiments test and comparisons among a heuristic algorithm, a genetic algorithm and the hybrid genetic algorithm were conducted. The experimental results show that the proposed hybrid genetic algorithm can solve the NP-hard problem effectively.