Article ID: | iaor20072274 |
Country: | United States |
Volume: | 18 |
Issue: | 1 |
Start Page Number: | 55 |
End Page Number: | 73 |
Publication Date: | Jan 2006 |
Journal: | International Journal of Flexible Manufacturing Systems |
Authors: | Azizolu Meral, Karakayal brahim |
Keywords: | production: FMS |
In this study, we address a job sequencing and tool switching problem arising in flexible manufacturing systems. We consider the single machine problem of minimizing total flow time. We prove that the problem is NP-hard in the strong sense and show that the tool switching problem is polynomially solvable for a given sequence. We propose a branch-and-bound algorithm whose efficiency is improved by precedence relations and several lower and upper bounding techniques. Our computational results reveal that the branch and bound approach produces optimal solutions in reasonable times for moderate sized problems. Our upper bounds produce very satisfactory solutions; therefore they can be an attractive alternative to solve larger sized problems.