An Implicit Enumeration Algorithm for the Nonpreemptive Shop Scheduling Problem

The purpose of this paper is to report on the development and computational results of an implicit enumeration algorithm for the nonpreemptive shop scheduling problem. This algorithm is inspired by the disjunctive graph representation of the problem and is somewhat similar to the branch-and-bound approach. In order to guide the search, the algorithm employs a decision vector which is designed to reduce the number of iterations. Attention has been focused on improving the quality of the initial solution with minimum computational effort involved. The rapid convergence of the algorithm is demonstrated by solving problems with up to 1000 operations. The results obtained are compared favorably with a number of published procedures. Generalizations of the algorithm are also provided.