On-line scheduling of two-machine open shops where jobs arrive over time

B. Chen, A.P.A. Vestjens, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)


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 inthe non-clairvoyant on-line model, this processing requirement is notknown 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).
Original languageEnglish
Pages (from-to)355-365
Number of pages11
JournalJournal of Combinatorial Optimization
Issue number4
Publication statusPublished - 1998


Dive into the research topics of 'On-line scheduling of two-machine open shops where jobs arrive over time'. Together they form a unique fingerprint.

Cite this