A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions

References

• Blazewicz , J. , Ecker , K. H. , Pesch , E. , Schmidt , G. and Weglarz , J. 2007 . “ Scheduling under resource constraints ” . In Handbook on scheduling: From theory to applications , 425 – 475 . New York/Berlin/Heidelberg : Springer-Verlag .
   Google Scholar
• Bosch , R. and Trick , M. 2004 . Constraint programming and hybrid formulations for three life designs . Annals of Operations Research , 130 ( 1–4 ) : 41 – 56 .
   Web of Science ®Google Scholar
• Bourland , K. E. and Carl , L. K. 1994 . Parallel machine scheduling with fractional operator requirements . IIE Transactions , 26 ( 5 ) : 56 – 65 .
   Web of Science ®Google Scholar
• Chen , J.-F. 2005 . Unrelated parallel machine scheduling with secondary resource constraints . International Journal of Advanced Manufacturing Technology , 26 : 285 – 292 .
   Web of Science ®Google Scholar
• Chen , J.-F. and Wu , T.-H. 2006 . Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints . Omega – International Journal of Management Science , 34 : 81 – 89 .
   Web of Science ®Google Scholar
• Chu , Y. and Xia , Q. A hybrid algorithm for a class of resource-constrained scheduling problems . Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 2nd international conference (CPAIOR’2005). 30 May – 1 June , Prague, Czech Republic. pp. 110 – 124 . Berlin/Heidelberg : Springer-Verlag . Lecture Notes in Computer Science 3524
   Google Scholar
• Daniels , R. L. , Hoopes , B. J. and Mazzola , J. B. 1996 . Scheduling parallel manufacturing cells with resource flexibility . Management Science , 42 ( 9 ) : 1260 – 1276 .
   Web of Science ®Google Scholar
• Daniels , R. L. , Hoopes , B. J. and Mazzola , J. B. 1997 . An analysis of heuristics for the parallel-machine flexible-resource scheduling problem . Annals of Operations Research , 70 : 439 – 472 .
   Web of Science ®Google Scholar
• Daniels , R. L. , Hua , S. Y. and Webster , S. 1999 . Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment . Computers & Operations Research , 26 : 143 – 155 .
   Web of Science ®Google Scholar
• Darbi-Dowman , K. D. , Little , J. , Mitra , G. and Zaffalon , M. 1997 . Constraint logic programming and integer programming approaches and their collaboration in solving an assignment scheduling problem . Constraints , 1 : 245 – 264 .
   Google Scholar
• Darbi-Dowman , K. D. and Little , J. 1998 . Properties of some combinatorial optimization problems and their effect on the performance of integer programming and constraint logic programming . Informs Journal on Computing , 10 ( 3 ) : 276 – 286 .
   Google Scholar
• Edis , E. B. and Ozkarahan , I. Parallel machine scheduling with additional resources: A brief review of the literature . 11th IFAC international symposium CEFIS’2007 . October 9–11 , Istanbul. pp. 381 – 386 . Istanbul : Dogus University .
   Google Scholar
• Edis , E. B. , Araz , C. and Ozkarahan , I. Lagrangian-based solution approaches for a resource-constrained parallel machine scheduling problem with machine eligibility restrictions . The 21st international conference on industrial, engineering and other applications of applied intelligent systems (IEA/AIE 2008) . June 18–20 , Wroclaw, Poland. pp. 337 – 346 . Berlin/Heidelberg : Springer-Verlag . Lecture Notes in Artificial Intelligence 5027
   Google Scholar
• Focacci , F. , Lodi , A. and Milano , M. 2002 . Mathematical programming techniques in constraint programming: A short overview . Journal of Heuristics , 8 : 7 – 17 .
   Google Scholar
• Gao , L. , Wang , C. , Wang , D. , Yin , Z. and Wang , S. 1998 . A production scheduling system for parallel machines in an electrical appliance plant . Computers & Industrial Engineering , 35 ( 1–2 ) : 105 – 108 .
   Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . Computers and intractability: A guide to the theory of NP-completeness , New York : W.H. Freeman .
   Google Scholar
• Grigoriev , A. , Sviridenko , M. and Uetz , M. 2007 . Machine scheduling with resource dependent processing times . Mathematical Programming, Series B , 110 : 209 – 228 .
   Web of Science ®Google Scholar
