• CN: 11-2187/TH
  • ISSN: 0577-6686

›› 2011, Vol. 47 ›› Issue (4): 186-191.

• Article • Previous Articles     Next Articles

Hybrid Algorithm for JSP with Discretely Controllable Processing Times

NIU Ganggang;SUN Shudong;LI Jingyao;SUN Qifeng;WANG Junqiang   

  1. Institute of System Integration and Engineering Management, Northwestern Polytechnical University Key Laborary of Contemporary Design and Integrated Manufacturing Technology of Ministry of Education
  • Published:2011-02-20

Abstract: 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.

Key words: Decomposition, Discretely controllable processing times, Hybrid algorithm, Job-shop, Plug-in hybrid electric vehicle Genetic algorithm (GA) global optimization Discrete optimization of the equivalent factor Control strategy based ECMS

CLC Number: