Single-machine scheduling problems with time and position dependent processing times

Xingong Zhang (), Guangle Yan, Wanzhen Huang and Guochun Tang

Annals of Operations Research, 2011, vol. 186, issue 1, 345-356

Abstract: We consider single-machine scheduling problems with time and position dependent job processing times. In many industrial settings, the processing time of a job changes due to either job deterioration over time or machine/worker’s learning through experiences. In the models we study, each job has its normal processing time. However, a job’s actual processing time depends on when its processing starts and how many jobs have completed before its start. We prove that the classical SPT (Shortest Processing Time) rule remains optimal when we minimize the makespan or the total completion time. For problems of minimizing the total weighted completion time, the maximum lateness, and the discounted total weighted completion time, we present heuristic sequencing rules and analyze the worst-case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates or weights. Copyright Springer Science+Business Media, LLC 2011

Keywords: Single-machine scheduling; Learning effect; Performance ratio; Worst-case error (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-011-0835-1 (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:186:y:2011:i:1:p:345-356:10.1007/s10479-011-0835-1

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

DOI: 10.1007/s10479-011-0835-1

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 ().