Journal Article

Distributed Integrated Scheduling Algorithm for Identical Two-Workshop Based on the Improved Bipartite Graph

Zhao, Jinghua, Xie, Zhiqiang, Wei, Yingxin, Zhou, Wei, Tan, Zhenjiang

2025

Overview

To address the issue of further collaboratively optimizing process continuity, time cost, and equipment utilization in identical two-workshop distributed integrated scheduling, an identical two-workshop distributed integrated scheduling algorithm based on the improved bipartite graph (DISA-IBG) is proposed. The method introduces an improved bipartite graph cyclic decomposition strategy that incorporates both the topological characteristics of the process tree and the dynamic resource constraints of the workshops. Based on the resulting substrings, a multi-substring weight scheduling strategy is constructed to achieve a systematic evaluation of substring priorities. Finally, a substring pre-allocation strategy is designed to simulate the scheduling process through virtual allocation, which enables dynamic adjustments to resource allocation schemes during the actual scheduling process. Experimental results demonstrate that the algorithm reduces the total product makespan to 37 h while improving the overall equipment utilization to 67.8%, thereby achieving the synchronous optimization of \"shorter processing time and higher equipment efficiency.\" This research provides a feasible scheduling framework for intelligent sensor-enabled manufacturing environments and lays the foundation for data-driven collaborative optimization in cyber-physical production systems.

• Publisher: MDPI AG,Multidisciplinary Digital Publishing Institute (MDPI)
• Subject: Algorithms / Collaboration / Critical path / Decision making / Decomposition / distributed integrated scheduling algorithm / Efficiency / Genetic algorithms / improved bipartite graph / Manufacturing / Methods / multi-substring / Neighborhoods / Optimization / Outsourcing / Scheduling / sensor-enabled manufacturing / Workshops / Workshops (Educational programs)