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