Two-machine flow shop scheduling with two criteria: Maximum earliness and makespan

In this study we address the problem of minimizing makespan and maximum earliness simultaneously in a two-machine flow shop environment. We develop a branch-and-bound procedure that generates all efficient solutions with respect to two criteria. We propose several lower and upper bounding schemes to enhance the efficiency of the algorithm. We also propose a heuristic procedure that generates approximate efficient solutions. Our computational results reveal that the branch-and-bound procedure is capable of solving problems with up to 25 jobs and the heuristic procedure produces approximate efficient solutions that are very close to exact efficient solutions in very small computation times.