An Algorithm for the Construction and Evaluation of Feasible Schedules

An algorithm for the generation of feasible schedules and the computation of the completion times of the job operations of feasible schedule is presented. Using this algorithm, the distribution of schedule times over the set of feasible schedule—or a subset of feasible schedules—was determined for technological orderings that could occur in a general machine shop. These distributions are found to be approximately normal. Biasing techniques corresponding to “first come first serve,” random choice of jobs ready at each machine and combinations of these two extremes were used to compute distributions of schedule times. In all the experiments “first come first serve” appears the best in the sense that convergence to the minimum is fastest and the smallest. The work presented in this paper is supported by the AEC Computing and Applied Mathematics Center, Institute of Mathematical Sciences, New York University, under Contract AT(30-l)-1480 with the U.S. Atomic Energy Commission.

• 저널Management Science · 8(2) · 168–183
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.8.2.168
• 저자Jack Heller, George Logemann