Precedence-Constrained Scheduling Problems Parameterized by Partial Order WidthReport as inadecuate




Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width - Download this document for free, or read online. Document in PDF available to download.

1 SWT - TUB - Department of Software Engineering and Theoretical Computer Science 2 LIGM - Laboratoire d-Informatique Gaspard-Monge 3 Institut für Softwaretechnik und Theoretische Informatik EECS-TUB 4 Department of mathematics and computing science Eindhoven

Abstract : Negatively answering a question posed by Mnich and Wiese Math. Program. 1541–2:533–562, we show that P2|prec,pj∈{1, 2}|Cmax, the problem of finding a non-preemptive minimum-makespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W2-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of k other given words, is W2-hard param-eterized by k, thus additionally answering a question posed by Rizzi and Vialette CSR 2013. Finally, refining a geometric algorithm due to Servakh Diskretn. Anal. Issled. Oper. 71:75–82, we show that the more general Resource-Constraint Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job.

Keywords : resource-constrained project scheduling parallel identical machines makespan minimization parameterized complexity shuffle product





Author: René Van Bevern - Robert Bredereck - Laurent Bulteau - Christian Komusiewicz - Nimrod Talmon - Gerhard Woeginger -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents