| Article ID: | iaor20013870 |
| Country: | China |
| Volume: | 23 |
| Issue: | 1 |
| Start Page Number: | 31 |
| End Page Number: | 37 |
| Publication Date: | Jan 2000 |
| Journal: | Acta Mathematicae Applicatae Sinica |
| Authors: | Zhang Guochuan, Chen Shiping |
In this paper, we will consider a new on-line scheduling model on two parallel machines where jobs arrive over time. The number of jobs is not known beforehand. Each job becomes available at its release date, which is not known in advance, and its processing time becomes known upon its arrival. The goal is to schedule all jobs such that the makespan is minimized. Chen and Vestjens gave an on-line LPT algorithm with a worst-case ratio of 3/2.