An exact method for the bi-objective one-machine problem with maximum lateness and unit family setup cost objectives

This paper deals with an NP-hard bi-objective one-machine problem with ready times involving maximum lateness and unit family setup cost objectives. Considering separately both objectives, the maximum lateness one-machine problem is also NP-hard but efficiently solved by Carlierʹs algorithm while the unit family setup cost one machine-problem with two families can be solved in polynomial timeby Darteʹs algorithm, even when precedence constraints are considered. Under the ϵ-constraint framework we propose a branch-and-bound method to minimize the first objective with a given upper bound on the second.