ECCO 2024
Abstract Submission

32. Optimal rescheduling with new jobs under bounded disruption

Invited abstract in session TC-2: Scheduling , stream Scheduling.

Thursday, 11:30 - 13:00
Room: M228

Authors (first author is the speaker)

1. Ulrich Pferschy
Department of Operations and Information Systems, University of Graz
2. Stefan Lendl
Institute of Operations und Information Systems, University of Graz
3. Elena Rener
University of Bern

Abstract

Rescheduling problems arise when a given schedule has to be modified due to an interruption or unexpected event. Following the seminal paper of Hall and Potts (2004), we consider the arrival of new orders to be integrated into a given production sequence of so-called old jobs. To avoid a major disruption of the original schedule, the completion time of each old job in the new sequence should not deviate from its original completion time in the old sequence by more than a certain threshold, no matter whether the job is processed earlier or later. We aim at minimizing a standard objective function for the joint set of jobs.

We succeed in answering an open question in the existing literature by proving that the rescheduling problem is strongly NP-hard for the minimization of the number of late jobs. Then we study more broadly the minimization of the total weighted completion time. We show weak NP-hardness (even for a single old job) and characterize several structural properties of an optimal schedule. These can be utilized for the construction of an exact dynamic programming algorithm with pseudo-polynomial running time. A fully polynomial time approximation scheme (FPTAS) is obtained from the dynamic program by three different scaling and reduction steps. We also present a polynomial time algorithm with bounded approximation ratio based on the relation to a scheduling problem with an unavailability period.

Keywords

Status: accepted

Back to the list of papers