Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959740 | European Journal of Operational Research | 2017 | 8 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Federico Della Croce, Christos Koulamas, Vincent T'kindt,