An improved formulation and efficient heuristics for the discrete parallel-machine makespan ScheLoc problem

作     者：Wang, Shijin Wu, Ruochen Chu, Feng Yu, Jianbo Liu, Xin 

作者机构：Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Univ Paris Saclay Univ Evry Lab IBISC F-91025 Evry France Fuzhou Univ Sch Econ & Management Fuzhou 350116 Peoples R China Tongji Univ Sch Mech Engn Shanghai 200092 Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China 

出 版 物：《COMPUTERS & INDUSTRIAL ENGINEERING》 (计算机与工业工程)

年 卷 期：2020年第140卷

页      面：106238-106238页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China (NSFC) [71571135, 71971155] Fundamental Research Funds for the Central Universities 

主　　题：Scheduling-location (ScheLoc) problem Discrete location Mixed integer programming formulation Polynomial-time algorithm 

摘      要：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 Healer 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.