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

Ali Dogramaci and Julius Surkis
Additional contact information
Ali Dogramaci: Columbia University
Julius Surkis: Rutgers University

Management Science, 1979, vol. 25, issue 12, 1208-1216

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.

Keywords: production/scheduling; statistics: nonparametric; programming: integer algorithms; heuristic (search for similar items in EconPapers)
Date: 1979
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.25.12.1208 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:25:y:1979:i:12:p:1208-1216

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().