Scheduling alternative operations in two-machine flow-shops

Most of the previous studies on scheduling problems assume that each machine is used exclusively for one operation although it has, in practice, potential to carry out some others. This paper studies two-machine flow-shop scheduling problems in which either or both machines are versatile so that alternative operations are possible. Branch-and-bound algorithms are developed to minimize the makespan of jobs for these problems and computational experiments are conducted to illustrate the effectiveness of these algorithms.