EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Scheduling
- Algorithms
- Combinatorial Optimization
Status: accepted
Back to the list of papers