On Scheduling Problems with Deferral Costs

A class of scheduling problems involving deferral costs has been formulated by McNaughton, who has described a simple method of solution for the linear, single-processor case. In this report dynamic programming and linear programming techniques are applied to nonlinear and multiple-processor problems. A dynamic programming solution of the nonlinear, single processor problem is possible, provided the number of jobs is small. Transportation methods of linear programming can be used to solve large nonlinear, multiple-processor problems, provided the processing times for the jobs are equal. Approximate and/or partial solutions are possible for other cases.