An efficient heuristic for robot acquisition and cell formation

In this paper, a mathematical model and a solution algorithm are developed for solving a robot acquisition and cell formation problem (RACFP). Our model considers purchasing a proper mix of robots and assigning all given workstations to purchased robots such that each robot cell satisfies its workstations' resource demands while minimizing the total system (acquisition) cost. Specifically, each robot has two capacity constraints - available work envelope and effective machine time. RACFP is formulated as a multi-type two-dimensional bin packing problem, a pure 0-1 integer program which is known to be NP-hard. In this paper, a very efficient (polynomial time bound) heuristic algorithm is developed and implemented. The algorithm consists of two major stages. The first stage employs an LP-based bounding procedure to produce a tight solution bound, whereas the second stage repetitively invokes a random search heuristic using a greedy evaluation function. The algorithm is tested by solving 450 randomly generated problems based on realistic parameter values. Computational results show that the heuristic algorithm has outperformed algorithms using general optimization techniques such as Simulated Annealing and Column Generation. All test problems are solved within an order of magnitude of 10 seconds, with a gap of less than 1% from the optimum. More importantly, over 70% of all solutions are optimal (334 out of 450). The algorithm can be easily modified for other applications such as file placement for a multi-device storage system and job scheduling for a multi-processing system. Copyright Kluwer Academic Publishers 1998