一种求解车间调度问题的混沌遗传规划方法

摘要

作业车间调度问题是制造业的一个经典 NP-hard 组合优化难题.提出一种基于混沌遗传规划的调度算法,利用遗传规划进行染色体的结构设计,采用混沌序列改善初始种群质量,利用混沌扰动来维持进化群体的多样性,并自适应调整个体权重,使算法具有优良的综合求解性能.实验表明,算法对典型的标准调度测试问题具有较强的全局搜索能力,甘特图表明其获得的最优解优于当前已知的最优解历史记录,对比结果表明了该方法的有效性.%The job-shop scheduling problem is an NP-hard combinational optimization problem in the manufacturing field. The paper proposes a job-shop scheduling algorithm based on chaos genetic programming. Genetic programming is adopted to design a chromosome structure,the chaos sequence method is used to improve the quality of initial population,chaos disturbances are taken to maintain the diversity of evolutionary population, and the self-adaptive adjusting method of individual weight is applied.Accordingly the proposed algorithm has a comprehensive solving capacity for a scheduling problem. Simulation experiments show that it has better ability to find the global optimum for several typical scheduling testing benchmarks. The results of Gantt charts point out that the optimum solutions obtained by this novel algorithm are better than the historic ones. The comparison of the results reveals the feasibility and efficiency of the method.