Beam Search Algorithms for Minimizing Tool Switches on a Flexible Manufacturing System - Senne, Edson Luiz França [UNESP]; Yanasse, Horacio Hideki (World Scientific and Engineering Acad and Soc, 2009)
In the minimization of tool switches problem we seek a sequence to process a set of jobs so that the number of tool switches required is minimized. In this work different variations of a heuristic based on partial ordered job sequences are implemented and evaluated. All variations adopt a depth first strategy of the enumeration tree. The computational test results indicate that good results can be obtained by a variation which keeps the best three branches at each node of the enumeration tree, and randomly choose, among all active nodes, the next node to branch when backtracking.
Keywords: Minimization of tool switches; Partial ordering heuristics; Beam search; Flexible manufacturing systems; Combinatorial optimization