A constraint generation approach for the two-machine flow shop problem with jobs selection Conference

Della Croce, F, Koulamas, C, T'Kindt, V. (2014). A constraint generation approach for the two-machine flow shop problem with jobs selection . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 8596 LNCS 198-207. 10.1007/978-3-319-09174-7_17

cited authors

  • Della Croce, F; Koulamas, C; T'Kindt, V

authors

abstract

  • We consider a job selection problem in a two-stage flow shop. The objective is to select the best job subset with a given cardinality to minimize the makespan. This problem is known to be ordinary -hard and the current state of the art algorithms can solve instances with up to jobs. We introduce a constraint generation approach to the integer linear programming (ILP) formulation of the problem 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. This approach yields a new solution algorithm capable of solving problems with up to jobs or more. © 2014 Springer International Publishing.

publication date

  • January 1, 2014

published in

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 13

start page

  • 198

end page

  • 207

volume

  • 8596 LNCS