Single-Machine Time-Dependent Scheduling with Proportional and Delivery Times

Cuixia Miao, Jiaxin Song () and Yuzhong Zhang ()
Additional contact information
Cuixia Miao: School of Mathematical Sciences, Qufu, Normal University, Qufu 273165, P. R. China
Jiaxin Song: School of Mathematical Sciences, Qufu, Normal University, Qufu 273165, P. R. China
Yuzhong Zhang: Institute of Operations Research, Qufu, Normal University, Rizhao 276826, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 04, 1-12

Abstract: We consider the time-dependent scheduling with proportional and delivery times on a single machine. Three models of the processing times are addressed here, they are proportional deterioration, proportional-linear shortening and proportional-linear increasing. The objective is to minimize the time by which all jobs are delivered. For the first model, we prove that the problem is polynomial solvable when jobs have identical release dates. When jobs arrive dynamically, we first give the proof of the NP-hardness and present a two-approximation algorithm. Then we propose a fully polynomial time approximation scheme for the case where the number of distinct release dates is a constant by applying the “rounding-the-input-data†technique. For the second and third models, when jobs have identical release dates, we prove that they are polynomial solvable, when jobs have different release dates, we present two-approximation algorithms for each of them.

Keywords: Deterioration; delivery times; NP-hard; fully polynomial time approximation scheme (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400152
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:wsi:apjorx:v:40:y:2023:i:04:n:s0217595922400152

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400152

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().