Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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 and proves that the worst-case performance of the LPT algorithm has an asymptotically tight bound of $4}{3}$ times the optimal.
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.