Outranking-based multi-objective PSO for scheduling unrelated parallel machines with a freight industry-oriented application

Abstract

This paper presents Outranking-based Particle Swarm Optimisation (O-PSO) a novel metaheuristic to address the multi-objective Unrelated Parallel Machine Scheduling Problem. It is a particle swarm optimisation algorithm enriched with the preferences of the Decision Maker (DM), articulated in a fuzzy relational system based on ELECTRE III. Unlike other multi-objective metaheuristics, O-PSO searches for the Region of Interest (RoI) instead of approximating a sample of the complete Pareto frontier. The RoI is the subset consisting of those Pareto-efficient solutions that satisfy the outranking relations, that is, they are the best solutions in terms of the DM’s system of preferences. Therefore, O-PSO not only approximates the Pareto solutions but also supports multicriteria decision analysis of the schedules. The efficiency of O-PSO is validated on a benchmark of synthetic instances from the scientific literature, where the Wilcoxon rank-sum test provides statistical evidence that O-PSO offers high-quality solutions when compared with two state-of-the-art metaheuristics; specifically, O-PSO is capable of generating a greater proportion of solutions (on average, ranging from 7% to 14%) dominating those of the state-of-the-art algorithms, as well as finding more solutions (from 13% to 18%) that satisfy the DM’s preferences. O-PSO is also applied to a real-world case study in the transport industry to provide evidence for its applicability.