An improved formulation and efficient heuristics for the discrete parallel-machine makespan ScheLoc problem. (February 2020)

• Record Type: Journal Article
• Authors: Wang, Shijin; Wu, Ruochen; Chu, Feng; Yu, Jianbo; Liu, Xin
• Is Part Of: Computers & industrial engineering. Volume 140(2020)
• Publication Date: 2020-02
• Subjects: Scheduling-location (ScheLoc) problem -- Discrete location -- Mixed integer programming formulation -- Polynomial-time algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.106238
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: This paper revisits the discrete parallel-machine makespan ScheLoc problem. A network-flow-based new MIP programming model is formulated. Two formulation-based heuristics and a polynomial-time algorithm are designed. Computational results demonstrate the efficacy of the proposed methods. Abstract: The scheduling-location (ScheLoc) problem is a new and interesting field, which is a combination of two complex problems: the machine-location problem and the scheduling problem. Owing to the NP-hardness of both the component problems, the ScheLoc problem is naturally NP-hard. This study investigates a deterministic and discrete parallel-machine ScheLoc problem for minimizing the makespan. A new mixed integer programming formulation based on network flow problems is proposed. Two formulation-based heuristics are developed for small-scale problems. Subsequently, a polynomial-time heuristic is designed for efficiently solving large-scale problems. Extensive computational experiments are conducted for 1450 benchmark problem instances with different scales. The computational results show that our model can solve more problem instances to optimality than that in Heßler and Deghdak (2017) in the same time limit. In addition, the heuristics can yield near-optimal solutions for small-scale problems in a short time. The polynomial-time algorithm outperforms most of the state-of-the-art methods for the large-scale problems in terms of both the efficiency and solution quality.