Two-agent single-machine scheduling with cumulative deterioration

Ren-Xia Chen and Shi-Sheng Li ()
Additional contact information
Ren-Xia Chen: Zhongyuan University of Technology
Shi-Sheng Li: Zhongyuan University of Technology

4OR, 2019, vol. 17, issue 2, No 4, 219 pages

Abstract: Abstract We address cumulative deterioration scheduling in which two agents compete to perform their respective jobs on a single machine. By cumulative deterioration we mean that the actual processing time of any job of the two agents is a linear increasing function of the total normal processing times of already processed jobs. Each agent desires to optimize some scheduling criterion that depends on the completion times of its own jobs only. We study several scheduling problems arising from different combinations of some regular scheduling criteria, including the maximum cost (embracing lateness and makespan as its special cases), the total completion time, and the (weighted) number of tardy jobs. The aim is to find an optimal schedule that minimizes the objective value of one agent while maintaining the objective value of the other agent not exceeding a fixed upper bound. For each problem under study, we design either a polynomial-time or a pseudo-polynomial-time algorithm to solve it.

Keywords: Scheduling; Single-machine; Two-agent; Cumulative deterioration; 90B35 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-018-0388-0 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:aqjoor:v:17:y:2019:i:2:d:10.1007_s10288-018-0388-0

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-018-0388-0

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

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