A decomposition approach to the solution of large-scale scheduling problems (Q796447)

When planning the manufacturing of a discrete medium-sized product we are faced with the problem of scheduling which involves sequencing of and assigning deadlines to several tens and even hundreds of thousands of activities (technological processes or jobs). For larger products, these numbers are substantially greater. Therefore, activity scheduling in this context is unpracticable unless the original problem can be partitioned into subproblems and the solutions obtained for the individual subproblems can then be combined into a solution of the original problem. The proposed decomposition and aggregation method employs a modification of the combinatorial algorithm presented in a previous paper of the author [Avtom. Telemekh. 1982, No.4, 72-77 (1982)], utilizing the network properties of the data describing the product and the manufacturing technology. In this way the scheduling subproblems need not be solved by an exact method and any heuristic single-pass method with a priority rule is quite adequate for these purposes. This appears to be the only practicable approach to the solution of scheduling problems in acceptable time.