×

zbMATH — the first resource for mathematics

An integrated method for planning and scheduling to minimize tardiness. (English) Zbl 1103.68811
Summary: We combine Mixed Integer Linear Programming (MILP) and Constraint Programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CP. We also obtain much better solutions for problems that cannot be solved to optimality.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238–252. · Zbl 0109.38302
[2] Cambazard, H., Hladik, P.-E., Déplanche, A.-M., Jussien, N., & Trinquet, Y. (2004). Decomposition and learning for a hard real time task allocation problem. In M. Wallace (Ed.), Principles and practice of constraint programming (CP2004), Volume 3258 of Lecture Notes in Computer Science (pp. 153–167). Berlin Heidelberg New York: Springer. · Zbl 1152.68545
[3] Chu, Y., & Xia, Q. (2004). Generating benders cuts for a class of integer programming problems. In J. C. Régin & M. Rueher (Eds.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR 2004), volume 3011 of Lecture Notes in Computer Science (pp. 127–141). Berlin Heidelberg New York: Springer. · Zbl 1094.90578
[4] Corréa, A. I., Langevin, A., & Rousseau, L. M. (2004). Dispatching and conflict-free routing of automated guided vehicles: A hybrid approach combining constraint programming and mixed integer programming. In J. C. Régin & M. Rueher (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2004), volume 3011 of Lecture Notes in Computer Science (pp. 370–378). Berlin Heidelberg New York: Springer. · Zbl 1094.90519
[5] Eremin, A., & Wallace, M. (2001). Hybrid Benders decomposition algorithm in constraint logic programming. In T. Walsh (Ed.), Principles and practice of constraint programming (CP2001), volume 2239 of Lecture Notes in Computer Science (pp. 1–15). Berlin Heidelberg New York: Springer. · Zbl 1067.68630
[6] Geoffrion, A. M. (1972) Generalized benders decomposition. Journal of Optimization Theory and Applications, 10, 237–260. · Zbl 0229.90024
[7] Harjunkoski, I., & Grossmann, I. E. (2001). A decomposition approach for the scheduling of a steel plant production. Computers and Chemical Engineering, 25, 1647–1660.
[8] Hooker, J. N. (2000). Logic-based methods for optimization: combining optimization and Constraint Satisfaction. New York: Wiley. · Zbl 0974.90001
[9] Hooker, J. N. (2004). A hybrid method for planning and scheduling. In M. Wallace (Ed.), Principles and practice of constraint programming (CP2004), volume 3258 of Lecture Notes in Computer Science (pp. 305–316). Berlin Heidelberg New York: Springer. · Zbl 1152.90445
[10] Hooker, J. N. (2005). A hybrid method for planning and scheduling. Constraints, 10, 385–401. · Zbl 1122.90054
[11] Hooker, J. N. (2005). Planning and scheduling to minimize tardiness. In Principles and practice of constraint programming (CP2005), Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer. · Zbl 1153.90423
[12] Hooker, J. N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96, 33–60. · Zbl 1023.90082
[13] Hooker, J. N., & Yan, H. (1995). Logic circuit verification by benders decomposition. In V. Saraswat & P. Van Hentenryck (Eds.), Principles and practice of constraint programming: The Newport Papers (pp. 267–288). Cambridge, Massachusetts: MIT.
[14] Hooker, J. N., & Yan, H. (2002). A relaxation for the cumulative constraint. In P. Van Hentenryck (Ed.), Principles and practice of constraint programming, volume 2470 of Lecture Notes in Computer Science (pp. 686–690). Berlin Heidelberg New York: Springer.
[15] Jain, V., & Grossmann, I. E. (2001). Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS Journal on Computing, 13, 258–276. · Zbl 1238.90106
[16] Maravelias, C. T., & Grossmann, I. E. (2004). Using MILP and CP for the scheduling of batch chemical processes. In J. C. Régin & M. Rueher (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization problems (CPAIOR 2004), volume 3011 of Lecture Notes in Computer Science (pp. 1–20). Berlin Heidelberg New York: Springer. · Zbl 1094.90559
[17] Thorsteinsson, E. (2001). Branch and check: A hybrid framework integrating mixed integer programming and constraint logic programming. In T. Walsh (Ed.), Principles and practice of constraint programming (CP2001), volume 2239 of Lecture Notes in Computer Science (pp. 16–30). Berlin Heidelberg New York: Springer. · Zbl 1067.68677
[18] Timpe, C. (2002). Solving planning and scheduling problems with combined integer and constraint programming. OR Spectrum, 24, 431–448. · Zbl 1028.90017
[19] Türkay, M., & Grossmann, I. E.(1996). Logic-based MINLP algorithms for the optimal synthesis of process networks. Computers and Chemical Engineering, 20, 959–978.
[20] Xia, Q., Eremin, A., & Wallace, M. (2004). Problem decomposition for traffic diversions. In J. C. Régin & M. Rueher (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2004), volume 3011 of Lecture Notes in Computer Science (pp. 348–363). Berlin Heidelberg New York: Springer. · Zbl 1094.90515
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.