VNS METAHEURISTIC APPLIED TO A FAIR SEQUENCING PROBLEM

The Minmax Response Time Problem (mRTP) is a fair sequencing problem that emerges whenever tasks, customers, products, or events need to be sequenced in a way that minimizes the variability of the expected time between successive allocations of scarce resources. With applications ranging from scheduling medical shifts to maintaining industrial machines, mRTP has not been explored as much in the literature when compared to other tight sequence problems. This work proposes specialized data structures for mRTP, which, together with a proposed algorithm based on the VNS metaheurist, obtained the best solutions for the set of reference instances in the literature so far.