A bottleneck-based beam search for job scheduling in a flexible manufacturing system

This paper studies job-scheduling methods for flexible manufacturing systems (FMSs). Routeing flexibility is a feature that distinguishes FMS scheduling from a classic general jobshop problem. The paper formalizes the problem as a flexible jobshop problem and introduces a flexibility index to measure the extent of routeing flexibility. Based on a procedure to identify a potential bottleneck machine, it develops a beam search method for approximately solving the problem. The proposed method yields a significantly shorter makespan than that of the commonly used shortest processing-time dispatching rule, and it properly exploits the added flexibility in routeing. The computational effort required also is small enough to enable practical implementation.