EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1238. An FPTAS for scheduling with resource constraints

Invited abstract in session TD-60: Resource constrained scheduling, stream Project Management and Scheduling.

Tuesday, 14:30-16:00
Room: S09 (building: 101)

Authors (first author is the speaker)

1. Bo Chen
Warwick Business School, University of Warwick
2. Vitaly Strusevich
School of Computing and Mathematical Sciences, University of Greenwich

Abstract

We study a basic scheduling problem with resource constraints: A number of jobs need to be scheduled on two parallel identical machines to minimize the makespan, subject to the constraint that jobs may require a unit of one of the given renewable resources during their execution. For this NP-hard problem, we develop a fully polynomial-time approximation scheme (FPTAS). Our FPTAS makes novel use of existing algorithms for the subset-sum problem and the open shop scheduling problem.

Keywords

Status: accepted


Back to the list of papers