Large-scale capacitated part-routing in the presence of process and routing flexibilities and setup costs

Abstract

We develop a Lagrangean relaxation-based heuristic procedure to generate a near-optimal solution to large-scale capacitated part-routing problems through a cellular manufacturing system with both routing flexibilities and setup times. Several alternate process plans exist for each product. Any given operation can be performed on alternate machines at different costs. The part demands can be satisfied from internal production or through outsourcing. The objective is to minimize the total material handling, production, outsourcing, and setup costs, subject to satisfying all the part demands and not exceeding any of the machine capacity limits. Our computational experiments show that large problems involving several thousand products and decision variables can be solved in a reasonable amount of computer time to within 1% of their optimal solutions. The proposed procedure is general enough to be applied directly or with slight modifications to real-life, industrial-sized problems.

Keywords:

• Lagrangean Relaxation
• large-scale optimization
• dynamic programming
• cellular manufacturing systems

Acknowledgements

This research was supported by the NSERC (Canada) granting council. We thank Cao Yuheng for her overall contribution and the anonymous referees for suggestions that have proved very useful in revising a previous version of this paper.