Rescheduling with New Orders Under Bounded Disruption

Stefan Lendl (), Ulrich Pferschy () and Elena Rener ()
Additional contact information
Stefan Lendl: Department of Operations and Information Systems, University of Graz, 8010 Graz, Austria
Ulrich Pferschy: Department of Operations and Information Systems, University of Graz, 8010 Graz, Austria
Elena Rener: Department of Management and Production Engineering, Politecnico di Torino, 10129 Torino, Italy

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1654-1675

Abstract: Rescheduling problems arise when unpredicted events occur, such as the arrival of new orders. These new jobs should be integrated in a proper way in the existing schedule of the so-called old jobs, with the aim of minimizing an objective function for the joint set of jobs. To avoid a major disruption of the original schedule, each old job is not allowed to deviate from its original completion time by more than a certain threshold. Filling a gap in the existing literature, we consider the minimization of the total weighted completion time. The resulting rescheduling problem is shown to be weakly NP-hard and several properties of the structure of an optimal schedule are derived. These can be used for the construction of an exact dynamic programming algorithm with pseudo-polynomial running time. A fully polynomial time approximation scheme is obtained from the dynamic program by three different scaling and reduction steps. Finally, for the minimization of the number of late jobs a strong NP-hardness result is derived.

Keywords: rescheduling; total weighted completion time; disruption; approximation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0038 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1654-1675

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().