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

作者：Della Croce Federico^*; Koulamas Christos; T'kindt Vincent

来源：European Journal of Operational Research, 2017, 259(3): 898-905.

DOI：10.1016/j.ejor.2016.11.036

• Scheduling
• Jobs selection
• Two-machine shop problems
• Constraint generation approach

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 100000 jobs.

• 出版日期2017-6-16