A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups

Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. This paper addresses a jobshop scheduling problem with these factors simultaneously considered. In it, a mixed integer program model of the problem is presented, along with a local search scheme. The local search scheme utilizes a property identified to reduce computation time. In addition, a property that establishes a performance bound is presented. Results from a comparative computational study using benchmark data show that the scheme significantly enhances the performance of several greedy-based dispatching rules for the problem under consideration.