English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (4): 121-126.doi: 10.15960/j.cnki.issn.1007-6093.2015.04.012

• 运筹学 • 上一篇    

平行机上带有前瞻区间的不相容工件组在线排序问题

李文华1,*, 柴幸1, 袁航2, 杨素芳1   

  1. 1. 郑州大学数学与统计学院, 郑州 450001；2. 浙江大学经济学院, 杭州 310027
  • 收稿日期:2014-12-01 出版日期:2015-12-15 发布日期:2015-12-15
  • 基金资助:

    1.国家自然科学基金(No. 11171313),
    2.河南省教育厅科技研究重点项目(No. 14A110025),
    3.郑州大学自主创新项目(No. 14LD00610)

On-line algorithms for incompatible job families on parallel  machines scheduling with lookahead

LI Wenhua1,*, CHAI Xing1, YUAN Hang2, YANG Sufang1   

  1. 1.School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001,China; 2.College of Economics, Zhejiang University, Hangzhou 310027, China
  • Received:2014-12-01 Online:2015-12-15 Published:2015-12-15
  • Contact: 李文华 liwenhua@zzu.edu.cn

PDF

538

被引次数

2

摘要：

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.

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

Abstract:

 We consider the on-line scheduling of incompatible unit-length job families  on unbounded parallel-batch machines with lookahead when the number of
job families is equal to the number of machines. In this paper online means that jobs arrive over time. The objective is to minimize the makespan. 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). By incompatible job
families, we  mean that jobs from different families cannot be assigned together in the same batch. When \beta \geq 1, we provide an optimal online algorithm; When 0\leq \beta < 1, we give a best possible online algorithm of competitive ratio 1+\alpha, where \alpha is the positive root of the equation \alpha^{2}+(1+\beta) \alpha+\beta-1=0.  We also provide a new lower bound on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.

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