Refinements on an emuneration scheme for solving a pattern sequencing problem

We introduce some refinements on a branch-and-bound-scheme for solving the minimization of open stack problem (MOSP). After representing the MOSP as a graph traversing problem, we attempt to divide the graph into parts aiming to solve the resulting subgraphs independently in order to reduce the search in the branching scheme. Subgraphs with special topologies (such as trees) are solved exactly using polynomial time algorithms. The branching scheme is applied only to the parts that are ‘complex’. The refinements introduced produce substantial savings in computational time when the MOSP graph presents some special structures. Limited computational results are presented.