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-6905

Full text not available from this repository.

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
Journal or Publication Title:	JOURNAL OF COMBINATORIAL OPTIMIZATION
Publisher:	KLUWER ACADEMIC PUBL
ISSN:	1382-6905
Date:	1998
Volume:	1
Number:	4
Number of Pages:	11
Page Range:	pp. 355-365
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/15416

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item