A constraint generation approach for two-machine shop problems with jobs selection

We consider job selection problems in two-stage flow shops and job shops. The aim is to select the best job subset with a given cardinality to minimize the makespan. These problems are known to be ordinary NP-hard and the current state of the art algorithms can solve flow shop problems with up to 3000 jobs. We introduce a constraint generation approach to the integer linear programming (ILP) formulation of these problems according to which the constraints associated with nearly all potential critical paths are relaxed and then only the ones violated by the relaxed solution are sequentially reinstated. The proposed approach is capable of solving problems with up to 100 000 jobs.