EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1514. The LPT heuristic for minimizing total load on a proportionate openshop
Invited abstract in session WA-26: Optimization problems in scheduling, stream Combinatorial Optimization.
Wednesday, 8:30-10:00Room: 012 (building: 208)
Authors (first author is the speaker)
| 1. | Gur Mosheiov
|
| School of Business, Hebrew University | |
| 2. | Enrique Gerstl
|
| School of Business Administration, The Hebrew University |
Abstract
The LPT heuristic for minimizing total load on a proportionate openshop
Enrique Gerstl and Gur Mosheiov
School of Business Administration,
The Hebrew University, Jerusalem 91905, Israel
Abstract
We study the problem of minimizing total load on a proportionate openshop. The problem is proved to be NP-hard. A simple LPT (Longest Processing Time first)-based heuristic is proposed, and a bound on the worst-case relative error is introduced. The proposed bound is significantly smaller than the classical bound on the relative error of LPT when minimizing makespan on parallel identical machines. The algorithm is tested numerically and is shown to produce extremely close-to-optimal schedules.
Keywords
- Scheduling
- Combinatorial Optimization
Status: accepted
Back to the list of papers