Online scheduling in a parallel batch processing system to minimize makespan using restarts
详细信息 查看全文
- 作者：Ruyan Fu ; Tian Ji ; Jinjiang Yuan ; Yixun Lin
- 关键词：Single machine scheduling ; Parallel batch ; Online algorithm ; Restart ; Competitive ratio
- 刊名：Theoretical Computer Science
- 出版年：2007
- 出版时间：20 April 2007
- 年：2007
- 卷：374
- 期：1-3
- 页码：196-202
- 全文大小：214 K
文摘
We consider an online scheduling problem in a parallel batch processing system with jobs in a batch being allowed to restart. Online means that jobs arrive over time, and all jobs’ characteristics are unknown before their arrival times. A parallel batch processing machine can handle up to several jobs simultaneously. All jobs in a batch start and complete at the same time. The processing time of a batch is equal to the longest processing time of jobs in the batch. We are allowed to restart a batch, that is, a running batch may be interrupted, losing all the work done on it. Jobs in the interrupted batch are released and become independently unscheduled jobs. We deal with an unbounded model where each batch’s capacity is sufficiently large. We provide a linear online algorithm with competitive ratio 3/2 for the problem. We also show that the considered problem has no online algorithm using restarts with competitive ratio less than .