Minimization of the Number of Tool Magazine Setups on Automated Machines: A Lagrangean Decomposition Approach

Meltem Denizel ()
Additional contact information
Meltem Denizel: Graduate School of Management, Sabanc(iota) University, Orhanl(iota)/Tuzla, Istanbul 34956, Turkey

Operations Research, 2003, vol. 51, issue 2, 309-320

Abstract: This paper addresses the parts-grouping problem that arises in automated manufacturing environments where appropriate cutting tools must be loaded on Computer Numerical Control (CNC) machines to process a variety of parts. Since tool-loading times may be considerably long and reduce available machine processing times, it is important to find a mutually exclusive grouping of parts such that the total number of tools required by each group does not exceed the tool-magazine capacity and the number of groups is minimized. We present an integer programming formulation of the problem and develop a lower bounding procedure using Lagrangean decomposition. We then introduce valid inequalities to improve the quality of the lower bounds obtained from the relaxed problem. Our solution procedure for the lower bounding problem requires only one set of Lagrange multipliers, which reduces the required computational effort significantly. We also modify the lower bound solution heuristically to find an upper bound. The lower and upper bounds are then incorporated in a branch-and-bound scheme to search for an optimal solution. Our computational comparisons with the best existing solution procedures from the literature show that our procedure performs better on average, and for the majority of test problems within the scope of our experiments.

Keywords: Programming; integer; algorithms; relaxation: bin-packing problem with sharing; Lagrangean decomposition; Manufacturing; automated systems: tool-loading decision (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.2.309.12784 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:2:p:309-320

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().