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 \((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\).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: February 23, 1998; revised August 5, 1998
Rights and permissions
About this article
Cite this article
He, Y., Zhang, G. Semi On-Line Scheduling on Two Identical Machines. Computing 62, 179–187 (1999). https://doi.org/10.1007/s006070050020
Issue Date:
DOI: https://doi.org/10.1007/s006070050020