NS-BRKGA for Multi-Objective Time- and Machine-Dependent Scheduling Problem

The Time- and Machine-Dependent Scheduling Problem (TMDSP) models the large-scale scheduling of Firmware-Over-The-Air (FOTA) updates for fleets of connected devices under time-varying resource constraints.

The original TMDSP minimizes only the total completion time, which can lead to unbalanced schedules with a high makespan.

We propose a multi-objective extension, called MOTMDSP, that simultaneously minimizes makespan and total completion time.

Our approach is based on a Non-dominated Sorting Biased Random-Key Genetic Algorithm (NS-BRKGA) with a specialized decoder for the MOTMDSP.

We evaluate NS-BRKGA on realistic large-scale instances derived from FOTA scenarios for connected vehicles.

In the experiments, the method produces high-quality Pareto fronts and outperforms several reference multi-objective algorithms, including the Non-dominated Sorting Genetic Algorithm II (NSGA-II), providing operators with a wide range of schedules that reflect different trade-offs between the objectives.