一种求解加工时间离散可控作业车间调度问题的混合算法

摘要：

加工时间离散可控作业车间调度问题(Job-shop scheduling problem with discretely controllable processing times,JSP-DCPT)是经典作业车间调度问题(Job-shop scheduling problem,JSP)的一类扩展问题.为避免通过多项式时间近似方法求解JSP-DCPT的近似问题,提出一种混合算法直接求解JSP-DCPT.该算法基于分解方法,嵌套一种禁忌搜索模拟退火混合算法TSSA和一种快速精英保留非支配排序遗传算法NSGA-II,以分别高效求解JSP-DCPT分解所得的JSP子问题和离散时间一成本权衡子问题.基于JSP标准算例FT06,FT10和FT20构造3个不同问题规模的测试算例,试验仿真结果表明,混合算法能够得到收敛的帕累托边界.

关键词：作业车间、离散可控加工时间、分解、混合算法

所属期刊栏目：47

分类号：TH18

资助基金：国家自然科学基金51075337,50705076,50705077;陕西省自然科学基础研究计划2009JQ9002

在线出版日期：2011-06-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：186-191,198