https://hal.science/hal-02443272Wang, ShijinShijinWangSchool of Economics & Management - Tongji UniversityWu, RuochenRuochenWuSchool of Economics & Management - Tongji UniversityChu, FengFengChuIBISC - Informatique, BioInformatique, Systèmes Complexes - UEVE - Université d'Évry-Val-d'Essonne - Université Paris-SaclaySchool of Economics and Management - Fuzhou UniversityYu, JianboJianboYuSchool of Mechanical Engineering - Tongji UniversityLiu, XinXinLiuGlorious Sun School of Business & Management - Donghua University [Shanghai]An improved formulation and efficient heuristics for the discrete parallel-machine makespan ScheLoc problemHAL CCSD2020Discrete locationMixed integer programming formulationPolynomial-time algorithmScheduling-location (ScheLoc) problem[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]Davesne, Frédéric2020-01-17 09:07:102023-01-24 03:35:072020-01-17 09:07:10enJournal articles10.1016/j.cie.2019.1062381The 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.