Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System

Authors:
  • BDBryan L. Deuermeyer
    Bryan L. Deuermeyer
  • DFDonald K. Friesen
    Donald K. Friesen
  • MLMichael A. Langston
    Michael A. Langston

Abstract
This investigation considers the problem of nonpreemptively assigning a set of independent tasks to a system of identical processors to maximize the earliest processor finishing time. While this goal is a nonstandard scheduling criterion, it does have natural applications in certain maintenance scheduling and deterministic fleet sizing problems. The problem is NP-hard, justifying an analysis of heuristics such as the well-known LPT algorithm in an effort to guarantee near-optimal results. It is proved that the worst-case performance of the LPT algorithm has an asymptotically tight bound of $\frac{4}{3}$ times the optimal.

This publication has 4 references indexed in Scilit: