Scheduling larger job shops: A decomposition approach

Large scale job scheduling problems are addressed in this paper through a divide and conquer scheme. With the scheme, a job shop is first decomposed into cells, a shop scheduling problem is then solved through iteratively defining, solving and coordinating cell scheduling problems. So-called proxy operations and dummy machines are employed to account for the interactions between the cell scheduling problems. The scheme is tested on total flow time reduction job shop scheduling problems with the problem sizes up to 120 machines and 200 jobs. The computational results show that the scheme is effective.