Unrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness. (January 2023)

• Record Type: Journal Article
• Authors: Maecker, Söhnke; Shen, Liji; Mönch, Lars
• Is Part Of: Computers & operations research. Volume 149(2023)
• Publication Date: 2023-01
• Subjects: Parallel machine scheduling -- Total weighted tardiness -- Delivery times -- Mixed integer linear programming -- Variable neighborhood search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105999
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This paper addresses an unrelated parallel machine scheduling problem with job-machine-dependent delivery times and eligibility constraints motivated by a distributed manufacturing environment. The objective is total weighted tardiness minimization. We present a mixed integer linear programming (MILP) formulation and conduct an analysis of the scheduling problem to derive precedence properties that can be integrated in local search procedures to increase computational efficiency. We implement a variable neighborhood search (VNS) algorithm for the problem at hand and examine the effect of integrating the properties on the performance. The tests show that the theoretical findings can reduce computational effort significantly. Furthermore, we propose another heuristic approach based on the Apparent Tardiness Cost rule and a memetic biased random-key genetic algorithm. In experiments, we compare the MILP and (meta-)heuristics on a large set of randomly generated problem instances. The VNS procedure outperforms the other algorithms. Highlights: We address an unrelated parallel machine scheduling problem in distributed manufacturing. Our objective is to minimize the total weighted tardiness. A mixed integer linear programming formulation is proposed. Theoretical properties are integrated into a variable neighborhood search algorithm. The variable neighborhood search reaches optima for small instances and outperforms a genetic algorithm and a heuristic.