Customer order scheduling problem to minimize makespan with sequence-dependent setup times

Abstract

In this paper, we study a variant of the customer order scheduling problem when sequence-dependent setup times cannot be ignored. The performance measure adopted is the makespan minimization. The existence of sequence-dependent setup times makes this problem to be NP-hard. Furthermore, the solution encoding usually employed for other variants of the customer order scheduling problem does not guarantee finding optimal solutions. For this problem, we present some properties and develop two Mixed Integer Linear Programming (MILP) formulations to analyze the structure of the solutions. Using these properties and models, we propose two matheuristics based on fixing some integer decision variables in the MILP models, denoted as Fixed Variable List Algorithm (FVLA) and Clustering Sequence Algorithm (CSA), respectively. The computational experiments carried out prove the ability of these matheuristics to find high-quality solutions in reasonable CPU time. More specifically, the FVLA matheuristic stands out as the most efficient for the problem.