Parallel-machine scheduling with machine unavailability to maximize total early work

Ke Chen

doi:10.1080/01605682.2025.2565464

Parallel-machine scheduling with machine unavailability to maximize total early work

2025-10-01

0

PRE

AI

DOI：10.1080/01605682.2025.2565464

Original

Original request for help

Save

Abstract

En 中文

This article considers a parallel-machine scheduling problem in which machines are unavailable to process jobs for a specified period. The objective is to maximize the total amount of early work, where the early work of a job is the amount of processing time performed before its due date. Since this problem is NP-hard, we propose a pseudo-polynomial time dynamic programming algorithm, and based on it, we further provide a fully polynomial time approximation scheme. The time complexity of these two algorithms is relatively high; to this end, we also offer a 2-approximation ratio heuristic algorithm to help solve large-scale problems, and we show that the bound is tight.

Keywords:

Parallel machine

early work maximization

dynamic programming

approximation algorithm

FPTAS

Parallel-machine scheduling with machine unavailability to maximize total early work

Abstract

Journal

Organization