An Improved Method for Scheduling Independent Tasks

1 September 1971

journal article
research article
Published by Taylor & Francis in A I I E Transactions

Vol. 3 (3) , 239-245
https://doi.org/10.1080/05695557108974812

Abstract

A computationally efficient algorithm is developed for scheduling an independent task set, characterized by deterministic processing times and due dates, on a single processor so that total tardiness is minimized. The performance index is assumed to be a loss function of the form max (0, C_i - D_i) where C_i is the calendar completion time of task i and D_i, is its due date. The method is in general sub-optimal, but conditions are given for which an optimal schedule is always obtained. In addition, a technique is presented for improving suboptimal solutions by merely interchanging certain nonadjacent pairs of tasks.

Keywords

This publication has 2 references indexed in Scilit:

Scheduling Independent Tasks on Parallel Processors
Management Science, 1966
Scheduling with Deadlines and Loss Functions on k Parallel Machines
Management Science, 1965