2026-09-18T02:36:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24262 2026-09-05T18:40:12Z ddc:004 open_access

Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis Grüttemeier, Niels Heeger, Klaus Job shop parallel machines reactive scheduling We consider the problem of repairing production schedules in a job-shop setting by reducing pre-planned waiting times. Herein, a schedule of all jobs is given. To compensate unforeseen disturbances, this schedule contains waiting times between the execution of two consecutive tasks of a job. Further, we assume that the schedule temporarily overloads some machines, e.g. due to reduced machine capacities because of worker sickness or (partially) broken machines. We study the problem of removing as few waiting times as possible in order to eliminate the machine overloads. After formalizing this problem, we perform an extensive analysis of its parameterized complexity with respect to several natural parameters, resulting in a detailed picture of the problem’s complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niels Grüttemeier and Klaus Heeger 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.31 urn:nbn:de:0030-drops-242624 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.31 eng https://creativecommons.org/licenses/by/4.0/legalcode