Machine-fixed, machining-assembly flow shop scheduling

In this paper effective heuristics are proposed for minimizing makespan in machine-fixed, machining-assembly flowshop scheduling, where parts of each job are machined on prespecified parallel machines in the machining stage and then assembled in the assembly stage after all component parts have been completed. Since this problem is NP-complete, several heuristics have been proposed so far by converting the original problem into the usual two-machine flowshop problem which can be solved through Johnson's algorithm. However, the tight upper boundaries for the relative error in these heuristics are very large, i.e., 50–100%. The heuristics proposed in this paper exploit the basic idea of Johnson's rule, Gupta's idea and the results of worst/difficult case analyses without any conversion of the original problem into the usual two-machine flowshop problem. Numerical experiments showed that the proposed heuristics can efficiently solve all problems generated randomly for the two parallel-machine case, and can solve more than 99.0 percent of the problems for three and five parallel-machine cases. These heuristics are superior to the usual branch and boundary algorithm with a limited computation time of 30 minutes, not only in efficiency but also in accuracy.