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

Hybrid Algorithm for JSP with Discretely Controllable Processing Times

作　　者：牛刚刚[1,2] 孙树栋[1,2] 李兢尧[1,2] 孙启峰[1,2] 王军强[1,2] 

机构地区：[1]西北工业大学系统集成与工程管理研究所,西安710072 [2]西北工业大学现代设计与集成制造技术教育部重点实验室,西安710072

出　　处：《机械工程学报》2011年第4期186-191,198,共7页Journal of Mechanical Engineering

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

摘　　要：加工时间离散可控作业车间调度问题(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个不同问题规模的测试算例,试验仿真结果表明,混合算法能够得到收敛的帕累托边界。Job-shop scheduling problem with discretely controllable processing times（JSP-DCPT） is a generalization of the classical Job-shop scheduling problem（JSP）.To avoid solving the approximate problem of JSP-DCPT by using polynomial time approximation schemes,a hybrid algorithm is proposed to solve JSP-DCPT directly.Based on a decomposition approach,both the hybrid algorithm of tabu search and simulated annealing（TSSA） and the fast elitist non-dominated sorting genetic algorithm（NSGA-II） are nested within the proposed algorithm in order to effectively and efficiently solve the JSP and the discrete time-cost tradeoff problems decomposed from JSP-DCPT.Computational instance of different problem size is separately constructed on the basis of JSP benchmark FT06,FT10 and FT20.Experimental simulation results demonstrate that constrained Pareto frontiers can be obtained by using the proposed hybrid algorithm.

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

分 类 号：TH18[机械工程—机械制造及自动化]