Minimizing Total Weighted Late Work in a Proportionate Flow Shop with Job Rejection

Ren-Xia Chen, Shi-Sheng Li () and Qi Feng ()
Additional contact information
Ren-Xia Chen: School of Mathematics and Information Science, Zhongyuan University of Technology, Zhengzhou 450007, People’s Republic of China
Shi-Sheng Li: School of Mathematics and Information Science, Zhongyuan University of Technology, Zhengzhou 450007, People’s Republic of China
Qi Feng: School of Mathematics and Information Science, Zhongyuan University of Technology, Zhengzhou 450007, People’s Republic of China

Asia-Pacific Journal of Operational Research (APJOR), 2024, vol. 41, issue 03, 1-23

Abstract: In this paper, we investigate a scheduling problem with optional job rejection in a proportionate flow shop setting, where the job processing times are machine independent. A solution to our problem is characterized by (i) partitioning the set of jobs into a set of accepted jobs and a set of rejected jobs, and (ii) scheduling the accepted jobs in a proportionate flow shop setting. The aim is to find a solution to minimize the sum of total weighted late work of the accepted jobs and total rejection cost of the rejected jobs. When all jobs share a common due date, we show that the single-machine case is ð ’©ð ’«-hard by reduction from the Subset Sum problem. When the operations of all jobs have equal processing times, we solve the case in O(n3) time by reducing it into a linear assignment problem. For the general problem, we first provide a pseudo-polynomial-time algorithm via the dynamic programming method, then we convert it into a fully polynomial time approximation scheme. As a byproduct, we also resolve an open question in the literature.

Keywords: Scheduling; proportionate flow shop; late work; rejection (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923500239
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:41:y:2024:i:03:n:s0217595923500239

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595923500239

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