Minimization of the Number of Tool Magazine Setups on Automated Machines: A Lagrangean Decomposition Approach
Author:
- 1 April 2003
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 51 (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
This publication has 14 references indexed in Scilit:
- Part-type selection in flexible manufacturing systems: a bicriteria approach with due datesJournal of the Operational Research Society, 1998
- Assignment of tools to machines in a flexible manufacturing systemEuropean Journal of Operational Research, 1995
- Improved Lagrangean decomposition: An application to the generalized assignment problemEuropean Journal of Operational Research, 1990
- Modelling and solving an FMS part selection problemInternational Journal of Production Research, 1989
- Models Arising from a Flexible Manufacturing Machine, Part II: Minimization of the Number of Switching InstantsOperations Research, 1988
- A study of FMS part type selection approaches for short-term production planningInternational Journal of Flexible Manufacturing Systems, 1988
- Lagrangean decomposition: A model yielding stronger lagrangean boundsMathematical Programming, 1987
- Sequential decision procedures for batching and balancing in FMSsAnnals of Operations Research, 1985
- The part families problem in flexible manufacturing systemsAnnals of Operations Research, 1985
- A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling ProblemManagement Science, 1980