Research Reports from the Department of Operations
Scheduling Independent Jobs on Parallel Machines to Minimize Two Objectives Related to Job Tardiness
Document Type
Dissertation
Publication Date
8-27-1975
Abstract
This research considers the scheduling on parallel machines of jobs which are independent and simultaneously available for processing and which have due dates and known processing times. Cases in which the machines are identical and in which they operate at different speeds are both covered. The principal objective treated is finding a schedule which meets all due dates and uses the minimum number of machines required for that criterion. It is shown that methods which solve for this first objective can easily be modified for a second, that of minimizing maximum tardiness on a given number of machines. An assumption made for most of the paper is that each job must be assigned to a single machine and processed without interruption on it. However, solutions are given for the special cases in which the jobs may be divided between machines. Previous research on the scheduling of independent jobs on parallel machines is reviewed. It is shown that an optimal sequence of jobs on a given machine may easily be established. Lower bounds on the number of machines required in a zero tardiness schedule and on maximum tardiness on a fixed number of machines are proved. It is shown that this first bound is equivalent to an earlier sufficient condition (Horn 1974) for the case in which the jobs may be divided between machines but not processed on more than one simultaneously.Six heuristics for the zero tardiness problem are developed, as are exact enumerative algorithms for both the identical and nonidentical machine cases. The amount of search required in the exact methods is reduced by a group of theorems; these establish conditions under which sets of jobs must all be on different machines in a zero tardiness schedule, give lower bounds on the start time of each job, and (for the nonidentical machines case) restrict certain jobs to the fastest machines.For the identical machines case, computational results are presented for problems with from ten to forty jobs and between two and eight machines required at the lower bound. The lower bound on the number of machines required for zero tardiness was found to give the exact minimum for at least eighty-four percent of the problems in fifteen out of sixteen problem sets. The exact algorithm for the zero tardiness problem solved, using five seconds or less time on a UNIVAC 1103, problems with up to forty jobs and five machines required at the lower bound. However, for several problems with twenty and thirty jobs, searches on six and eight machines could not be completed in that amount of time.
Keywords
Operations research, Scheduling--Mathematical models, Parallel processing (Electronic computers), Heuristic algorithms, Production scheduling, Tardiness, Computational complexity
Publication Title
Dissertation, Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 382 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Nunnikhoven, Thomas S., "Scheduling Independent Jobs on Parallel Machines to Minimize Two Objectives Related to Job Tardiness" (1975). Research Reports from the Department of Operations. 496.
https://commons.case.edu/wsom-ops-reports/496