Bi-objective scenario-guided swarm intelligent algorithms based on reinforcement learning for robust unrelated parallel machines scheduling with setup times

This paper addresses an uncertain unrelated parallel machine scheduling problem (UPMSP) with setup times, which is referred to the scenario UPMSP since uncertain processing times are described by a set of discrete scenarios. The bi-objective robust optimization formulation is established. Two objectives are to minimize the mean makespan and the worst-case makespan across all scenarios, which reflect solution optimality and solution robustness respectively. The contribution of this paper is three-fold. First, we propose the bi-objective robust optimization formulation under discrete scenarios for uncertain UPMSP. Second, two versions of swarm intelligent algorithms are developed by combining fruit fly optimization algorithm (FOA) framework and scenarioguided local search, which are performed based on two problem-specific neighborhood structures. The learning-scenario neighborhood structure is constructed by selecting single scenario using reinforcement learning. The united-scenario neighborhood structure is constructed by collecting all discrete scenarios. Third, an experiment was conducted to compare two developed algorithms with the state-of-the-art alternative algorithms. The computational results show that the developed algorithms are identically better than possible alternatives in terms of multi-objective metrics. Moreover, it is shown that the FOA algorithm with learning-scenarioneighborhood smell search is advantageous for the discussed problem.

Automated summary

This paper addresses an uncertain unrelated parallel machine scheduling problem (UPMSP) with setup times, and proposes a bi-objective robust optimization formulation to minimize the mean and worst-case makespan. Two versions of swarm intelligent algorithms are developed based on fruit fly optimization algorithm (FOA) framework and scenario-guided local search, and experimental results show their advantages. The contribution of this paper lies in the proposed formulation and algorithm approaches for the discussed problem.