AN EFFICIENT HEURISTIC FOR ROBOT ACQUISITION AND CELL-FORMATION

In this paper, a mathematical model and a solution algorithm are devel oped 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 tota l system (acquisition) cost. Specifically, each robot has two capacity constraints - available work envelope and effective machine time. RAC FP 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 deve loped 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 rando m search heuristic using a greedy evaluation function. The algorithm i s tested by solving 450 randomly generated problems based on realistic parameter values. Computational results show that the heuristic algor ithm 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 l ess than 1% from the optimum. More importantly, over 70% of all soluti ons are optimal (334 out of 450). The algorithm can be easily modified for other applications such as file placement for a multi-device stor age system and job scheduling for a multi-processing system.