A Branch and Bound Algorithm for Scheduling of Flexible Manufacturing Systems

Flexible manufacturing systems (FMSs), which can easily adapt to changes in job types, have been widely used in manufacturing areas. Scheduling of FMSs is a variant of a flexible job shop with transport robots and no buffer, and it is extremely hard as it involves determining the job processing sequence on machines and the sequence of robot tasks, with various jobs with different processing flows and the risk of deadlocks. Due to these characteristics, many existing studies have focused on developing heuristic algorithms. However, an optimal solution is still crucial to minimize FMSs makespan. Therefore, we propose a mixed integer programming (MIP) and a branch and bound (B & B) algorithm with a timed Petri net (TPN) to achieve optimal scheduling of FMSs. FMSs are first modeled with a TPN, and tight lower bounds are proposed based on bottleneck machines and sophisticated ready times. In addition, the search space is effectively reduced by the transition index marking (TIM)-based dominance rule and various deadlock prevention conditions based on the TPN. The experimental results show that our proposed B & B algorithm outperforms mathematical formulation and previous algorithms in various FMS instances

Automated summary

Flexible Manufacturing Systems (FMSs) are widely used in manufacturing areas and require a scheduling process that is extremely difficult due to various job types and the risk of deadlocks. Many existing studies focus on developing heuristic algorithms, but an optimal solution is crucial to minimize FMSs makespan. Therefore, we propose a mixed integer programming (MIP) and a branch and bound (B & B) algorithm with a timed Petri net (TPN) to achieve optimal scheduling of FMSs. Experimental results show that our proposed B & B algorithm outperforms mathematical formulations and previous algorithms in various FMS instances.