Premium
SCHEDULING JOBS ON PARALLEL PROCESSORS WITH DYNAMIC PROGRAMMING
Author(s) -
Gupta Jatinder N. D.,
Maykut Albert R.
Publication year - 1973
Publication title -
decision sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.238
H-Index - 108
eISSN - 1540-5915
pISSN - 0011-7315
DOI - 10.1111/j.1540-5915.1973.tb00572.x
Subject(s) - computer science , mathematical optimization , dynamic programming , computation , scheduling (production processes) , dynamic priority scheduling , set (abstract data type) , job shop scheduling , algorithm , mathematics , schedule , programming language , operating system
The problem of scheduling jobs on M ‐parallel processors is one of selecting a set of jobs to be processed from a set of available jobs in order to maximize profit. This problem is examined and a dynamic programming solution is presented which decomposes it into a sequencing problem within an allocation problem. The computation required for solution is found to depend on the sequencing problem as it is affected by the waiting cost function. Various forms of the waiting cost function are considered. The solution procedure is illustrated by an example, and possible extensions of the formulation are discussed.