An exact framework for the discrete parallel machine scheduling location problem. (August 2021)

• Record Type: Journal Article
• Authors: Kramer, Raphael; Kramer, Arthur
• Is Part Of: Computers & operations research. Volume 132(2021)
• Publication Date: 2021-08
• Subjects: Scheduling -- Facility location -- Makespan -- Heuristics -- Exact framework; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105318
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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 multiple 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. Highlights: An exact framework for the discrete parallel machine ScheLoc problem is proposed. An arc-flow formulation and three heuristic methods are presented. All instances from the related literature are solved to optimality. A new set of instances is proposed.