A Branch-and-Bound Algorithm for Two-Stage Production-Sequencing Problems

Abstract

This paper presents an algorithm for determining an optimum solution to a two-stage production sequencing problem with these characteristics: There are n jobs to be sequenced in a two-stage production environment; each production stage is equipped with a single facility; jobs to be sequenced are subject to due-date constraints; facilities in both stages require setup prior to processing each job; setup times in both stages are sequence dependent, and setup cost is assumed to be directly proportional to setup time; and the optimal solution is one that minimizes the total setup cost (of stages I and II) without violating job-due dates. The algorithm employs controlled enumeration through branch-and-bound procedures, together with feasibility tests.