EUVIMEDEUVIMED entdecken
Crossref

Approximation algorithms for scheduling with rejection in green manufacturing

Mingyang Gong, Brendan Mumey

Theoretical Computer Science · 2026-09 · 1083 · 116136

DOI: 10.1016/j.tcs.2026.116136 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theoretical Computer Science, 2026-09. Verfasst von Mingyang Gong und 1 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivated by green manufacturing, this paper investigates a scheduling with rejection problem subject to an energy consumption constraint. Machines are associated with non-uniform energy consumption rates, defined as the energy consumed per unit time. Each job is either rejected with a rejection penalty or accepted and scheduled on some machine for processing, which incurs energy consumption. The problem aims to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs while the total energy consumption is bounded by a given threshold. In this paper, when the number of machines is part of the input, we develop the first $(2+\epsilon)$-approximation algorithm for any fixed constant $\epsilon$ and a simple QPTAS as well as a PTAS for uniform energy consumption rates. Moreover, we present an FPTAS when the number of machines is a fixed constant.

Förderung

  • National Science Foundation

Zitieren

APA

Gong, M., & Mumey, B. (2026). Approximation algorithms for scheduling with rejection in green manufacturing. Theoretical Computer Science, 1083, 116136. https://doi.org/10.1016/j.tcs.2026.116136

Vancouver

Gong M, Mumey B. Approximation algorithms for scheduling with rejection in green manufacturing. Theoretical Computer Science. 2026;1083:116136. doi:10.1016/j.tcs.2026.116136

BibTeX
@article{Gong2026,
  author = {Gong, Mingyang and Mumey, Brendan},
  title = {Approximation algorithms for scheduling with rejection in green manufacturing},
  journal = {Theoretical Computer Science},
  year = {2026},
  volume = {1083},
  pages = {116136},
  doi = {10.1016/j.tcs.2026.116136}
}
Kostenlos starten →