Integrated Scheduling Algorithm Based on the Improved Floyd Algorithm

Yingxin Wei, Wei Zhou, Zhiqiang Xie, Ming Sun, Zhenjiang Tan, Wangcheng CaoSymmetry 2025 · DOI

TL;DR

This paper introduces an Integrated Scheduling Algorithm Based on the Improved Floyd Algorithm (ISA-IFA) to tackle the complex scheduling challenges of asymmetric tree-like product structures. By enhancing the Floyd algorithm with a path-weighted strategy and a focus on leaf node optimization, ISA-IFA significantly reduces product completion time and improves equipment utilization.

What Problem Does This Paper Address?

Modern manufacturing relies heavily on intelligent systems to manage complex production processes. For products with tree-like structures, especially those with asymmetric dependencies (where components don't have uniform relationships), traditional scheduling methods struggle. These asymmetries lead to hierarchical complexities, varying degrees of dependence, and intricate production sequences. Existing approaches often overlook the potential of leaf nodes (tasks at the end of a branch) which, despite low priority, can be scheduled earlier. This oversight can lead to underutilized parallel processing capabilities and exacerbate delays along critical paths, ultimately hindering production efficiency and increasing equipment idle time.

Methods

The core of this paper is the Integrated Scheduling Algorithm Based on the Improved Floyd Algorithm (ISA-IFA). The authors adapt the classic Floyd algorithm, traditionally used for finding shortest paths in graphs, for scheduling. Key innovations include:

  • Improved Floyd Algorithm: The algorithm modifies the Floyd algorithm to use the processing time of immediate successor processes as path weights. This allows for a more accurate representation of dependencies in the scheduling context.
  • Path-Weighted Strategy: This strategy, built upon the improved Floyd algorithm, assigns weights to paths within the process tree. It prioritizes paths that lead to leaf nodes with lower hierarchical priority, aiming to leverage their scheduling flexibility.
  • Scheduling Advantage Strategy: This strategy defines the earliest possible start time for a process on a given machine, considering process constraints.
  • Audit Strategy: This approach, building on the scheduling advantage, checks the feasibility of process start times by ensuring they don't precede the completion of their immediate predecessors, thus preventing time conflicts.
  • Dynamic Pruning: The algorithm iteratively prunes the process tree, creating subtrees and recalculating path weights. This helps in managing complexity and identifying optimal scheduling paths, especially in asymmetric structures.

The algorithm's complexity is reduced from the traditional O(n³) of Floyd's algorithm to O(n²) through these optimizations.

Datasets

The paper uses a randomly generated complex product process tree (Product A) for demonstration and comparative analysis. This process tree consists of 22 processes and four machines. For broader validation, the authors also generated four sets of 40 product process trees with varying scales (20, 50, 100, and 200 processes) and structures (symmetric and asymmetric) for comparative experiments.

Key Insights and Ideas

  • Leaf Node Potential: The most significant insight is the recognition and exploitation of the scheduling advantage offered by leaf nodes. By prioritizing these nodes, the algorithm can unlock parallelism and reduce overall completion time, especially in asymmetric structures.
  • Floyd Algorithm Adaptation: Successfully adapting a graph-based shortest path algorithm like Floyd's for complex scheduling problems demonstrates the versatility of established algorithms when creatively applied.
  • Symmetry vs. Asymmetry Handling: The ISA-IFA shows a strong ability to handle both symmetric (regular, balanced) and asymmetric (irregular, complex dependencies) process structures, a critical capability for real-world manufacturing.
  • Reduced Idle Time: The combined strategies effectively balance workloads, leading to significantly reduced equipment idle time and improved utilization.

Key Results

  • Reduced Makespan: For the example complex product A, the ISA-IFA achieved a total processing time of 27 working hours, outperforming other algorithms (ISA-NWCOG: 28 hours, TISA-CCSP: 31 hours, RCISA-CHSO: 28 hours).
  • Improved Equipment Utilization: The ISA-IFA achieved an equipment utilization rate of 55.9%, which was 2.3%, 9.5%, and 0.6% higher than ISA-NWCOG, TISA-CCSP, and RCISA-CHSO, respectively.
  • Scalability and Stability: Experimental results across varying operation scales (20 to 200 processes) showed that ISA-IFA consistently achieved the least processing time and maintained a high optimal solution ratio, demonstrating good stability and performance.

Limitations and Future Work

The authors acknowledge several limitations:

  • Ultra-Large Scales: The algorithm's processing time can escalate significantly at extremely large scales.
  • Initialization Sensitivity: The algorithm shows some sensitivity to the initialization of sparse process trees.
  • Multi-Dimensional Constraints: The current model does not fully integrate multi-dimensional constraints such as personnel and materials, which limits its direct application in complex industrial scenarios.

Future work suggested includes:

  • Integrating heterogeneous resources (personnel, materials) into the scheduling model.
  • Developing a multi-objective co-optimization model to balance green scheduling objectives with efficiency.
  • Exploring mechanisms for trade-offs between these objectives.
  • Improving adaptability for extreme asymmetric structures and distributed scalability for ultra-large-scale symmetric trees.

Summary updated

BibTeX
@article{wei2025integrated,
  author = {Yingxin Wei and Wei Zhou and Zhiqiang Xie and Ming Sun and Zhenjiang Tan and Wangcheng Cao},
  title = {{Integrated Scheduling Algorithm Based on the Improved Floyd Algorithm}},
  journal = {Symmetry},
  year = {2025},
  doi = {10.3390/sym17050682},
}
Figure