| 关于单台批处理机在线排序的一些研究 |
| |
| 引用本文： | 刘朝晖,王桢. 关于单台批处理机在线排序的一些研究[J]. 运筹与管理, 2009, 18(1) |
| |
| 作者姓名： | 刘朝晖 王桢 |
| |
| 作者单位： | 华东理工大学数学系,上海,200237 |
| |
| 摘 要： | 一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上的在线排序,其中每个工件有事先未知的到达时间,加工时间在其到达时才知道,目标是极小化工件的最大完工时间.Zhang等(Naval Research Logistics,2001,48:241～258)就该问题提出了一个竞争比不超过2的算法MHB,并猜测其竞争比可以达到1.618,因此是最好的在线算法.在本文中,我们证明了当机器容量趋于无穷时,算法MHB的竞争比不可能小于2,从而就上述猜测给出了否定的回答;另外,我们也提出了一个新算法,其竞争比也不超过2.
|
| 关 键 词： | 运筹学 排序 批处理机 在线算法 |
Some Results on Online Scheduling on a Batch Machine |
| |
| LIU Zhao-hui,WANG Zhen. Some Results on Online Scheduling on a Batch Machine[J]. Operations Research and Management Science, 2009, 18(1) |
| |
| Authors: | LIU Zhao-hui WANG Zhen |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
