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

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