English

运筹学学报 ›› 2012, Vol. 16 ›› Issue (2): 115-120.

• 运筹学 • 上一篇    下一篇

具有前瞻区间的两个工件组单机在线排序问题

杨素芳1, 李文华1   

  1. 1.  郑州大学数学系，郑州，450001
  • 收稿日期:2011-09-23 修回日期:2011-11-09 出版日期:2012-06-15 发布日期:2012-06-15
  • 通讯作者: 李文华 E-mail:liwenhua@zzu.edu.cn

On-line scheduling on a machine of two families with lookahead

YANG  Sufang1, LI  Wenhua1   

  1. 1. Department of Mathematics, Zhengzhou University, Zhengzhou 450001, China
  • Received:2011-09-23 Revised:2011-11-09 Online:2012-06-15 Published:2012-06-15

PDF

1207

被引次数

6

摘要： 研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题. 工件按时在线到达, 目标是最小化 最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于 该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <1.

关键词: 在线排序, 平行分批, 不相容工件组, 最大完工时间, 竞争比

Abstract: We consider on-line scheduling on a parallel batching machine of two incompatible families of unit-length jobs with lookahead where the batch capacity is unbounded. In this paper online means that jobs arrive over time. The objective is to mininize the makespan. In unbounded parallel batch scheduling, an infinite capacity machine can process many jobs simultaneously as a batch, the processing time of a batch is equal to the maximum processing time of jobs in the batch. In the lookahead model, at a time instant t, an on-line algorithm can foresee the information of all jobs arriving in the time segment (t,t+\beta]. Incompatible job families means that jobs which belong to different families cannot be assigned to the same batch. For this problem, we provide a best possible online algorithm of competitive ratio 1+\alpha for 0\leq \beta <1, where \alpha is the positive root of the equation 2\alpha^{2}+(\beta +1)\alpha +\beta -2=0.

Key words:  on-line scheduling, parallel batching, incompatible family, makespan, competitive ratio