Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times

Yongqiang Li, Gang Li, Linyan Sun and Zhiyong Xu

International Journal of Production Economics, 2009, vol. 118, issue 2, 424-429

Abstract: This paper investigates a single machine scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is an increasing function of its execution starting time. Job deterioration is described by a function which is proportional to a linear function of time. The objective is to find a schedule that minimizes total absolute differences in completion times (TADC). We show that the optimal schedule is V-shaped, i.e., 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 also prove some other properties of an optimal schedule, and propose two 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; The; total; absolute; deviation; of; completion; times; (TADC) (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925-5273(08)00389-7
Full text for ScienceDirect subscribers only

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:eee:proeco:v:118:y:2009:i:2:p:424-429

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().