Optimal Online-list Batch Scheduling
Speaker
Abstract
| We consider the online-list batch scheduling problem. Jobs arrive one by one and have to be assigned upon arrival to a scheduled batch such that the makespan is minimized. Each batch can accommodate up to B jobs. The online-time version of the problem has been extensively studied but the online-list model has received less attention so far. We give a complete classification of the tractability of this online problem. More specifically, with respect to the competitive ratio, we derive an optimal algorithm for any batch capacity. The novelty of this work lies in the lower bound proofs. The design of the optimal online algorithms is based on the well known "doubling" strategy. |
| Remember that this is a lunch meeting. For ordering the right amount of sandwiches, coffee, tea and milk, please let us know before Wednesday, November 19 whether you will be present. We hope to welcome all of you. |
| Contact information: |
| Wilco van den Heuvel |