• Grigoriev , A. and Uetz , M. 2009 . Scheduling jobs with time-resource trade-off via non-linear programming . Discrete Optimization , 6 : 414 – 419 .
   Google Scholar
• Heipcke , S. 1999 . Comparing constraint programming and mathematical programming approaches to discrete optimization – the change problem . Journal of Operational Research Society , 50 : 581 – 595 .
   Google Scholar
• Hooker , J. N. 2000 . Logic-based methods for optimization: Combining optimization and constraint satisfaction , USA : Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons .
   Google Scholar
• Hooker , J. N. 2002 . Logic, optimization and constraint programming . INFORMS Journal on Computing , 14 : 295 – 321 .
   Google Scholar
• Hooker , J. N. 2005 . A hybrid method for planning and scheduling . Constraints , 10 : 385 – 401 .
   Web of Science ®Google Scholar
• Hooker , J. N. 2006 . An integrated method for planning and scheduling to minimize tardiness . Constraints , 11 : 139 – 157 .
   Google Scholar
• ILOG . 2003 . OPL Studio 3.7™ language manual , France : ILOG S.A .
   Google Scholar
• ILOG . 2005a . CPLEX 9.0™ user's manual , France : ILOG S.A .
   Google Scholar
• ILOG . 2005b . ILOG Solver 6.0™ user's manual , France : ILOG S.A .
   Google Scholar
• ILOG . 2005c . ILOG Scheduler 6.0™ user's manual , France : ILOG S.A .
   Google Scholar
• Jain , V. and Grossmann , I. E. 2001 . Algorithms for hybrid MILP/CP models for a class of optimization problems . Informs Journal on Computing , 13 : 258 – 276 .
   Web of Science ®Google Scholar
• Kellerer , H. 2008 . An approximation algorithm for identical parallel machine scheduling with resource dependent processing times . Operations Research Letters , 36 : 157 – 159 .
   Web of Science ®Google Scholar
• Kellerer , H. and Strusevisch , V. A. 2004 . Scheduling problems for parallel dedicated machines under multiple resource constraints . Discrete Applied Mathematics , 133 : 45 – 68 .
   Web of Science ®Google Scholar
• Kellerer , H. and Strusevisch , V. A. 2008 . Scheduling parallel dedicated machines with the speeding–up resource . Naval Research Logistics, , 55 ( 5 ) : 377 – 389 .
   Web of Science ®Google Scholar
• Kumar , V. S.A. , Marathe , M. V. , Parthasarathy , S. and Srinivasan , A. Approximation algorithms for scheduling on multiple machines . Proceedings of the 46th annual IEEE symposium on foundations of computer science . October 23–25 , Pittsburg, PA. pp. 254 – 263 . Washington D.C : IEEE Computer Society .
   Google Scholar
• Li , Y. , Wang , F. and Lim , A. Resource constraints machine scheduling: A genetic algorithm approach . 2003 congress on evolutionary computation . December 9–12 , Canberra, Australia. Vol. 2 , pp. 1080 – 1085 . New Jersey : IEEE Press .
   Google Scholar
• Lin , C. K.Y. , Wong , C. L. and Yeung , Y. C. 2002 . Heuristic approaches for a scheduling problem in the plastic moulding department of an audio company . Journal of Heuristics , 8 : 515 – 540 .
   Google Scholar
• Lustig , I. J. and Puget , J. F. 2001 . Program does not equal program: Constraint programming and its relationship to mathematical programming . Interfaces , 31 ( 6 ) : 29 – 53 .
   Google Scholar
• Magatao , L. 2005 . “ Mixed integer linear programming and constraint logic programming: A unified modeling framework ” . Brazil : The Federal Center of Technological Education of Parana . Thesis (PhD)
   Google Scholar
• Milano , M. 2004 . Constraint and integer programming: Toward a unified methodology , Edited by: Milano , M. USA : Kluwer Academic Publishers .
   Google Scholar
• Milano , M. and Trick , M. 2004 . “ Constraint and integer programming ” . In Constraint and integer programming: Toward a unified methodology , Edited by: Milano , M. 1 – 31 . USA : Kluwer Academic Publishers .
   Google Scholar
