A new branch and bound algorithm for loading problems in flexible manufacturing systems

Loading problems in flexible manufacturing systems involve assigning operations for selected part types and their associated tools to machines or machine groups. One of the objectives might be to maximize the expected production rate (throughput) of the system. Because of the difficulty in dealing with this objective directly, a commonly used surrogate objective is the closeness of the actual workload allocation to the continuous workload allocation that maximizes throughput. The authors test several measures of closeness and discuss correlations between these measures and throughput. Using the best measure, they show how to modify an existing branch and bound algorithm which was developed for the case of equal target workloads for all machine groups to accommodate unequal target workloads. The authors also develop a new branch and bound algorithm which can be used for both types of problems. The efficiency of the algorithm in finding optimal solutions is achieved through the application of better branching rules and improved dominance results. Computational results on randomly generated test problems indicate that the new algorithm performs well.