EUVIMEDEUVIMED entdecken
Crossref

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

Ren-Xia Chen, Shi-Sheng Li, Qi Feng

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →