A decomposition approach to two-stage hybrid flow shop scheduling with diverging jobs

A two-stage hybrid flow shop associated with process industry is considered, in which job batch size(s) must be determined together with their schedule. This problem contains a combination of features not usually considered in standard scheduling models, such as i) overlapping production, ii) job diverging, and iii) multiple performance measures (the number of setups, demand satisfaction ratio, and inventory level). We propose ‘a decomposition approach’, which breaks down the entire problem into three subproblems, upper-/lower-stage batching subproblems and a scheduling subproblem so that these problems have a hierarchical structure. Each of the batching subproblems to minimize the number of setups while maximizing demand satisfaction ratio, is formulated as a mixed integer program and solved independently. Based on the job batch sizes thus obtained, the scheduling subproblem is then solved by an iterative algorithm in which upper- and lower-stage schedules are generated alternately based on the information of intermediate inventory obtained from the repeated solutions of one-machine sub-subproblems. These procedures try to improve demand satisfaction ratio and also to reduce intermediate inventory, while keeping the number of setups derived by the batching subproblems. Numerical experiments show that inventory level is reduced substantially by the proposed set of procedures.