On-line scheduling of two-machine open shops where jobs arrive over time
UNSPECIFIED. (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
|Journal or Publication Title:||JOURNAL OF COMBINATORIAL OPTIMIZATION|
|Publisher:||KLUWER ACADEMIC PUBL|
|Number of Pages:||11|
|Page Range:||pp. 355-365|
Actions (login required)
Downloads per month over past year