Decomposition-based Makespan Minimization in Job Shops

This paper proposes a decomposition-based heuristic approach to minimizing the makespan of job shops. In general, decomposition methods first divide the whole problem into several sub-problems, solve them and then combine sub-schedules to obtain a good feasible schedule. Although it may be reasonable to minimize the makespan of each sub-problem, its optimality will be lost when combining sub-schedules and making the whole schedule be feasible. If each sub-schedule is relatively insensitive to the uncertainty of processing times, this property may weaken the relationship between sub-schedules, and a feasible solution may be obtained without affecting the optimality so much. Based on this idea, a minimum instability schedule is selected from the set of makespan-minimum active schedules as the solution for sub-problems. The minimum instability schedule is the least sensitive schedule against the one time unit of completion delay in an operation. Three benchmark problems were solved to examine the effectiveness of adopting the minimum instability schedules. The results indicated that the minimum instability sub-schedules often produced better whole schedules when compared with the schedules based on the maximum instability sub-schedules.