Semi On-Line Scheduling on Two Identical Machines

• DOI: 10.1007/s006070050020
• Publication Date: 2004-03-20T10:42:43Z
• Authors: Y. He; G. Zhang
• Keywords: Line (geometry)

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 $(p>0, r\geq1)$ . 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 $(r+1)/2$ which is still $3/2$ in the worst case $r=2$ .