Algoritmo ABC para la resolución de problema en un entorno de flow shop con restricción no-idle

Abstract

En este trabajo se utiliza el algoritmo de optimización Artificial Bee Colony (ABC) inspirado en la inteligencia de enjambre, perteneciente a una rama de la Inteligencia artificial que se basa en el comportamiento colectivo de sistemas descentralizados y auto organizados. Este algoritmo reproduce el comportamiento inteligente de las colonias de abejas a la hora de buscar fuentes de alimentos. En nuestro caso lo aplicamos a la resolución de un problema de programación de la producción. Entre sus muchas variantes, nos hemos centrado en una de las restricciones menos atendidas por la literatura. Concretamente, un problema en un entorno del flow shop, con el fin de minimizar el tiempo de finalización del último trabajo, o makespan, bajo la restricción no idle, esto es, la inactividad en máquinas no está permitida una vez comienza su actividad. Para la resolución de este problema se proponen una serie de variantes del algoritmo, que son presentadas a lo largo de este documento. Posteriormente, se realiza una evaluación computacional de los resultados obtenidos en las simulaciones con el algoritmo inicial y las variantes aportadas. El algoritmo inicial y las nuevas variantes que hemos introducido se han codificado en lenguaje C, mediante el programa informático Code::Blocks, con la ayuda de la librería <schedule.h>, que posee una serie de funciones que facilita la implementación.

In this work we use the Artificial Bee Colony (ABC) optimization algorithm, an algorithm inspired by swarm intelligence, a branch of artificial intelligence which is based on the collective behavior of decentralized and self-organized systems. This algorithm is motivated by the intelligent behavior of honey bees when looking for food sources. We apply it to the resolution of a scheduling problem. Among its many variants, we have focused on one problem that has not attracted much attention in the literature. Specifically, a problem in a flow shop environment in order to minimize the makespan, considering the constraint of no idle times allowed on machines. In order to solve this problem, several variants of the algorithm are proposed, which are presented throughout this document. Subsequently, computational results obtained in the simulations with the initial algorithm and the variants proposed are carried out. The initial algorithms and the variants are coded in C with the computer program Code::Blocks, with the aid of the functions included on the <schedule.h> library.