Learning-Aided Evolutionary Algorithm for Solving Energy-Minimized Deadline-Constrained Task Scheduling Problem in Human-Cyber-Physical Systems

This work addresses an energy-minimized deadline-constrained task scheduling problem in human-cyber-physical systems. It consists of three subproblems: processor allocation, task sequencing, and processor frequency scaling. A Learning-aided Evolutionary Algorithm (LEA) is proposed to efficiently find its reliable and high-quality solutions. It incorporates a bidirectional long short-term memory network-embedded autoencoder trained via end-to-end self-supervised learning. The model extracts the interconnections among the three strongly-coupled subproblems, enabling effective global search in a low-dimensional feature space. A parallel framework with two co-evolved subpopulations, one using the autoencoder and another undergoing regular evaluation in the original search space, is constructed. To balance LEA's exploration and exploitation, a deep reinforcement learning-based search operator selection scheme is introduced, using a novel feedback-based reward function to guide operator selection for each subpopulation. Numerical experiments demonstrate that LEA surpasses several recently developed methods in finding high-quality schedules in a reasonable time. Note to Practitioners - In a human-cyber-physical system, heuristics are commonly used to solve task scheduling problems. However, fast dispatching rules tend to perform poorly. Evolutionary algorithms can identify relatively high-quality schedules but are highly time-consuming, especially for population-based methods that iteratively evaluate fitness functions. To balance computational burden and solution quality, our idea is to combine two machine learning methods with evolutionary algorithms. First, a self-supervised autoencoder enhances global search capability by reducing the complexity of the search space. Second, a deep reinforcement learning-based operator selection scheme balances exploration and exploitation. This hybrid approach enables engineers to find high-quality schedules for the considered problems in a short time. Theoretical analysis and experimental results demonstrate that our proposed method outperforms its competitive peers.