nach oben

Journal of Scheduling

Erschienen in:

01.08.2016

Temporal linear relaxation in IBM ILOG CP Optimizer

verfasst von: Philippe Laborie, Jérôme Rogerie

Erschienen in: Journal of Scheduling | Ausgabe 4/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

IBM ILOG CP Optimizer is a constraint solver that implements a model-and-run paradigm. For scheduling problems, CP Optimizer provides a relatively simple but very expressive modeling language based on the notion of interval variables. This paper presents the temporal linear relaxation (TLR) used to guide the automatic search when solving scheduling problems that involve temporal and resource allocation costs. We give the rationale of the TLR, describe its integration in the automatic search of CP Optimizer, and present the relaxation of most of the constraints and expressions of the model. An experimental study on a set of classical scheduling benchmarks shows that using the TLR is essential for problems with irregular temporal costs and generally helps for problems with resource allocation costs.

Vorheriger Artikel Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delays

Nächster Artikel Lawler’s minmax cost algorithm: optimality conditions and uncertainty

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

It is to be noted that \(x(a)\), \(s(a)\), \(e(a)\), and \(l(a)\) are not proper decision variables of the problem, and we use them here only for the purpose of defining interval variables. In the model, interval variables are basic variables, and they are not an assembly of lower level variables. The different features of an interval variable (presence status, start, end, and length) are constrained via some expressions that we will see later (Table 1).

Subscript \(p\) stands for presence value as this is the value of the expression in case the interval variable is present.

Baptiste, P., Flamini, M., & Sourd, F. (2008). Lagrangian bounds for just-in-time job-shop scheduling. Computers and Operations Research, 35, 906–915.CrossRef

Beasley, J., Krishnamoorthy, M., Sharaiha, Y., & Abramson, D. (2000). Scheduling aircraft landings—The static case. Transportation Science, 34, 180–197.CrossRef

Beck, C., & Refalo, P. (2001). A hybrid approach to scheduling with earliness and tardiness costs. In Proceedings of the 3th international CP-AI-OR conference (CP-AI-OR 2001).

Biskup, D., & Feldmann, M. (2001). Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Computers and Operation Research, 28(8), 787–801.CrossRef

Bockmayr, A., & Pisaruk, N. (2006). Detecting infeasibility and generating cuts for mixed integer programming using constraint programming. Computers and Operations Research, 33, 2777–2786.CrossRef

Brucker, P., & Schumacher, D. (1999). A new tabu search procedure for an audit-scheduling problem. Journal of Scheduling, 2, 157–173.CrossRef

Bulbul, K., Kaminsky, P., & Yano, C. (2007). Preemption in single machine earliness/tardiness scheduling. Journal of Scheduling, 10, 271–292.CrossRef

Ciré, A., Coban, E., & Hooker, J. (2013). Mixed integer programming vs. logic-based benders decomposition for planning and scheduling. In Proceedings of the CP-AI-OR 2013.

Danna, E., & Perron, L. (2003). Structured versus unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs. In Proceedings of the 9th International CP Conference (CP 2003) (pp. 817–821).

Desaulniers, G., Desrosiers, J., & Solomon, M. (Eds.) : (2005), Column generation. New York: Springer.

Godard, D., Laborie, P., & Nuijten, W. (2005). Randomized Large Neighborhood Search for Cumulative Scheduling. In Proceedings of the ICAPS-05 (pp. 81–89).

Hooker, J. (2006). Integrated methods for optimization. Heidelberg: Springer.

Kramer, L.A., Barbulescu, L.V., & Smith, S.F. (2007). Understanding performance tradeoffs in algorithms for solving oversubscribed scheduling. In Proceedings of the 22nd AAAI conference on artificial intelligence (AAAI-07) (pp. 1019–1024).

Laborie, P., & Rogerie, J. (2008). Reasoning with conditional time-intervals. In Proceedings of the 21th international FLAIRS conference (FLAIRS 2008).

Laborie, P., Rogerie, J., Shaw, P., & Vilím, P. (2009). Reasoning with conditional time-intervals, Part II: An algebraical model for resources. In Proceedings of the 22th international FLAIRS conference (FLAIRS 2009).

Liberti, L., & Pantelides, C. C. (2003). Convex envelopes of monomials of odd degree. Journal of Global Optimization, 25, 157–168.

Morton, T., & Pentico, D. (1993). Heuristic scheduling systems. New York: Wiley.

Nuijten, W., Bousonville, T., Focacci, F., Godard, D., & Pape, C.L. (2004). Towards an industrial manufacturing scheduling problem and test bed. In Proceedings of the 9th international conference on project management and scheduling.

Policella, N., Cesta, A., Oddi, A., & Smith, S. (2004). Generating robust schedules through temporal flexibility. In Proceedings ICAPS-04, Whistler.

Policella, N., Wang, X., Smith, S., & Oddi, A. (2005). Exploiting temporal flexibility to obtain high quality schedules. In Proceedings of the AAAI-2005.

Refalo, P. (2000). Linear formulation of constraint programming models and hybrid solvers. In Proceedings of the CP-2000.

Refanidis, I. (2007). Managing personal tasks with time constraints and preferences. In Proceedings of the 17th international conference on automated planning and scheduling systems (ICAPS-07) (pp. 272–279).

el Sakkout, H., Richards, T., & Wallace, M. (1998). Minimal perturbation in dynamic scheduling. In Proceedings of the ECAI-98.

Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In Proceedings of the CP-98 (pp. 417–431).

Vanhoucke, M. (2010). A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flows. International Journal of Production Research, 48, 1983–2001.CrossRef

Vanhoucke, M., Demeulemeester, E., & Herroelen, W. (2001). An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem. Annals of Operations Research, 102(1–4), 179–196.CrossRef

Titel: Temporal linear relaxation in IBM ILOG CP Optimizer
verfasst von: Philippe Laborie
Jérôme Rogerie
Publikationsdatum: 01.08.2016
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2016
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-014-0408-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2016

Lawler’s minmax cost algorithm: optimality conditions and uncertainty

Configuration and the advantages of the shifting bottleneck procedure for optimizing the job shop total weighted tardiness scheduling problem

Scheduling evacuation operations

Late acceptance hill-climbing for high school timetabling

A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations

A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing