Ordinal On-Line Scheduling for Maximizing the Minimum Machine Completion Time

Yong He () and Zhiyi Tan
Additional contact information
Yong He: Zhejiang University
Zhiyi Tan: Zhejiang University

Journal of Combinatorial Optimization, 2002, vol. 6, issue 2, No 6, 199-206

Abstract: Abstract This paper considers the on-line problem of scheduling nonpreemptively n independent jobs on m > 1 identical and parallel machines with the objective to maximize the minimum machine completion time. It is assumed that the values of the processing times are unknown but the order of the jobs by their processing times is known in advance. We are asked to decide the assignment of all the jobs to some machines at time zero by utilizing only ordinal data rather than the actual magnitudes of jobs. Algorithms to slove the problem are called ordinal algorithms. In this paper, we give lower bounds and ordinal algorithms. We first propose an algorithm MIN which is at most $$(\left\lceil {\sum {_{i = 1}^m {\text{ }}1/} i} \right\rceil + 1)$$ -competitive for any m machine case, while the lower bound is ∑ i=1 m 1/i. Both are on the order of Θ(ln m). Furthermore, for m = 3, we present an optimal algorithm.

Keywords: on-line scheduling; analysis of algorithm; competitive ratio (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1023/A:1013855712183 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:6:y:2002:i:2:d:10.1023_a:1013855712183

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

DOI: 10.1023/A:1013855712183

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 ().