| 具有特殊工件的平行机在线排序问题 |
| |
| 引用本文： | 刘瑞芳. 具有特殊工件的平行机在线排序问题[J]. 运筹学学报, 2008, 12(3) |
| |
| 作者姓名： | 刘瑞芳 |
| |
| 基金项目： | 国家自然科学基金,Development Foundation of Shanghai Education Committee |
| |
| 摘 要： | 本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.
|
| 关 键 词： | 运筹学 平行机排序 列表在线 特殊工件 竞争比 |
On-line Parallel Machine Scheduling with Special Jobs to Minimize the Makespan |
| |
| Liu Ruifang. On-line Parallel Machine Scheduling with Special Jobs to Minimize the Makespan[J]. OR Transactions, 2008, 12(3) |
| |
| Authors: | Liu Ruifang |
| |
| Affiliation: | Department of Mathematics, East China Normal University, Shanghai 200241, China |
| |
| Abstract: | In the parallel machine on-line scheduling with special jobs to minimize the makespan, we have two kinds of jobs, normal jobs and special jobs. The normal jobs can be processed on any one of the m identical parallel machines, while the special jobs can only be processed on specified machines, and each of the special jobs has its own unique specified machine. In this paper, all the special jobs are specified to be processed on machine M1. We provide a linear on-line algorithm with competitive ratio of (2m2 - 2m + 1)/(m2 - m + 1). When rn = 2, the algorithm is the best possible and has a competitive ratio of 5/3. When m = 3, the competitive ratio of the algorithm is 13/7 ≈ 1.857, and we also show that the considered problem has no on-line algorithm with competitive ratio less than (1 +(平方根33))/4 ≈ 1.686. |
| |
| Keywords: | Operations research parallel machine scheduling on-line-list special jobs competitive ratio |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
