The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan

详细信息    查看全文

• 作者：Qingqin Nong ; Jinjiang Yuan ; Ruyan Fu ; Lin Lin ; Ji Tian
• 关键词：Single-machine scheduling ; Worst-case analysis ; Approximation algorithm ; On-line ; Family ; Batching
• 刊名：International Journal of Production Economics
• 出版年：2008
• 出版时间：February 2008
• 年：2008
• 卷：111
• 期：2
• 页码：435-440
• 全文大小：161 K

文摘

In this paper we consider the single-machine parallel-batching scheduling problem with family jobs under on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job until its arrival. Our objective is to minimize the maximum completion time of the jobs (makespan). We deal with two variants of the problem: the unbounded model in which the machine can handle infinite number of jobs simultaneously and the bounded model. For the unbounded case, we provide an on-line algorithm with a worst-case ratio of 2 and prove that there exists no on-line algorithm with a worst-case ratio less than 2. For the bounded case, we also present an on-line algorithm with a worst-case ratio of 2.