Problem Definition and Optimization Method for Bipartite Graph Scheduling

Abstract

Bipartite graphs can describe various systems in real world. In this study, we define a new problem class for optimizing the cost or profit associated with state changes in systems represented by bipartite graphs and propose a heuristic approach based on a fast greedy algorithm. We present the problem setting of the network circuit and device removal problem as a real-world problem and demonstrate the superiority of the proposed method for large-scale applications. This study contributes to the understanding and solving of various optimization problems in industrial fields, providing a comprehensive approach to cost (profit) optimization problems associated with state changes in systems represented by bipartite graphs.

Keywords

• Bipartite graph
• combinatorial problem
• scheduling optimization
• sequence problem