CrossRef Open Access 2025

Parallel Machine Scheduling With Periodic Availability Constraints to Minimize Makespan

Lishi Yu Zhiyi Tan

Lihat Sumber DOI

Abstrak

ABSTRACT We investigate the scheduling problem on parallel and identical machines under periodic availability constraints. Availability periods and unavailability periods appear alternately on each machine. We propose an algorithm, PFFD, and demonstrate that its worst‐case ratio is at most for , where represents the ratio of the duration of an unavailability period to an availability period. Furthermore, we develop the PPTAS algorithm, which can achieve a worst‐case ratio arbitrarily close to and runs in polynomial time when is a constant. When is part of the input, we show that there does not exist a polynomial time algorithm with worst‐case ratio better than unless .

Penulis (2)

Lishi Yu

Zhiyi Tan

Format Sitasi

APA MLA BibTeX

Yu, L., Tan, Z. (2025). Parallel Machine Scheduling With Periodic Availability Constraints to Minimize Makespan. https://doi.org/10.1002/nav.70019

Akses Cepat

Lihat di Sumber doi.org/10.1002/nav.70019

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: CrossRef
DOI: 10.1002/nav.70019
Akses: Open Access ✓