Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs

Sun L-H, Sun L-Y and Wang J-B ()
Additional contact information
Sun L-H: School of Business Administration, Xi’an University of Technology
Sun L-Y: The State Key Laboratory on Mechanic Manufacturing, Xi’an Jiaotong University
Wang J-B: Knowledge Management & Innovation Research Centre, Xi’an Jiaotong University

Journal of the Operational Research Society, 2011, vol. 62, issue 4, 768-775

Abstract: Abstract In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.

Keywords: scheduling; single machine; deteriorating jobs; total absolute differences in waiting times; heuristic algorithm (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1057/jors.2010.26 Abstract (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:pal:jorsoc:v:62:y:2011:i:4:d:10.1057_jors.2010.26

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/jors.2010.26

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().