Abstract
We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, $P2|online-list,m_j|C_{max}$, we show that 2 is a lower bound on the competitive ratio of any online algorithm. Thereby we not only improve the existing lower bound of $1+\sqrt{2/3}$, but also close the gap with the trivial upper bound of 2. For the problem with m machines, $Pm|online-list,m_j |C_{max}$, we derive lower bounds using an ILP formulation. Futhermore, we show that with the presented construction no lower bound greater than 2.5 can be obtained.
| Original language | Undefined |
|---|---|
| Place of Publication | Enschede |
| Publisher | BETA Research School for Operations Management and Logistics |
| Number of pages | 13 |
| Publication status | Published - Feb 2007 |
Publication series
| Name | Beta working papers |
|---|---|
| Publisher | Beta Research School for Operations Management and Logistics, University of Twente |
| No. | 2/WP-200 |
| ISSN (Print) | 1386-9213 |
Keywords
- IR-67006
- METIS-242069
- EWI-9514