Parallel Machines Scheduling with Deteriorating Maintenance Activities and Job Rejection

Juan Zou (), Yu-Kang Sui (), Jie Gao () and Xian-Zhao Zhang
Additional contact information
Juan Zou: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China
Yu-Kang Sui: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China
Jie Gao: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China
Xian-Zhao Zhang: College of Mathematics and Statistics, Linyi University, Linyi 276005, P. R. China

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

Abstract: We consider parallel identical machines scheduling problems with deteriorating maintenance activities and the option of job rejection. Each machine has at most one deteriorating maintenance activity. The length of each maintenance activity increases linearly with its starting time. The location of the maintenance activity on each machine needs to be determined. The goal is to find the sequence of jobs to minimize scheduling cost; we further the model by allowing job rejection. A job is either accepted and processed on one of machines, or rejected. The goal is to determine the sequence of the accepted jobs to minimize scheduling cost of the accepted jobs plus total rejection penalty of the rejected jobs. When the scheduling cost is the makespan, we design a pseudo-polynomial time algorithm, a 2-approximation algorithm and a fully polynomial time approximation scheme. When the scheduling cost is the total completion time, we provide a polynomial time algorithm for the problem. When the scheduling costs are the total weighted completion time under the agreeable ratio assumption and the maximum lateness, we present pseudo-polynomial time algorithms to solve these problems, respectively.

Keywords: Scheduling; deteriorating maintenance activity; rejection; pseudo-polynomial algorithm (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400139
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:s0217595922400139

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400139

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