The unrelated parallel machine scheduling problem with sequence and machine dependent setup times and a shared resource without overlap

This paper deals with minimizing the makespan in unrelated parallel machines with sequence and machine-dependent setup times involving a non-overlapping shared resource. The shared resource corresponds to an operator that can service one machine at a time to perform setup operations when it is necessary to change the type of job to be processed. We develop two Mixed Integer Linear Programming (MILP) formulations and a metaheuristic algorithm that combines an Iterated Greedy scheme with Variable Neighborhood Descent (IG + VND). Both approaches were compared with existing models and algorithms from the literature. The results indicate that the proposed formulation outperforms previous models present in the literature in instances of up to 14 jobs and 4 machines. The algorithm reported average deviations within 5 % of the solutions obtained by the model, but performed up to 3 orders of magnitude faster. Similarly, the proposed IG+VND outperformed the other algorithms in the literature, particularly for instances of up to 40 jobs and 6 machines, and obtained solutions for instances of up to 60 jobs and up to 6 machines. • We study the unrelated parallel machine problem with sequence- and machine dependent setups and a shared resource. • We present two mathematical formulations to solve the problem. • Our models outperform existing formulations in the literature. • We present an algorithm to efficiently solve instances of up to 60 jobs and 6 machines. • We propose a set of instances that could be used for further comparison.