Exact and heuristic methods for the discrete parallel machine scheduling location problem

06/09/2020
by   Raphael Kramer, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset