License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.37
URN: urn:nbn:de:0030-drops-153286
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15328/
Go to the corresponding LIPIcs Volume Portal

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

Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem

pdf-format:
LIPIcs-CP-2021-37.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{lackner_et_al:LIPIcs.CP.2021.37,
  author =	{Lackner, Marie-Louise and Mrkvicka, Christoph and Musliu, Nysret and Walkiewicz, Daniel and Winter, Felix},
  title =	{{Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15328},
  URN =		{urn:nbn:de:0030-drops-153286},
  doi =		{10.4230/LIPIcs.CP.2021.37},
  annote =	{Keywords: Oven Scheduling Problem, Parallel Batch Processing, Constraint Programming, Integer Linear Programming}
}

Keywords: Oven Scheduling Problem, Parallel Batch Processing, Constraint Programming, Integer Linear Programming
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021
Supplementary Material: Software (Source Code, Benchmark Set, and Results): https://cdlab-artis.dbai.tuwien.ac.at/papers/ovenscheduling/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI