Parallel-Machine Scheduling with Step-Deteriorating Jobs to Minimize the Total (Weighted) Completion Time

Cuixia Miao, Fanyu Kong (), Juan Zou (), Ran Ma and Yujia Huo ()
Additional contact information
Cuixia Miao: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China
Fanyu Kong: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China
Juan Zou: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China
Ran Ma: School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China3University Research Center for Smart City, Construction and Management of Shandong Province, Qingdao 266525, P. R. China
Yujia Huo: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China

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

Abstract: In this paper, we consider the parallel-machine scheduling with step-deteriorating jobs. The actual processing time of each job deteriorates as a step function if its starting time is beyond a given deteriorating date. We focus on the case of the common job deteriorating date. For the minimization problem of total completion time, we first show that the problem is NP-hard in the strong sense. Then we propose one property of any optimal schedule. Furthermore, we prove that two special cases of common normal processing time or common penalty are polynomially solvable. For the minimization problem of total weighted completion time, we analyze the NP-hardness and present a polynomial time optimal algorithm for the case of common normal processing time and common penalty.

Keywords: Scheduling; step-deteriorating; strongly NP-hard; polynomial time algorithm (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400115
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:01:n:s0217595922400115

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400115

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