Abstract
We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job Jj has a release time rj and it can only be processed on a subset of machines Mj. The machines are linearly ordered. Each job Jj has a machine index aj such that Mj = {Maj, Maj + 1, ..., Mm}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O (n k log P + m n k2 + m3 k), where k is the number of distinct release times and P is the total processing time of all jobs.
Original language | English (US) |
---|---|
Pages (from-to) | 292-298 |
Number of pages | 7 |
Journal | Discrete Optimization |
Volume | 6 |
Issue number | 3 |
DOIs | |
State | Published - Aug 2009 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computational Theory and Mathematics
- Applied Mathematics
Keywords
- Inclusive processing set
- Makespan minimization
- Polynomial-time algorithms
- Preemptive scheduling
- Release time