On-line scheduling of two-machine open shops where jobs arrive over time
Chen, Bo, Arjen, P. A., Vestjens, Arjen P. A. and Woeginger, Gerhard J. . (1998) On-line scheduling of two-machine open shops where jobs arrive over time. Journal of Combinatorial Optimization, 1 (4). pp. 355-365. ISSN 1382-6905Full text not available from this repository.
We investigate the problem of on-line scheduling two-machine open shops with the objective of minimizing the makespan. Jobs arrive independently over time, and the existence of a job is not known until its arrival. In the clairvoyant on-line model, the processing requirement of every job becomes fully known at the arrival of the job, while in the non-clairvoyant on-line model, this processing requirement is not known until the job is processed and completed. In both models, scheduling of a job is irrevocable.
We study the two-machine open shop problem for both models in the preemptive and in the non-preemptive version. For each of the four variants, we provide an algorithm that is best possible with respect to the worst-case performance. In the clairvoyant on-line model, the best worst-case performance ratios are 5/4 (preemptive) and 3/2 (non-preemptive), and in the non-clairvoyant on-line model, they are 3/2 (preemptive and non-preemptive).
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Divisions:||Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences
Faculty of Social Sciences > Warwick Business School
|Journal or Publication Title:||Journal of Combinatorial Optimization|
|Publisher:||Springer New York LLC|
|Number of Pages:||11|
|Page Range:||pp. 355-365|
Actions (login required)