Utilizing Constraint Optimization for Industrial Machine Workload Balancing

Authors Benjamin Kovács, Pierre Tassel, Wolfgang Kohlenbrein, Philipp Schrott-Kostwein, Martin Gebser



PDF
Thumbnail PDF

File

LIPIcs.CP.2021.36.pdf
  • Filesize: 0.84 MB
  • 17 pages

Document Identifiers

Author Details

Benjamin Kovács
  • Universität Klagenfurt, Austria
Pierre Tassel
  • Universität Klagenfurt, Austria
Wolfgang Kohlenbrein
  • Kostwein Holding GmbH, Klagenfurt, Austria
Philipp Schrott-Kostwein
  • Kostwein Holding GmbH, Klagenfurt, Austria
Martin Gebser
  • Universität Klagenfurt, Austria
  • Technische Universität Graz, Austria

Cite AsGet BibTex

Benjamin Kovács, Pierre Tassel, Wolfgang Kohlenbrein, Philipp Schrott-Kostwein, and Martin Gebser. Utilizing Constraint Optimization for Industrial Machine Workload Balancing. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.36

Abstract

Efficient production scheduling is an important application area of constraint-based optimization techniques. Problem domains like flow- and job-shop scheduling have been extensive study targets, and solving approaches range from complete and local search to machine learning methods. In this paper, we devise and compare constraint-based optimization techniques for scheduling specialized manufacturing processes in the build-to-print business. The goal is to allocate production equipment such that customer orders are completed in time as good as possible, while respecting machine capacities and minimizing extra shifts required to resolve bottlenecks. To this end, we furnish several approaches for scheduling pending production tasks to one or more workdays for performing them. First, we propose a greedy custom algorithm that allows for quickly screening the effects of altering resource demands and availabilities. Moreover, we take advantage of such greedy solutions to parameterize and warm-start the optimization performed by integer linear programming (ILP) and constraint programming (CP) solvers on corresponding problem formulations. Our empirical evaluation is based on production data by Kostwein Holding GmbH, a worldwide supplier in the build-to-print business, and thus demonstrates the industrial applicability of our scheduling methods. We also present a user-friendly web interface for feeding the underlying solvers with customer order and equipment data, graphically displaying computed schedules, and facilitating the investigation of changed resource demands and availabilities, e.g., due to updating orders or including extra shifts.

Subject Classification

ACM Subject Classification
  • Applied computing → Command and control
