Evaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors

Abstract

In this paper we consider the problem of scheduling “n” independent fades on “m” parallel processors. Each job consists of a single operation with a specific processing time and due date. The processors are identical and the operation of the system is non-preemptive. The objective is to schedule the jobs in such a way that the total tardiness of the n jobs is as small as possible. For the case of a single processor with n jobs, there exists algorithms which provide optimal solutions. On the other hand currently available optimal scheduling algorithms for multiple processors can handle only small problems. Therefore, practitioners are forced to use heuristic methods to schedule their jobs on multiple processors. This raises questions of the following nature: “Are we scheduling our jobs reasonably well? Are there other schedules with which our total tardiness can be lowered substantially? How far off might the heuristic solution be, from the optimal solution?” The study reported in this paper focuses on a heuristic which can handle reasonably large problems, and yet can be simply and economically implemented. Experiments are conducted by establishing lower bounds for the optimal total tardiness of randomly generated scheduling problems. These lower bounds are then compared with the total tardiness obtained from the heuristic. It is found that the heuristic under study provides solutions which are quite close to the optimal ones. The experiments include 560 randomly generated problems that range from “loose” to “tight” in due dates, with varying numbers of jobs and processors. A nonparametric statistical analysis is presented to generalize the results.