Estudo poliedral do problema da variabilidade do tempo de resposta

Abstract

Given a set of copy of symbols and a set of slots, the Response Time Variability Problem (RTVP) is NP-hard and attempts to minimize the variability of the total response time, attributing to each slot one and only one copy of the symbol and, along, attributing each symbol in one and only one slot. This problem has a great number of applications, varying from automobile production on an assembly line to the collect of residues from a recipient in many hospital rooms. This work presents a polyhedral study associated to RTVP, describing it in linear equations and inequations. From this perspective, a descriptive research was done, in relation to the objectives, with bibliographic procedures. Furthermore, a description in a mathematical formulation was adapted based on Integer Linear Programming and it was compared to an exact method already consolidated on the literature, thus characterizing it as a research of applied nature to a quantitative approach. The computational results show that the proposed model worked well, highlighting the possibility that the inequalities really are polytope facets.