On-Line Scheduling of Two-Machine Open Shops Where Jobs Arrive Over Time

Bo Chen (), Arjen P.A. Vestjens and Gerhard J. Woeginger
Additional contact information
Bo Chen: Warwick Business School, The University of Warwick, Coventry
Arjen P.A. Vestjens: Eindhoven University of Technology
Gerhard J. Woeginger: Institut füur Mathematik, Graz University of Technology

Journal of Combinatorial Optimization, 1998, vol. 1, issue 4, No 2, 355-365

Abstract: Abstract 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).

Keywords: scheduling; open shop; makespan; on-line algorithm; heuristic algorithm; worst-case performance ratio; worst-case guarantee (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009786526733 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:1:y:1998:i:4:d:10.1023_a:1009786526733

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009786526733

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().