The Tricriteria Two-Machine Flowshop Scheduling Problem

The literature on the two-machine flowshop scheduling problem reveals that the problem has been addressed with bicriteria of either makespan and mean flowtime or makespan and maximum tardiness (lateness). This paper extends the problem to all the three criteria (tricriteria) where the objective is to minimize a weighted sum of makespan, mean flowtime, and maximum lateness. A dominance relation and a lower bound are established. The dominance relation and the lower bound are used to develop a branch-and-bound algorithm. The dominance relation is also used to develop several heuristics. An extensive computational analysis is conducted to evaluate the performance of the dominance relation and the heuristics. The analysis shows that the dominance relation is effective. The analysis also shows that the heuristics are quite efficient, and some heuristics have an error of less than 1%. Moreover, these heuristics have the desirable property that the error does not increase by the number of jobs.