Semi On-Line Scheduling on Two Identical Machines |
| |
| Authors: | Y. He G. Zhang |
| |
| Affiliation: | (1) Department of Applied Mathematics, Zhejiang University, Hangzhou 310027, P. R. China, e-mail: heyong@math.zju.edu.cn , CN;(2) Institute of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China, e-mail: zgc@math.zju.edu.cn , CN |
| |
| Abstract: | ![]()
This paper investigates two different semi on-line scheduling problems on a two-machine system. In the first case, we assume that all jobs have their processing times in between p and rp . In the second case, we assume that the largest processing time is known in advance. We show that one has a best possible algorithm with worst case ratio 4/3 while LS is still the best possible for the other problem with ratio which is still in the worst case . Received: February 23, 1998; revised August 5, 1998 |
| |
| Keywords: | AMS Subject Classifications:90B35 90C27. |
| 本文献已被 SpringerLink 等数据库收录！ |
|
