Rescheduling on a single machine with part-type dependent setup times and deadlines

Ali Tamer Unal, Reha Uzsoy and Ali Kiran

Annals of Operations Research, 1997, vol. 70, issue 0, 93-113

Abstract: We consider the problem of rescheduling a facility modeled as a single machine in the face of newly arrived jobs with part-type dependent setup times. The facility contains a number of jobs that have been assigned due dates and scheduled so as to meet them. We wish to insert the new jobs into the existing schedule in a manner that will minimize the disruption of the jobs in the system and minimize the total weighted completion time or the maximum completion time of the new jobs. We provide a polynomial-time algorithm for the maximum completion time problem, prove that the total weighted completion time problem is NP-hard in the strong sense and study several of its special cases. In particular, we show that the case with reverse-agreeable weights (of which the unit weight problem is a special case) can be solved in polynomial time when the number of part types is fixed. We also present two heuristics for the problem with arbitrary weights and develop data-dependent worst-case error bounds. Extensive computational experiments show that the heuristics consistently obtain near-optimal solutions in very reasonable CPU times. Copyright Kluwer Academic Publishers 1997

Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018955111939 (text/html)
Access to full text is restricted to subscribers.

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:annopr:v:70:y:1997:i:0:p:93-113:10.1023/a:1018955111939

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

DOI: 10.1023/A:1018955111939

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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