Task Scheduling Based on a Hybrid Heuristic Algorithm for Smart Production Line with Fog Computing

Juan Wang, Di LiSensors 2019 · DOI

TL;DR

This paper tackles the challenge of efficiently scheduling tasks in smart manufacturing environments that utilize fog computing. They propose a novel hybrid heuristic (HH) algorithm that combines particle swarm optimization (PSO) and ant colony optimization (ACO) to minimize task completion time and energy consumption, outperforming existing methods.

What Problem Does This Paper Address?

The increasing adoption of the Industrial Internet of Things (IIoT) and smart manufacturing has led to a surge in data and real-time processing demands. While cloud computing offers vast resources, its inherent latency makes it unsuitable for many time-sensitive industrial applications. Fog computing, with its distributed architecture closer to the edge, offers a solution by providing low-latency services. However, a significant challenge in fog computing for smart manufacturing is the heterogeneity of both the tasks (e.g., real-time fault detection vs. computationally intensive scheduling) and the fog nodes themselves (varying processing power, storage, and network capabilities). This heterogeneity makes task scheduling – deciding which fog node should process which task to minimize delay and energy consumption while maximizing performance metrics like production efficiency – a complex, NP-hard problem. Existing solutions often struggle to balance these competing objectives across diverse environments.

Methods

The core of this paper is the development of a Hybrid Heuristic (HH) algorithm for task scheduling. This HH algorithm is designed to leverage the strengths of two established metaheuristic algorithms:

  • Improved Particle Swarm Optimization (IPSO): The authors adapt the standard PSO algorithm for the discrete nature of the task scheduling problem by introducing a discrete particle swarm initialization and updating mechanism. They also incorporate an adaptive inertia weight and contraction factor to enhance convergence speed and accuracy.
  • Improved Ant Colony Optimization (IACO): The IACO algorithm is enhanced by improving its heuristic information and path transition probability. The heuristic information is modified to consider both local and global computational overheads, and a regulatory factor is introduced to the transition probability to prevent premature convergence to local optima.

The HH algorithm works by first using the IPSO to quickly find an initial optimal solution. This solution then serves as the initial pheromone distribution for the IACO algorithm, which refines it to achieve a more precise optimal solution. This two-stage approach aims to combine the fast search speed of PSO with the high precision of ACO.

Datasets

Not discussed in the paper. The authors developed a simulation environment in MATLAB to evaluate their proposed algorithm.

Key Insights and Ideas

  • Heterogeneity is the Key Challenge: The paper effectively highlights that the diverse nature of tasks and fog nodes in smart manufacturing is the primary obstacle to efficient task scheduling.
  • Hybridization for Synergy: The core idea of combining IPSO and IACO is to create a synergistic effect, where the strengths of one algorithm compensate for the weaknesses of the other. IPSO provides a quick initial solution, guiding IACO towards a better final result.
  • Balancing Competing Objectives: The objective function is carefully formulated to minimize both task completion time and energy consumption, acknowledging that these are often conflicting goals. The use of weighted satisfaction factors (Wit and Wie) for delay and energy further emphasizes this balance.
  • Discrete Optimization is Crucial: Recognizing that task scheduling is a discrete problem, the authors' adaptation of PSO to a discrete version is a critical methodological step.

Key Results

The proposed Hybrid Heuristic (HH) algorithm demonstrated superior performance across three key metrics compared to three other strategies (IPSO, IACO, and Round-Robin (RR)):

  • Completion Time: HH achieved the lowest completion time, consistently outperforming IPSO, IACO, and significantly outperforming RR, especially as the number of tasks increased.
  • Energy Consumption: HH also resulted in the lowest energy consumption, which is directly correlated with its minimal completion time.
  • Reliability: HH exhibited the highest reliability, meaning it had the highest success rate in completing tasks within their maximum tolerance time and available residual energy. This reliability remained high even as the number of tasks increased or maximum tolerance times varied.

Limitations and Future Work

  • Limitations:
    • The paper assumes that tasks are independent and cannot be interrupted, which might not always hold true in real-world scenarios.
  • The mobility of terminal equipment is not considered in the task execution process.
  • The simulation environment is used for evaluation, and real-world deployment challenges are not explicitly addressed.
  • Future Work: The authors suggest extending their research to include task clustering and fog node clustering for task scheduling in fog computing. This would likely address scenarios where tasks can be grouped for more efficient processing or where fog nodes can be logically grouped to optimize resource utilization.

Summary updated

Abstract

Fog computing provides computation, storage and network services for smart manufacturing. However, in a smart factory, the task requests, terminal devices and fog nodes have very strong heterogeneity, such as the different task characteristics of terminal equipment: fault detection tasks have high real-time demands; production scheduling tasks require a large amount of calculation; inventory management tasks require a vast amount of storage space, and so on. In addition, the fog nodes have different processing abilities, such that strong fog nodes with considerable computing resources can help terminal equipment to complete the complex task processing, such as manufacturing inspection, fault detection, state analysis of devices, and so on. In this setting, a new problem has appeared, that is, determining how to perform task scheduling among the different fog nodes to minimize the delay and energy consumption as well as improve the smart manufacturing performance metrics, such as production efficiency, product quality and equipment utilization rate. Therefore, this paper studies the task scheduling strategy in the fog computing scenario. A task scheduling strategy based on a hybrid heuristic (HH) algorithm is proposed that mainly solves the problem of terminal devices with limited computing resources and high energy consumption and makes the scheme feasible for real-time and efficient processing tasks of terminal devices. Finally, the experimental results show that the proposed strategy achieves superior performance compared to other strategies.
BibTeX
@inproceedings{wang2019task,
  author = {Juan Wang and Di Li},
  title = {{Task Scheduling Based on a Hybrid Heuristic Algorithm for Smart Production Line with Fog Computing}},
  booktitle = {Sensors},
  year = {2019},
  doi = {10.3390/s19051023},
}
Figure