A New Approach to Job Shop Scheduling with Due Dates,
Abstract
The classical formulation of the static job shop scheduling problem with job due dates implies that the question of interest to the manager is: What is the best that can be done to meet due dates with fixed resources. In this paper, two alternative formulations of the problem are proposed; one because of its practical appeal, the other because of its methodological appeal. The latter is used to develop a multi-pass heuristic scheduling procedure aimed at providing a practical tool for attacking any of the three formulations of the problem. The procedure was programmed and applied to a set of nineteen test problems for which solutions satisfying all job due dates are known to exist. The problems range in size up to 10 jobs, 9 machines and 14 jobs, 7 machines. Solutions were attained for each of the test problems. The average and maximum IBM 360-91 computing times were 1.23 and 3.28 seconds, respectively. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1971
- Accession Number
- AD0725838
Entities
People
- Charles A. Holloway
- Rosser T. Nelson
Organizations
- University of California, Los Angeles