Algorithms for Solving Production-Scheduling Problems

Abstract

Algorithms are developed for solving problems to minimize the length of production schedules. The algorithms generate anyone, or all, schedule(s) of a particular subset of all possible schedules, called the active schedules. This subset contains, in turn, a subset of the optimal schedules. It is further shown that every optimal schedule is equivalent to an active optimal schedule. Computational experience with the algorithms shows that it is practical, in problems of small size, to generate the complete set of all active schedules and to pick the optimal schedules directly from this set and, when this is not practical, to random sample from the bet of all active schedules and, thus, to produce schedules that are optimal with a probability as close to unity as is desired. The basic algorithm can also generate the particular schedules produced by well-known machine loading rules.