• Milano , M. and Wallace , M. 2006 . Integrating operations research in constraint programming . 4OR , 4 : 175 – 219 .
   Google Scholar
• Nagarur , N. , Vrat , P. and Duongsuwan , W. 1997 . Production planning and scheduling for injection moulding of pipe fittings. A case study . International Journal of Production Economics , 53 : 157 – 170 .
   Google Scholar
• Pinedo , M. 1995 . Scheduling theory: Algorithms and systems , New Jersey : Prentice Hall .
   Google Scholar
• Pinto , J. M. and Grossman , I. E. 1997 . A logic-based approach to scheduling problems with resource constraints . Computers and Chemical Engineering , 21 ( 8 ) : 801 – 818 .
   Google Scholar
• Rodosek , R. , Wallace , M. G. and Hajian , M. T. 1999 . A new approach to integrating mixed integer programming and constraint logic programming . Annals of Operations Research , 86 : 63 – 87 .
   Web of Science ®Google Scholar
• Ruiz-Torres , A. J. and Centeno , G. 2007 . Scheduling with flexible resources in parallel workcenters to minimize maximum completion time . Computers & Operations Research , 34 : 48 – 69 .
   Web of Science ®Google Scholar
• Ruiz-Torres , A. J. , Lopez , F. J. and Ho , J. C. 2007 . Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs . European Journal of Operational Research , 179 ( 2 ) : 302 – 315 .
   Web of Science ®Google Scholar
• Smith , B. M. , Brailsford , S. C. , Hubbard , P. M. and Williams , H. P. 1997 . The progressive party problem: Integer linear programming and constraint programming compared . Constraints , 1 : 119 – 138 .
   Google Scholar
• Sue , L.-H. and Lien , C.-Y. 2009 . Scheduling parallel machines with resource-dependent processing times . International Journal of Production Economics , 117 : 256 – 266 .
   Google Scholar
• Tamaki , H. , Hasegawa , Y. , Kozasa , J. and Araki , M. Application of search methods to scheduling problem in plastics forming plant: A binary representation approach . 32nd conference on decision and control . December 15–17 , San Antonio, Texas, USA. pp. 3845 – 3850 . New Jersey : IEEE Press .
   Google Scholar
• Thorsteinsson , E. S. Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming . Principles and practice of constraint programming . 26 November–1 December , Paphos, Cyprus. pp. 16 – 30 . Berlin/Heidelberg : Springer-Verlag . Lecture Notes in Computer Science 2239
   Google Scholar
• Thorsteinsson , E. S. 2001b . Hybrid approaches to combinatorial optimisation , Carnegie Mellon University . Thesis (PhD)
   Google Scholar
• Topaloglu , S. and Ozkarahan , I. Comparison of different variable and value order strategies for the optimum solution of a single machine scheduling problem with sequence-dependent setups . Computer and information sciences – ISCIS 2004 . October 27–29 , Antalya, Turkey. Edited by: Aykanat , C. , Dayar , T. and Körpeoglu , I. pp. 996 – 1005 . Berlin/Heidelberg : Springer-Verlag . Lecture Notes in Computer Science 3280
   Google Scholar
• Vairaktarakis , G. L. and Cai , X. The value of processing flexibility in multipurpose machines . IIE transactions , 35 763 – 774 .
   Google Scholar
• Van den Akker , J. M , Hurkens , C. A.J. and Savelsbergh , M. W.P. 2000 . Time-indexed formulations for machine scheduling problems: Column generation . Informs Journal on Computing , 12 ( 2 ) : 111 – 124 .
   Web of Science ®Google Scholar
• Van Hentenryck , P. 1999 . The OPL™ optimization programming language , Cambridge, MA : MIT Press .
   Google Scholar
• Van Hentenryck , P. , Perron , L. and Puget , J.-F. 2000 . Search and strategies in OPL . ACM Transactions on Computational Logic (TOCL) , 1 ( 2 ) : 285 – 320 .
   Google Scholar
• Ventura , J. A. and Kim , D. 2003 . Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints . Computers & Operations Research , 30 : 1945 – 1958 .
   Web of Science ®Google Scholar
• Wallace , M. , Novello , S. and Schimpf , J. 1997 . ECLIPSe: A platform for constraint logic programming . ICL Systems Journal , 12 : 159 – 120 .
   Google Scholar