| 工件按加工长度不增序到达的最小化最大流程在线分批排序 |
| |
| 引用本文： | 焦成文,李文华. 工件按加工长度不增序到达的最小化最大流程在线分批排序[J]. 运筹学杂志, 2013, 0(4): 96-102 |
| |
| 作者姓名： | 焦成文 李文华 |
| |
| 作者单位： | [1]郑州大学数学与统计学院,郑州450001 [2]中国科学院大学数学科学学院,北京100049 |
| |
| 基金项目： | 国家自然科学基金（No.11171313） |
| |
| 摘 要： | 研究单处理机工件按加工长度不增顺序到达的在线分批排序问题．工件按时在线到达，目标是最小化最大流程．流程时间是指工件的完工时间与到达时间的差值，它体现了工件在系统内的逗留时间．对于批容量有界的情形，给出了一个竞争比为1＋√5/2的最好可能的在线算法；对于批容量无界的情形，给出了一个竞争比为√2的最好可能的在线算法．
|
| 关 键 词： | 在线排序 平行分批 最大流程时间 竞争比 |
Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time |
| |
| JIAO Chengwen,LI Wenhua. Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time[J]. , 2013, 0(4): 96-102 |
| |
| Authors: | JIAO Chengwen LI Wenhua |
| |
| Affiliation: | 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 |
| |
| Abstract: | We consider on-line scheduling on a parallel batching machine where the jobs come with the noninereasing-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 1＋√5/2. For the unbounded model, we also give a best possible algorithm with competitive ratio √2. |
| |
| Keywords: | on-line scheduling parallel batching maximum flow-time competitive ratio |
| 本文献已被 维普 等数据库收录！ |
