A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors

We consider the scheduling of sets of n simultaneously available tasks on two identical processors. The task execution times are assumed to be independent samples from the uniform distribution on [0, 1]. We analyze the expected makespan (schedule-length) performance of two well-known largest-task-fi...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 1984-05, Vol.9 (2), p.260-266
Main Authors: Coffman, E. G., Jr, Frederickson, G. N, Lueker, G. S
Format: Article
Language:English
Subjects:
2-machine job shop
Algorithms
Approximation algorithms
Expected values
largest-first rule
Markov chains
Mathematical analysis
Mathematical sequences
Modeling
Operations research
Optimization
Random variables
Scheduling
Sequencing
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the scheduling of sets of n simultaneously available tasks on two identical processors. The task execution times are assumed to be independent samples from the uniform distribution on [0, 1]. We analyze the expected makespan (schedule-length) performance of two well-known largest-task-first, nonpreemptive approximation rules. With the largest-first (LF) rule, tasks are assigned in nonincreasing order of execution time to the processors as they become available. With the restricted largest first (RLF) rule, tasks are assigned in pairs, one to a processor. The larger task of a pair is the first to be scheduled. (If n is odd, the last task is simply assigned to the earner finishing processor in the schedule for the first n – 1 tasks.) We prove that the expected makespan for LF is bounded by
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.9.2.260