Minimizing Total Weighted Late Work in a Proportionate Flow Shop with Job Rejection
Asia-Pacific Journal of Operational Research · 2024-06 · 41 (03)
DOI: 10.1142/s0217595923500239 ↗Kurz gefasst
Fachartikel in der Zeitschrift Asia-Pacific Journal of Operational Research, online erschienen am 10.07.2023. Verfasst von Ren-Xia Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 46 Literaturangaben. Gefördert von: Key Research Projects of Henan Higher Education Institutions, IRTSTHN, Chongqing Municipal Science and Technology Commission of Natural Science Fund Projects.
Abstract (Originalsprache)
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 [Formula: see text]-hard by reduction from the Subset Sum problem. When the operations of all jobs have equal processing times, we solve the case in [Formula: see text] 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.
Förderung
- Key Research Projects of Henan Higher Education Institutions
- IRTSTHN
- Chongqing Municipal Science and Technology Commission of Natural Science Fund Projects
- Chongqing Education Commission Natural Science Fund key Projects
Zitieren
APA
Chen, R., Li, S., & Feng, Q. (2024). Minimizing Total Weighted Late Work in a Proportionate Flow Shop with Job Rejection. Asia-Pacific Journal of Operational Research, 41(03). https://doi.org/10.1142/s0217595923500239
Vancouver
Chen R, Li S, Feng Q. Minimizing Total Weighted Late Work in a Proportionate Flow Shop with Job Rejection. Asia-Pacific Journal of Operational Research. 2024;41(03). doi:10.1142/s0217595923500239
BibTeX
@article{Chen2024,
author = {Chen, Ren-Xia and Li, Shi-Sheng and Feng, Qi},
title = {Minimizing Total Weighted Late Work in a Proportionate Flow Shop with Job Rejection},
journal = {Asia-Pacific Journal of Operational Research},
year = {2024},
volume = {41},
number = {03},
doi = {10.1142/s0217595923500239}
}
EUVIMED