GRAPH PROPERTIES OF MINIMIZATION OF OPEN STACKS PROBLEMS AND A NEW INTEGER PROGRAMMING MODEL

Pesquisa Operacional

Isabel Cristina Lopes¹  J.m. Valério De Carvalho¹ 

关键词: integer programming;    graph layout problems;    Minimization of Open Stacks Problem;   

DOI  :  10.1590/0101-7438.2015.035.02.0213

来源: SciELO

【 摘 要 】

The Minimization of Open Stacks Problem (MOSP) is a Pattern Sequencing Problem that often arises in industry. Besides the MOSP, there are also other related Pattern Sequencing Problems of similar relevance. In this paper, we show that each feasible solution to the MOSP results from an ordering of the vertices of a graph that defines the instance to solve, and that the MOSP can be seen as an edge completion problem that renders that graph an interval graph. We review concepts from graph theory, in particular related to interval graphs, comparability graphs and chordal graphs, to provide insight to the structural properties of the admissible solutions of Pattern Sequencing Problems. Then, using Olariu'scharacterization and other structural properties of interval graphs, we derive an integer programming model for the MOSP. Some computational results for the model are presented.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License