Hybrid flow shop scheduling with specialised machines

We analyse the industrial system and propose a model for the overall process. This model possesses several features of note - it has multiple processing stages, with parallel machines at each stage; jobs may be restricted in which machines can process them at each stage (processing set restrictions); jobs may omit stages; material flows from one stage to the next as a continuous stream; and there is highly flexible inter-process storage of interim products. A simplified model, extending the hybrid flow shop model from the literature, is also presented. The scheduling of the system is approached in two steps. Firstly, we develop algorithms for solving the scheduling problems at each stage - parallel machines with processing set restrictions. We present efficient and exact algorithms for problems with unit-length jobs, across a wide range of the standard regular objective functions. We also suggest three heuristic algorithms for minimising the maximum lateness on identical parallel machines with processing set restrictions and general job lengths: Earliest Due Date (EDD); Jackson for Processing Sets (JPS); and Nested Jackson (NJ). Secondly, we develop a generalised framework for hierarchical decomposition, aimed at solving hybrid flow shop problems. The framework has four separate major components: decomposition into sub-problems, ordering of sub-problems, sub-problem solution, and backtracking. For each of these we develop several alternative methods. The framework is then tested on a wide variety of problems using computation methods. We conclude that decomposition of the problem by execution sets, solving the sub-problems in stage order with the EDD solution method and using multiple-pass backtracking produces the best quality solutions.