Approximation Schemes for Parallel Machine Scheduling to Maximize Total Weighted Early Work With a Common Due Date

In this article, we study a parallel machine scheduling problem with a common due date to maximize total weighted early work. We present the first EPTAS (efficient polynomial time approximation scheme) for this scheduling problem. In the EPTAS, we first schedule the large jobs with rounded processin...

Full description

Saved in:
Bibliographic Details
Published in:Naval research logistics 2024-11
Main Authors: Li, Weidong, Ou, Jinwen
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article, we study a parallel machine scheduling problem with a common due date to maximize total weighted early work. We present the first EPTAS (efficient polynomial time approximation scheme) for this scheduling problem. In the EPTAS, we first schedule the large jobs with rounded processing times via an integer programming formulation and a network‐flow‐based algorithm, followed by further scheduling the small jobs via a greedy method. For the special case in which the number of machines is fixed, we design an FPTAS (fully polynomial time approximation scheme).
ISSN:0894-069X
1520-6750
DOI:10.1002/nav.22237