A genetic algorithm extended modified sub-gradient algorithm for cell formation problem with alternative routings

Abstract

This paper addresses the cell formation problem with alternative part routes. The problem is considered in the aspect of the natural constraints of real-life production systems such as cell size, separation and co-location constraints. Co-location constraints were added to the proposed model in order to deal with the necessity of grouping certain machines in the same cell for technical reasons, and separation constraints were included to prevent placing certain machines in close vicinity. The objective is to minimise the weighted sum of the voids and the exceptional elements. A hybrid algorithm is proposed to solve this problem. The proposed algorithm hybridises the modified sub-gradient (MSG) algorithm with a genetic algorithm. MSG algorithm solves the sharp augmented Lagrangian dual problems, where zero duality gap property is guaranteed for a wide class of optimisation problems without convexity assumption. Generally, the dual problem is solved by using GAMS solvers in the literature. In this study, a genetic algorithm has been used for solving the dual problem at the first time. The experimental results show the advantage of combining the MSG algorithm and the genetic algorithm. Although the MSG algorithm, whose dual problem is solved by GAMS solver, and the genetic algorithm cannot find feasible solutions, hybrid algorithm generates feasible solutions for all of the test problems.

Keywords:

• cell formation problem
• cellular manufacturing
• alternative routings
• modified sub-gradient algorithm
• genetic algorithms