Keywords
  • application
  • production planning
  • production scheduling
  • linear programming
  • constraint programming
  • greedy algorithm
  • benchmarking

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Edward Anderson. A review of duality theory for linear programming over topological vector spaces. Journal of Mathematical Analysis and Applications, 97(2):380-392, 1983. URL: https://doi.org/10.1016/0022-247X(83)90204-4.
  2. Francisco Ballestín, Vicente Valls, and Sacramento Quintanilla. Due dates and RCPSP. In Joanna Józefowska and Jan Weglarz, editors, Perspectives in Modern Project Scheduling, volume 92 of International Series in Operations Research & Management Science, pages 79-104. Springer, 2006. URL: https://doi.org/10.1007/978-0-387-33768-5_4.
  3. Philippe Baptiste, Claude Le Pape, and Wim Nuijten. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, volume 39 of International Series in Operations Research & Management Science. Springer, 2001. URL: https://doi.org/10.1007/978-1-4615-1479-4.
  4. Michel Bénichou, Jean-Michel Gauthier, Paul Girodet, Gerard Hentges, Gerard Ribière, and O. Vincent. Experiments in mixed-integer linear programming. Mathematical Programming, 1(1):76-94, 1971. URL: https://doi.org/10.1007/BF01584074.
  5. Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors. Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2009. URL: https://doi.org/10.3233/978-1-58603-929-5-3.
  6. Jan Böttcher, Andreas Drexl, Rainer Kolisch, and Frank Salewski. Project scheduling under partially renewable resource constraints. Management Science, 45(4):543-559, 1999. URL: https://doi.org/10.1287/mnsc.45.4.543.
  7. Jacques Carlier and Éric Pinson. An algorithm for solving the job-shop problem. Management Science, 35(2):164-176, 1989. URL: https://doi.org/10.1287/mnsc.35.2.164.
  8. Ripon Chakrabortty, Ruhul Sarker, and Daryl Essam. Single mode resource constrained project scheduling with unreliable resources. Operational Research, 20(3):1-35, 2020. URL: https://doi.org/10.1007/s12351-018-0380-7.
  9. Giacomo Da Col and Erich Teppan. Industrial size job shop scheduling tackled by present day CP solvers. In Thomas Schiex and Simon de Givry, editors, Proceedings of the Twenty-fifth International Conference on Principles and Practice of Constraint Programming (CP'19), volume 11802 of Lecture Notes in Computer Science, pages 144-160. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-30048-7_9.
  10. Laure Drezet and Jean-Charles Billaut. A project scheduling problem with labour constraints and time-dependent activities requirements. International Journal of Production Economics, 112(1):217-225, 2008. URL: https://doi.org/10.1016/j.ijpe.2006.08.021.
  11. Jianzhong Du and Joseph Leung. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15(3):483-495, 1990. URL: https://doi.org/10.1287/moor.15.3.483.
  12. Steven Gay, Renaud Hartert, and Pierre Schaus. Simple and scalable time-table filtering for the cumulative constraint. In Gilles Pesant, editor, Proceedings of the Twenty-first International Conference on Principles and Practice of Constraint Programming (CP'15), volume 9255 of Lecture Notes in Computer Science, pages 149-157. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-23219-5_11.
  13. Iiro Harjunkoski. Deploying scheduling solutions in an industrial environment. Computers & Chemical Engineering, 91:127-135, 2016. URL: https://doi.org/10.1016/j.compchemeng.2016.03.029.
  14. Iiro Harjunkoski, Christos Maravelias, Peter Bongers, Pedro Castro, Sebastian Engell, Ignacio Grossmann, John Hooker, Carlos Méndez, Guido Sand, and John Wassick. Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering, 62:161-193, 2014. URL: https://doi.org/10.1016/j.compchemeng.2013.12.001.
  15. Sönke Hartmann and Dirk Briskorn. A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1):1-14, 2010. URL: https://doi.org/10.1016/j.ejor.2009.11.005.
  16. Oliver Holthaus. Efficient dispatching rules for scheduling in a job shop. International Journal of Production Economics, 48(1):87-105, 1997. URL: https://doi.org/10.1016/S0925-5273(96)00068-0.
  17. Vladimir Lifschitz. Answer Set Programming. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24658-7.
  18. Leilei Meng, Chaoyong Zhang, Yaping Ren, Biao Zhang, and Chang Lv. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Computers & Industrial Engineering, 142:Article ID 106347, 2020. URL: https://doi.org/10.1016/j.cie.2020.106347.
  19. Muhammad Nawaz, Emory Enscore, and Inyong Ham. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1):91-95, 1983. URL: https://doi.org/10.1016/0305-0483(83)90088-9.
  20. Klaus Neumann and Christoph Schwindt. Project scheduling with inventory constraints. Mathematical Methods of Operations Research, 56:513-533, 2003. URL: https://doi.org/10.1007/s001860200251.
  21. Yves Pochet and Laurence Wolsey. Production Planning by Mixed Integer Programming. Springer, 2010. URL: https://doi.org/10.1007/0-387-33477-7.
  22. Francesca Rossi, Peter van Beek, and Toby Walsh, editors. Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence. Elsevier, 2006. URL: https://doi.org/10.5555/2843512.
  23. Yuri Sotskov and Natalia Shakhlevich. NP-hardness of shop-scheduling problems with three jobs. Discrete Applied Mathematics, 59(3):237-266, 1995. URL: https://doi.org/10.1016/0166-218X(95)80004-N.
  24. Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278-285, 1993. URL: https://doi.org/10.1016/0377-2217(93)90182-M.
  25. Bernd Waschneck, André Reichstaller, Lenz Belzner, Thomas Altenmüller, Thomas Bauernhansl, Alexander Knapp, and Andreas Kyek. Optimization of global production scheduling with deep reinforcement learning. Procedia CIRP, 72:1264-1269, 2018. URL: https://doi.org/10.1016/j.procir.2018.03.212.
  26. Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. Journal of Machine Learning Research, 15(1):949-980, 2014. URL: http://dl.acm.org/citation.cfm?id=2638566.
  27. Fatos Xhafa and Ajith Abraham, editors. Metaheuristics for Scheduling in Industrial and Manufacturing Applications, volume 128 of Studies in Computational Intelligence. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-78985-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail