Minimizing Processing Time with Walk-Based Job Assignment in Union Graphs

In this paper, we introduce a union graph-based approach to optimize job scheduling for machines with overlapping capabilities. A union graph is used to model the relationships between jobs and machines, where vertices represent subsets of jobs, and edges indicate shared job capabilities between machines. We develop an algorithm that selects jobs based on minimal processing time by performing walks on the union graph, systematically reducing the overall processing time. The proposed method is illustrated through examples, demonstrating its effectiveness in various scheduling scenarios. Our results show that this approach enhances efficiency in job assignments, offering a novel perspective on handling shared machine capabilities. This study contributes to the field of optimization by leveraging the structure of union graphs for improved job scheduling.