Accession Number : AD0711543

Title :   AN EFFICIENT ALGORITHM FOR SCHEDULING INDEPENDENT TASKS.

Descriptive Note : Technical rept.,

Corporate Author : AUBURN UNIV ALA

Personal Author(s) : Wilkerson,L. J. ; Irwin,J. D.

Report Date : AUG 1970

Pagination or Media Count : 101

Abstract : An algorithm is developed for sequencing an independent task set, characterized by deterministic processing times and due dates, on a single processor so that total tardiness is minimized. The tasks are assumed to have a loss function of the form max (O, ((c sub i) - (d sub i))) where c sub i is the calender completion time of task i and d sub i is its due date. The method is in general suboptimal, but conditions are given for which an optimal schedule is always obtained. In addition, a technique is presented for improving suboptimal solutions by interchanging certain non-adjacent pairs of tasks. Finally, this scheduling technique is applied to the multiple processor case. (Author)

Descriptors :   (*COMPUTER PROGRAMMING, SCHEDULING), OPTIMIZATION, DECISION MAKING, MANAGEMENT PLANNING AND CONTROL, DYNAMIC PROGRAMMING, SET THEORY, COMPUTER PROGRAMS, THEOREMS, ALGORITHMS

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE