Search Results

Documents authored by Lackner, Marie-Louise

Document
DOI: 10.4230/LIPIcs.CP.2021.37
Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem

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

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2021.37},
  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}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.2
Latticepathology and Symmetric Functions (Extended Abstract)

Authors: Cyril Banderier, Marie-Louise Lackner, and Michael Wallner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
In this article, we revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener - Hopf formulas, thus capturing joint distributions. We also show that each of the fundamental families of symmetric polynomials corresponds to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Cite as

Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2020.2,
  author =	{Banderier, Cyril and Lackner, Marie-Louise and Wallner, Michael},
  title =	{{Latticepathology and Symmetric Functions (Extended Abstract)}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.2},
  URN =		{urn:nbn:de:0030-drops-120329},
  doi =		{10.4230/LIPIcs.AofA.2020.2},
  annote =	{Keywords: Lattice path, generating function, symmetric function, algebraic function, kernel method, context-free grammar, Sparre Andersen formula, Spitzer’s identity, Wiener - Hopf factorization}
}
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