A Combinatorial Approach to Dynamic Scheduling Problems

Zaw-Sing Su and Kenneth C. Sevcik
Additional contact information
Zaw-Sing Su: ITT-TTC, Stamford, Connecticut
Kenneth C. Sevcik: University of Toronto, Toronto, Ontario

Operations Research, 1978, vol. 26, issue 5, 836-844

Abstract: We introduce a combinatorial approach for studying multiple-processor scheduling problems that involve the preemptive scheduling of independent jobs. Unlike most combinatorial models used for studying scheduling problems, ours assumes that jobs arrive over time but that scheduling decisions must be made without knowledge of what jobs will arrive in the future. We seek dynamic algorithms that make scheduling decisions based on changing information. An algorithm is considered to be “optimal” only if it consistently produces schedules no worse than those produced by any omniscient algorithm that has exact knowledge of attributes of all jobs in advance. Measures of performance examined include the maxima and means of completion time, flow time, and lateness. “Optimal” algorithms are established in a few cases, while it is determined in other cases that such “optimal” algorithms require more information than the model provides.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.5.836 (application/pdf)

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:inm:oropre:v:26:y:1978:i:5:p:836-844

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().