Scheduling of three-operation jobs in a two-machine flowshop with mean flowtime measure

Abstract

This paper considers a two-machine flowshop scheduling problem for minimizing mean flowtime. Each job has three non-preemptive operations, where the first and third operations must be processed on the first and second machines, respectively, but the second operation is allowed to be processed on either machine. A lower bound based on SPT rule is derived, which is then used to develop a branch-and-bound algorithm. Also, an efficient simple heuristic algorithm is developed to generate a near-optimal schedule. Numerical experiments are conducted to evaluate the performances of the proposed branch-and-bound and the heuristic algorithm.