The Library
On-line scheduling of two-machine open shops where jobs arrive over time
Tools
Tools
Tools
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-6905.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 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 | ||||
| ISSN: | 1382-6905 | ||||
| Official Date: | 1998 | ||||
| Dates: |
|
||||
| Volume: | 1 | ||||
| Number: | 4 | ||||
| Number of Pages: | 11 | ||||
| Page Range: | pp. 355-365 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
