Scheduling Tasks with Exponential Service Times on Nonidentical Processors to Minimize Various Cost Functions.

Abstract

We consider preemptive scheduling of N tasks on m processors; processors have different speeds, tasks require amounts of work which are exponentially distributed, with different parameters. The policies of assigning at every moment the task with shortest (longest) expected processing time among those not yet completed to the fastest processor available, 2nd shortest (longest) to the 2nd fastest etc., are examined, and shown to minimize expected values of various cost functions. As special cases we obtain policies which minimize expected flowtime, expected makespan and expected lifetime of a series system with m component locations and N spares. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1978
Accession Number
ADA062471

Entities

People

  • Gideon Weiss
  • Michael Pinedo

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • C4I
  • Human Systems

DTIC Thesaurus Topics

  • Air Force
  • Computer Programming
  • Computer Science
  • Dynamic Programming
  • Engineering
  • Industrial Engineering
  • Inequalities
  • Military Research
  • Notation
  • Operations Research
  • Random Variables
  • Scheduling (Production)
  • Scientific Research
  • Stationary
  • Statistics
  • United States
  • United States Government

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Operations Research