Paper Info
Title
A constraint programming approach for a batch processing problem with non-identical job sizes.
Abstract
This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price. (c) 2012 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2012
10.1016/j.ejor.2012.04.008
European Journal of Operational Research
Keywords
Field
DocType
Combinatorial optimization,Artificial intelligence,Constraint programming,Scheduling,Packing
Constraint satisfaction,Mathematical optimization,Computer science,Constraint programming,Filter (signal processing),Algorithm,Combinatorial optimization,Concurrent constraint logic programming,Batch processing,Constraint logic programming,Operations management,Binary constraint
Journal
Volume
Issue
ISSN
221
3
0377-2217
Citations 
PageRank 
References 
17
0.72
15
Authors
3
Name
Order
Citations
PageRank
Arnaud Malapert1314.50
C. Guéret241518.12
Louis-Martin Rousseau388863.71