Minimization of the number of tool magazine setups on automated machines: a lagrangean decomposition approach

Denizel, Meltem (2003) Minimization of the number of tool magazine setups on automated machines: a lagrangean decomposition approach. Operations Research, 51 (2). pp. 309-320. ISSN 0030-364X (Print) 1526-5463 (Online)

Full text not available from this repository. (Request a copy)


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
Item Type: Article
Uncontrolled Keywords: Programming, integer, algorithms, relaxation: bin-packing problem with sharing; Lagrangean decomposition; Manufacturing, automated systems: tool-loading decision.
Subjects: Q Science > Q Science (General)
T Technology > TS Manufactures > TS0155-194 Production management. Operations management
Divisions: Sabancı Business School
Sabancı Business School > Operations Management and Information Systems
Depositing User: Meltem Denizel
Date Deposited: 01 Nov 2008 16:23
Last Modified: 19 Jul 2019 14:51

Actions (login required)

View Item
View Item