A Heuristic and an Exact Method for Pattern Sequencing Problems

In many applications, a suitable permutation of patterns (electronic circuit nodes, cutting patterns, product orders etc.) has to be found in order to optimize over some given objective function, so giving rise to the so-called Open Stack Problems. We focus on the Gate Matrix Layout Problem, where electronic circuits are obtained by connecting gates and one seeks a gate layout permutation that minimizes connection costs under restrictions on the circuit area. In the literature, the connection costs and the circuit area are also know as Time of Open Stacks and Maximum Number of Open Stacks, respectively. We propose a genetic algorithm providing heuristic solutions, and a branch-and-cut algorithm, based on a new linear integer programming formulation and representing, at our best knowledge, the first exact approach in the literature. The algorithms are under extensive test, and preliminary results on real instances are presented here.