Premium
Refinements on an enumeration scheme for solving a pattern sequencing problem
Author(s) -
Yanasse H. H,
Limeira M. S
Publication year - 2004
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2004.00458.x
Subject(s) - traverse , enumeration , scheme (mathematics) , graph , mathematical optimization , computational complexity theory , computer science , minification , theoretical computer science , mathematics , algorithm , discrete mathematics , mathematical analysis , geodesy , geography
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.