  The discrete parallel machine makespan scheduling location (ScheLoc) problem
is an integrated combinatorial optimization problem that combines facility
location and job scheduling. The problem consists in choosing the locations of
$p$ machines among a finite set of candidates and scheduling a set of jobs on
these machines, aiming to minimize the makespan. Depending on the machine
location, the jobs may have different release dates, and thus the location
decisions have a direct impact on the scheduling decisions. To solve the
problem, it is proposed a new arc-flow formulation, a column generation and
three heuristic procedures that are evaluated through extensive computational
experiments. By embedding the proposed procedures into a framework algorithm,
we are able to find proven optimal solutions for all benchmark instances from
the related literature and to obtain small percentage gaps for a new set of
challenging instances.
