The Multi-Period Service Scheduling Problems: A new model and heuristic approaches of relax-and-fix and fix-and-optimize



Heuristic, Multi-period servisse scheduling, Relax-and-fix, Fix-and-optimize, Scheduling


Multi-Period Service Scheduling Problem – MSSP is descibed as a category of problems that arise in the context of scheduling services. In these problems, customers have a periodic service to be attended, a finite number of times, within the time horizon. The Multi-Period Multi-Service Scheduling Problem – MMSSP is presented as an alternative formulation for MSSP, in which the resolution of an MMSSP is equivalent to the resolution of multiple MSSP, demonstrating the complexity of solving this pattern. The presented formulation can lead several applications in different areas. To solve this new pattern, the Relax-and-Fix and Fix-and-Optimize strategies are used. In these heuristics, part of the entire variables are fixed and/or relaxed interactively. To assess the efficiency of the strategies, a set of 150 small, medium and large instances are generated and resolved. The results of extensive experiments demonstrate that heuristics produce quality solutions, highlighting a good balance between optimization and computational time.

Author Biography

Cassius Tadeu Scarpin, Universidade Federal do Paraná

Cassius Tadeu Scarpin é Doutor (2012) e Mestre (2007) em Pesquisa Operacional pelo Programa de Pós-Graduação em Métodos Numéricos em Engenharia, área de concentração: Programação Matemática, na Universidade Federal do Paraná. Engenheiro de Produção (2010) e Licenciado em Matemática (2002) pela mesma universidade. Atualmente ocupa o cargo de Professor Adjunto no Departamento de Administração Geral e Aplicada (DAGA) da Universidade Federal do Paraná
(UFPR) e coordena o Grupo de Pesquisa de Tecnologia Aplicada à Otimização (GTAO).


Bookmark and Share