Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems (Q2265944)

Three different decomposition approaches are described for permutation schedules. The first, Complete decomposition, gives conditions when a scheduling problem can be decomposed into two or more scheduling problems that ca be solved separately and then recomposed. Except for some single machine scheduling problems and a few cases of other problems, it is unlikely that these conditions will be satisfied. A Partial decomposition may be employed if the Complete decomposition fails. This requires a subset enumeration procedure along with a partial satisfaction of the conditions specified before. The majority of NP-complete scheduling problems will not meet the conditions necessary to employ either of the above decompositions. In this case branch and bound can be used as a decomposition tool (Iterative decomposition). Algorithms are developed that provide upper bounds, lower bounds, branching rules as well as a heuristic estimate of the lower bound. This branch and bound decomposition approach is then implemented on the M-machine flow problem. The algorithm developed, efficiently finds optimal solutions to small flow shop problems (5 jobs/5 machines). Since the variance of CPU times required to use this algorithm is high, two heuristic algorithms are suggested. These algorithms either heuristically fathom nodes or terminate early. Their CPU times are small compared to the optimal algorithm and they provide schedules almost as good, and are therefore viewed as a practical alternative.