Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due dates

We consider the scheduling problem in hybrid flow shops that consist of two stages in series, each of which has multiple identical parallel machines. Each job has reentrant flow, i.e., the job visits each production stage several times. The problem is to determine the allocation of jobs to machines as well as the sequence of the jobs assigned to each machine for the objective of minimizing makespan subject to the maximum allowable due dates in the form of a constraint set with a certain allowance. To solve the problem, two types of algorithms are suggested: (a) a branch and bound algorithm that gives optimal semi-permutation schedules; and (b) heuristic algorithms that give non-permutation schedules. To show their performances, computational experiments were done on a number of test problems and the results are reported. In particular, one of the heuristics is competitive to the branch and bound algorithm with respect to the solution quality while requiring much shorter computation times.