2010-10-01
Polynomial-time approximation schemes for scheduling problems with time lags
Publication
Publication
Journal of Scheduling , Volume 13 - Issue 5 p. 553- 559
We identify two classes of machine scheduling problems with time lags that possess Polynomial-Time Approximation Schemes (PTASs). These classes together, one for minimizing makespan and one for minimizing total completion time, include many well-studied time lag scheduling problems. The running times of these approximation schemes are polynomial in the number of jobs, but exponential in the number of machines and the ratio between the largest time lag and the smallest positive operation time. These classes constitute the first PTAS results for scheduling problems with time lags.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1007/s10951-009-0134-8, hdl.handle.net/1765/17384 | |
| ERIM Article Series (EAS) | |
| Journal of Scheduling | |
| Organisation | Erasmus Research Institute of Management |
|
Zhang, X., & van de Velde, S. (2010). Polynomial-time approximation schemes for scheduling problems with time lags. Journal of Scheduling, 13(5), 553–559. doi:10.1007/s10951-009-0134-8 |
|
