Journal
INFORMS JOURNAL ON COMPUTING
Volume 34, Issue 2, Pages 1048-1069Publisher
INFORMS
DOI: 10.1287/ijoc.2021.1113
Keywords
ScheLoc; MILP; logic-based Benders decomposition; combinatorial Benders cut; optimality cut
Ask authors/readers for more resources
This paper investigates the discrete parallel machine scheduling and location problem and proposes new mixed-integer linear programs and a logic-based Benders decomposition algorithm for addressing the problem. The proposed models and algorithms outperform existing approaches according to computational experiments.
We investigate the discrete parallel machine scheduling and location problem, which consists of locating multiple machines to a set of candidate locations, assigning jobs from different locations to the located machines, and sequencing the assigned jobs. The objective is to minimize the maximum completion time of all jobs, that is, the makespan. Though the problem is of theoretical significance with a wide range of practical applications, it has not been well studied as reported in the literature. For this problem, we first propose three new mixed-integer linear programs that outperform state-of-the-art formulations. Then, we develop a new logic-based Benders decomposition algorithm for practical-sized instances, which splits the problem into a master problem that determines machine locations and job assignments to machines and a subproblem that sequences jobs on each machine. The master problem is solved by a branch-and-cut procedure that operates on a single search tree. Once an incumbent solution to the master problem is found, the subproblem is solved to generate cuts that are dynamically added to the master problem. A generic no-good cut is first proposed, which is later improved by some strengthening techniques. Two optimality cuts are also developed based on optimality conditions of the subproblem and improved by strengthening techniques. Numerical results on small-sized instances show that the proposed formulations outperform state-of-the-art ones. Computational results on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations demonstrate the effectiveness and efficiency of the algorithm compared with current approaches. Summary of Contribution: This paper employs operations research methods and computing techniques to address an NP-hard combinatorial optimization problem: the parallel discrete machine scheduling and location problem. The problem is of practical significance but has not been well studied in the literature. For the problem, we formulate three novel mixed-integer linear programs that outperform state-of-the-art formulations and develop a new logic-based Benders decomposition algorithm. Extensive computational experiments on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations are conducted to evaluate the performance of the proposed models and algorithms.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available