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

Hybrid Algorithm for JSP with Discretely Controllable Processing Times

加工时间离散可控作业车间调度问题(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.