Minimizing total flow time in a two-machine flowshop problem with minimum makespan

This paper considers the two-machine flowshop scheduling problem where it is desired to find a minimum total flow time schedule subject to the condition that the makespan of the schedule is minimum. Based on the analysis of the problem characteristics, several existing results are extended to develop two optimization algorithms for the problem. In view of the NP-hardness of the problem, two polynomially solvable cases are identified and solved. Further, several polynomial heuristic solution algorithms are developed and empirically evaluated as to their effectiveness in finding an optimal schedule for the problem. (C) 2001 Elsevier Science B.V. All rights reserved.