Decomposition methods for large job shops

There has been a significant amount of research focused on the scheduling of a job shop, either minimizing the makespan or the tardiness. Although the results for small size problems are satisfactory, there is not yet an approach for middle and large size problems. This paper presents a heuristic that decomposes the problems on a time window basis, solving each subproblem using a shifting bottleneck heuristic. Its results for a due date related objective function are promising.