Mathematical programming modeling of the Response Time Variability Problem

The Response Time Variability Problem (RTVP) is a scheduling problem that has recently been defined in the literature. The RTVP has a broad range of real-life applications from manufacturing to services and information technology. A previous study developed a position exchange heuristic to apply to initial sequences for the RTVP, and a MILP (Mixed Integer Linear Programming) to obtain optimal solutions with a practical limit of 25 units to be scheduled. This paper aims to improve the best mathematical programming model developed thus far in order to solve larger instances up to 40 units to optimality. The contribution of this paper is 4-fold: (i) larger instances can be solved to optimality by the off the shelf standard software; (ii) the new optimal solutions of the RTVP can be used to compare the results of heuristic procedures; (iii) the importance of modeling is demonstrated, as well as the huge impact that reformulation, redundant constraints and the elimination of symmetries have on the efficiency of MILPs is clearly established; finally (iv) a challenge to develop a customized optimization algorithm to rival the MILP solution efficiency for the RTVP is put forward.