Heuristic for Flexible Machine Selection Problems

ABSTRACT

This paper addresses the problem of machine selection in the design of flexible manufacturing systems. The proposed heuristic considers the flexibility of machines and the alternate routes for each part to be processed in order to determine the number of machines of each type to purchase and the tasks to be assigned to each of them. The heuristic is divided into two parts. The first part attempts to load and unload machines to improve the annual cost from an initial solution. The second part will attempt to further improve the annual cost by balancing the workload among the machine types. An overview of the heuristic is given and some numerical results obtained for a number of examples are presented. The heuristic generates, in short time, a good feasible solution compared to an optimal one obtained by solving an integer programming model for the same problem. The tests performed show that the proposed heuristic is more performant when used for large size problems.

RÉSUMÉ

Cet article traite du problème de sélection de machines lors de la conception d'un système manufacturier flexible. L'heuristique proposée considère à la fois la flexibilité des machines et des routages pour générer une solution réalisable. L'heuristique utilise une approche itérative. Elle procède à partir d'une solution initiale et tente d'aboutir, par un processus de chargement et déchargement puis d'équilibrage des charges, vers une configuration qui minimise le coût total annuel d'exploitation. Un aperçu des concepts et de l'approche utilisée est exposé. Des résultats numériques obtenus à partir d'exemples simples seront présentés. L'heuristique proposée permet d'obtenir, d'une manière simple et rapide, une configuration réalisable qui se compare avantageusement à celle générée par un modèle de programmation linéaire en nombres entiers. L'heuristique s'est montrée plus performante, en termes de temps de résolution et de proximité de la solution optimale, pour le traitement de problèmes de grande taille.

KEY WORDS:

• FMS
• design
• flexibility
• machine selection
• heuristic

MOTS-CLÉS:

• atelier flexible
• conception
• heuristique
• flexibilité