Exact and metaheuristic approaches for identical parallel machine scheduling with a common server and sequence-dependent setup times

Abstract

We consider the problem of scheduling parallel machines with a common server and sequence-dependent setup times, whose objective is to minimize the makespan. In this case, the common server, which can be a machine, individual or a team, is responsible for performing the setup operations. Therefore, there must be no conflicts while conducting them. An arc-time-indexed formulation is proposed for the problem, as well as an algorithm based on the metaheuristic iterated local search that makes use of an improved decoding algorithm. Computational experiments were carried out on 150 instances involving up to 100 jobs ranging from 2 to 10 machines. The results obtained suggest that the methods developed were capable of finding highly competitive solutions when compared to those achieved by existing approaches.

Keywords:

• Scheduling
• common server
• arc-time-indexed formulation
• iterated local search

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This research was partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), grants 428549/2016-0 and 307843/2018-1, and by Comissão de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) – Finance Code 001.