Minimizing makespan on a two-machine re-entrant flowshop
研究了两台机器重入流水车间中最小化最大完工时间的调度问题，所有工件需在两台机器上各加工两次。提出了支配性质、下界和启发式算法，并开发了分支定界算法，实验表明该算法可有效求解多达200个工件的问题。
Abstract This paper focuses on a two-machine re-entrant flowshop scheduling problem with the objective of minimizing makespan. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. We develop dominance properties, lower bounds and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 200 jobs in a reasonable amount of CPU time.