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 NP-hard and the current state of the art algorithms can solve instances with up to 3000 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 axe 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 100000 jobs or more.
展开▼
