| Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines |
| |
| 作者姓名： | 罗润梓 孙世杰 |
| |
| 作者单位： | Department of Mathematics，Shanghai University，Shanghai 200444，China，Department of Mathematics，Shanghai University，Shanghai 200444，China |
| |
| 摘 要： | INTRODUCTION Sequencing and scheduling are forms of deci-sion-making which play a crucial role in most manufacturing and production systems as well as in most information-processing environments, and also exist in transportation and distribution settings and in other types of service industries. A scheduling problem is called on-line if it re-quires scheduling jobs irrevocably on the machines as soon as they are given, without any knowledge about jobs that follow later on. If we have full…
|
| 关 键 词： | 时序安排 在线控制 竞争率 工作量 统筹方法 |
| 收稿时间： | 29 February 2004 |
| 修稿时间： | 8 August 2004 |
Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines |
| |
| Luo Run-zi,Sun Shi-jie.Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines[J].Journal of Zhejiang University Science,2005,6(6):591-595. |
| |
| Authors: | Luo Run-zi Sun Shi-jie |
| |
| Institution: | (1) Department of Mathematics, Shanghai University, 200444 Shanghai, China |
| |
| Abstract: | The paper investigates a semi on-line scheduling problem wherein the largest processing time of jobs done by three uniform machines M1, M2, M3 is known in advance. A speed si (s1=1, s2=r, s3=s, 1≤r≤s) is associated with machine Mi. Our goal is to maximize Cmin-the minimum workload of the three machines. We present a min3 algorithm and prove its competitive ratio is max {r 1,(3s r 1)/(1 r s)}, with the lower bound being at least max {2,r}. We also claim the competitive ratio of min3 algorithn cannot be improved and is the best possible for 1≤s≤2, r=1. |
| |
| Keywords: | Scheduling Semi on-line Competitive ratio |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ |
