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

AUTOR(ES)

Lopes, Isabel Cristina, Carvalho, J.M. Valério de

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

2015-08

RESUMO

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.

Documentos Relacionados

• A heuristic for the minimization of open stacks problem
• ANALYSIS OF MIXED INTEGER PROGRAMMING FORMULATIONS FOR SINGLE MACHINE SCHEDULING PROBLEMS WITH SEQUENCE DEPENDENT SETUP TIMES AND RELEASE DATES
• An integer programming model to limit hospital selection in studies with repeated sampling.
• NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM
• RESOLUÇÃO DE PROBLEMAS DE LOGÍSTICA FERROVIÁRIA UTILIZANDO PROGRAMAÇÃO INTEIRA