Rescheduling due to machine disruption to minimize the total weighted completion time

Wenchang Luo (), Taibo Luo (), Randy Goebel () and Guohui Lin ()
Additional contact information
Wenchang Luo: Ningbo University
Taibo Luo: University of Alberta
Randy Goebel: University of Alberta
Guohui Lin: University of Alberta

Journal of Scheduling, 2018, vol. 21, issue 5, No 7, 565-578

Abstract: Abstract We investigate a single machine rescheduling problem that arises from an unexpected machine unavailability, after the given set of jobs has already been scheduled to minimize the total weighted completion time. Such a disruption is represented as an unavailable time interval and is revealed to the production planner before any job is processed; the production planner wishes to reschedule the jobs to minimize the alteration to the originally planned schedule, which is measured as the maximum time deviation between the original and the new schedules for all the jobs. The objective function in this rescheduling problem is to minimize the sum of the total weighted completion time and the weighted maximum time deviation, under the constraint that the maximum time deviation is bounded above by a given value. That is, the maximum time deviation is taken both as a constraint and as part of the objective function. We present a pseudo-polynomial time exact algorithm and a fully polynomial time approximation scheme.

Keywords: Rescheduling; Machine disruption; Total weighted completion time; Approximation scheme (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0575-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:21:y:2018:i:5:d:10.1007_s10951-018-0575-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0575-z

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().