Document Open Access Logo

Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem

Authors Marie-Louise Lackner, Christoph Mrkvicka, Nysret Musliu, Daniel Walkiewicz, Felix Winter

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.37.pdf
  • Filesize: 0.74 MB
  • 18 pages

Document Identifiers

Author Details

Marie-Louise Lackner
  • Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, TU Wien, Austria
Christoph Mrkvicka
  • MCP GmbH, Wien, Austria
Nysret Musliu
  • Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, TU Wien, Austria
Daniel Walkiewicz
  • MCP GmbH, Wien, Austria
Felix Winter
  • Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, TU Wien, Austria

Funding

The financial support by the Austrian Federal Ministry for Digital and Economic Affairs, the National Foundation for Research, Technology and Development and the Christian Doppler Research Association is gratefully acknowledged.

Cite AsGet BibTex

Marie-Louise Lackner, Christoph Mrkvicka, Nysret Musliu, Daniel Walkiewicz, and Felix Winter. Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.37

Abstract

We introduce the Oven Scheduling Problem (OSP), a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Jobs need to be scheduled to one of several ovens and may be processed simultaneously in one batch if they have compatible requirements. The scheduling of jobs must respect several constraints concerning eligibility and availability of ovens, release dates of jobs, setup times between batches as well as oven capacities. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. This objective distinguishes the OSP from other batch processing problems which typically minimize objectives related to makespan, tardiness or lateness. We propose to solve this NP-hard scheduling problem via constraint programming (CP) and integer linear programming (ILP) and present corresponding CP- and ILP-models. For an experimental evaluation, we introduce a multi-parameter random instance generator to provide a diverse set of problem instances. Using state-of-the-art solvers, we evaluate the quality and compare the performance of our CP- and ILP-models, which could find optimal solutions for many instances. Furthermore, using our models we are able to provide upper bounds for the whole benchmark set including large-scale instances.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning and scheduling
Keywords
  • Oven Scheduling Problem
  • Parallel Batch Processing
  • Constraint Programming
  • Integer Linear Programming

Metrics

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

Supplementary Materials

References

  1. Meral Azizoglu and Scott Webster. Scheduling a batch processing machine with incompatible job families. Computers & Industrial Engineering, 39(3-4):325-335, 2001. Google Scholar
  2. Peter Brucker, Andrei Gladky, Han Hoogeveen, Mikhail Y Kovalyov, Chris N Potts, Thomas Tautenhahn, and Steef L Van De Velde. Scheduling a batching machine. Journal of scheduling, 1(1):31-54, 1998. Google Scholar
  3. Eray Cakici, Scott J Mason, John W Fowler, and H Neil Geismar. Batch scheduling on parallel machines with dynamic job arrivals and incompatible job families. International Journal of Production Research, 51(8):2462-2477, 2013. Google Scholar
  4. Bayi Cheng, Qi Wang, Shanlin Yang, and Xiaoxuan Hu. An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes. Applied Soft Computing, 13(2):765-772, 2013. Google Scholar
  5. Antonio Costa, Fulvio Antonio Cappadonna, and Sergio Fichera. A novel genetic algorithm for the hybrid flow shop scheduling with parallel batching and eligibility constraints. The International Journal of Advanced Manufacturing Technology, 75(5-8):833-847, 2014. Google Scholar
  6. Purushothaman Damodaran, Mario C Vélez-Gallego, and Jairo Maya. A grasp approach for makespan minimization on parallel batch processing machines. Journal of Intelligent Manufacturing, 22(5):767-777, 2011. Google Scholar
  7. Purushothaman Damodaran and Mario C. Vélez-Gallego. A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times. Expert Systems with Applications, 39(1):1451-1458, 2012. Google Scholar
  8. Ronald L Graham, Eugene L Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics, volume 5, pages 287-326. Elsevier, 1979. Google Scholar
  9. IBM. IBM ILOG CPLEX Optimization studio, Getting Started with Scheduling in CPLEX Studio, 2017. Google Scholar
  10. Sebastian Kosch and J Christopher Beck. A new mip model for parallel-batch scheduling with non-identical job sizes. In International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems, pages 55-70. Springer, 2014. Google Scholar
  11. Philippe Laborie, Jérôme Rogerie, Paul Shaw, and Petr Vilím. IBM ILOG CP optimizer for scheduling. Constraints, 23(2):210-250, 2018. Google Scholar
  12. Chung-Yee Lee, Reha Uzsoy, and Louis A Martin-Vega. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40(4):764-775, 1992. Google Scholar
  13. Arnaud Malapert, Christelle Guéret, and Louis-Martin Rousseau. A constraint programming approach for a batch processing problem with non-identical job sizes. European Journal of Operational Research, 221(3):533-545, 2012. Google Scholar
  14. Sujay Malve and Reha Uzsoy. A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, 34(10):3016-3028, 2007. Google Scholar
  15. Muthu Mathirajan and Appa Iyer Sivakumar. A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. The International Journal of Advanced Manufacturing Technology, 29(9-10):990-1001, 2006. Google Scholar
  16. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. MiniZinc: Towards a Standard CP Modelling Language. In Christian Bessière, editor, Principles and Practice of Constraint Programming endash CP 2007, Lecture Notes in Computer Science, pages 529-543, Berlin, Heidelberg, 2007. Springer. Google Scholar
  17. N Rafiee Parsa, Behrooz Karimi, and A Husseinzadeh Kashan. A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Computers & Operations Research, 37(10):1720-1730, 2010. Google Scholar
  18. Sergey Polyakovskiy, Dhananjay Thiruvady, and Rym M'Hallah. Just-in-time batch scheduling subject to batch size. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO '20, pages 228-235, New York, NY, USA, 2020. Association for Computing Machinery. Google Scholar
  19. Chris N. Potts and Mikhail Y. Kovalyov. Scheduling with batching: A review. European Journal of Operational Research, 120(2):228-249, 2000. Google Scholar
  20. Tanya Y. Tang and J. Christopher Beck. CP and Hybrid Models for Two-Stage Batching and Scheduling. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Lecture Notes in Computer Science, pages 431-446, 2020. Google Scholar
  21. Renan Spencer Trindade, Olinto CB de Araújo, and Marcia Fampa. Arc-flow approach for parallel batch processing machine scheduling with non-identical job sizes. In International Symposium on Combinatorial Optimization, pages 179-190. Springer, 2020. Google Scholar
  22. Reha Uzsoy. Scheduling a single batch processing machine with non-identical job sizes. The International Journal of Production Research, 32(7):1615-1635, 1994. Google Scholar
  23. Pascal Van Hentenryck. The OPL optimization programming language. MIT press, 1999. Google Scholar
  24. Mario Cesar Velez Gallego. Algorithms for scheduling parallel batch processing machines with non-identical job ready times. PhD thesis, Florida International University, 2009. Google Scholar
  25. Z. Zhao, S. Liu, M. Zhou, X. Guo, and L. Qi. Decomposition Method for New Single-Machine Scheduling Problems From Steel Production Systems. IEEE Transactions on Automation Science and Engineering, 17(3):1376-1387, 2020. Google Scholar
  26. Hongming Zhou, Jihong Pang, Ping-Kuo Chen, and Fuh-Der Chou. A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes. Computers & Industrial Engineering, 123:67-81, 2018. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact