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
Distribution Statement : APPROVED FOR PUBLIC RELEASE