English

运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 96-102.

• 运筹学 • 上一篇    下一篇

工件按加工长度不增序到达的最小化最大流程在线分批排序

焦成文1,2, 李文华1,*   

  1. 1. 郑州大学数学与统计学院, 郑州 450001;   2. 中国科学院大学数学科学学院, 北京 100049;
  • 出版日期:2013-12-15 发布日期:2013-12-15
  • 通讯作者: 李文华 E-mail:liwenhua@zzu.edu.cn
  • 基金资助:

    国家自然科学基金 (No. 11171313)

Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time

JIAO Chengwen1,2, LI Wenhua1,*   

  1. 1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China; 2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
  • Online:2013-12-15 Published:2013-12-15

PDF

629

摘要： 研究单处理机工件按加工长度不增顺序到达的在线分批排序问题. 工件按时在线到达, 目标是最小化最大流程. 流程时间是指工件的完工时间与到达时间的差值, 它体现了工件在系统内的逗留时间. 对于批容量有界的情形, 给出了一个竞争比为$\frac{1+\sqrt{5}}{2}$的最好可能的在线算法; 对于批容量无界的情形, 给出了一个竞争比为$\sqrt{2}$的最好可能的在线算法.

关键词: 在线排序, 平行分批, 最大流程时间, 竞争比

Abstract: We consider on-line scheduling on a parallel batching machine where the jobs come with the nonincreasing-processing times. In this paper online means that jobs arrive over time. The objective is to minimize the maximum flow time of these jobs.  The flow-time of a job means that its completion time minus its arrival time.  It reflects the time of the job staying in the system. For the bounded model, we give a best possible algorithm with competitive ratio $\frac{1+\sqrt{5}}{2}$. For the unbounded model, we also give a best possible algorithm with competitive ratio $\sqrt{2}$.

Key words: on-line scheduling, parallel batching, maximum flow-time, competitive ratio

中图分类号: