The tool transporter movements problem in flexible manufacturing systems

Karzan F. K., AZİZOĞLU M.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, vol.46, no.11, pp.3059-3084, 2008 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 46 Issue: 11
  • Publication Date: 2008
  • Doi Number: 10.1080/00207540601070135
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.3059-3084
  • Keywords: flexible manufacturing systems, tool transporter movements, branch-and-bound, beam search, TOTAL COMPLETION-TIME, SWITCHING PROBLEM, MACHINE, MINIMIZATION, NUMBER, PERFORMANCE, HEURISTICS, MODELS
  • Middle East Technical University Affiliated: Yes


We consider a job sequencing and tool transporter movements problem on a single flexible machine with limited tool magazine capacity. A tool transporter having limited capacity is used in transporting the tools between the machine and tool crib area. Our aim is to minimize the number of the tool transporter movements. We present several lower and upper bounds, propose a Branch-and-Bound algorithm and a Beam Search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized instances with 25 jobs and 25 tools. For large-sized problem instances, Beam Search provides high quality solutions very quickly. Finally, we address the problem of minimizing the total flow time.