Search Results

Documents authored by Teppan, Erich

Document
Extended Abstract
DOI: 10.4230/OASIcs.DX.2024.33
Summary of "Randomized Problem-Relaxation Solving for Over-Constrained Schedules" (Extended Abstract)

Authors: Patrick Rodler, Erich Teppan, and Dietmar Jannach

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
We present a general framework for tackling over-constrained job shop scheduling problems (JSSP) where the volume of jobs (orders) exceeds the production capacity for a given planning horizon. The goal is to process as many or as utile jobs as possible within the available time. The suggested framework approaches this optimization problem by solving multiple randomly modified relaxed problem instances, thereby taking a sample in a solution space that covers all optimal solutions. By continuously storing the best solution found so far, the result is a complete anytime algorithm that incrementally approximates an optimal solution. The proposed framework allows for highly parallel computations, and all of its modules are treated as black-boxes, allowing them to be instantiated with the most performant algorithms for the respective sub-problems. Using IBM’s cutting-edge CP Optimizer suite, experiments on well-known JSSP benchmark problems demonstrate that the proposed framework consistently schedules more jobs in less computation time compared to a standalone constraint solver approach. Due to the generality of the proposed approach and its applicability to computing minimum-cardinality or most preferred minimal diagnoses, this work has the potential to positively impact the field of model-based diagnosis.
Cite as

Patrick Rodler, Erich Teppan, and Dietmar Jannach. Summary of "Randomized Problem-Relaxation Solving for Over-Constrained Schedules" (Extended Abstract). In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 33:1-33:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rodler_et_al:OASIcs.DX.2024.33,
  author =	{Rodler, Patrick and Teppan, Erich and Jannach, Dietmar},
  title =	{{Summary of "Randomized Problem-Relaxation Solving for Over-Constrained Schedules"}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{33:1--33:4},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.33},
  URN =		{urn:nbn:de:0030-drops-221259},
  doi =		{10.4230/OASIcs.DX.2024.33},
  annote =	{Keywords: diagnosis computation, randomized diagnosis computation, minimum-cardinality diagnoses, most preferred diagnoses, maximum-probability diagnoses, applications of diagnosis (over-constrained scheduling problems), diagnosis-based optimization, constraint programming, CP Optimizer, job shop scheduling problem, job set optimization problem, operations research, scheduling, industry use cases, minimal subset subject to a monotone predicate (MSMP) problem, problem relaxation, sampling for optimization, anytime algorithm}
}
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 About DROPS Imprint Privacy Contact