JSSP PDF Imprimir E-mail

El problema de asignación de recursos en talleres de manufactura (JSSP, por sus siglas en inglés) es un problema basado en la calendarización de máquinas de un taller para la realización de un conjunto de trabajos, donde cada trabajo requiere de la ejecución de un conjunto de operaciones, este problema se caracteriza por la búsqueda de una secuencia óptima de ejecución de trabajos en cada máquina del sistema cumpliendo restricciones de precedencia en la ejecución de operaciones en cada en trabajo. El modelo que representa al JSSP [Roy and Sussman] se presenta a continuación.

3.1. Modelo NP-Completo JSSP.

La función objetivo en (12) se relaciona con el máximo tiempo de término de ejecución de la última operación que se realiza en el taller de manufactura. Para este problema se requiere minimizar ese tiempo. El conjunto de restricciones en (13) indica que el tiempo en el que inicia cada operación j, debe ser mayor o igual a cero. El conjunto de restricciones en (14) define las restricciones de precedencia que existe entre pares de operaciones que pertenece a un mismo trabajo. El conjunto de restricciones en (15) define las restricciones de capacidad de recursos que existe entre pares de operaciones que ejecuta la misma máquina.


Algoritmo Genético híbrido.

La figura 3, presenta la metodología de solución que está formada de un algoritmo genético que contiene un operador de selección “the best”, un operador de cruzamiento “SXX” y un operador de mutación “mutation-S” con una población factible inicial generada de forma aleatoria. El operador “the best”, selecciona de acuerdo a su aptitud en un porcentaje a los mejores individuos de cada población y cruza estos. Con el cruzamiento de intercambio subsecuente, se mantiene el tamaño de la población y permite la exploración del espacio de soluciones. El mutador que se ocupa, es un mutador iterativo [Cruz-Chávez and J. Frausto-Solís] el cual optimiza la función de aptitud, de tal forma que se reacomode cada gen en su respectivo cromosoma para llegar al mejor individuo encontrado mediante búsqueda local iterada mediante el procedimiento de recocido simulado; lo que significa que la agrupación de genes en ese individuo es la que reportará el menor Makespan. El procedimiento anterior se repite en cada generación de la población.


 

3.3. Procesamiento distribuido del Algoritmo.

El procesamiento distribuido aplicado al algoritmo se presenta en la figura 4. En un nodo de la MiniGRID Tarántula, se crea la población inicial factible. Este nodo realiza la selección y cruzamiento. La mutación que es el procedimiento más costoso en cuanto a tiempo de cómputo se reparte en forma proporcional en todos los nodos de la MiniGRID, esto quiere decir que se genera un número de procesos de acuerdo al número de CPU’s existentes en la GRID (1:1), cada proceso ejecuta un conjunto de Recocidos Simulados en una CPU, un RS por cada individuo de un subconjunto de la población a mutar. Los nodos regresan los nuevos individuos mutados al nodo origen. La ejecución del algoritmo continúa para la nueva generación en el nodo origen con la selección y cruzamiento. Para una población definida de tamaño 100 en las pruebas y si se muta el 80% de la población. Se tiene que si la MiniGRID cuenta con 20 CPU´s, cada CPU estará realizando la mutación de 4 individuos.

 




 

Patrocinadores


CIICAp
Maestrías y Doctorados en: Tecnología Eléctrica, Tecnología Química, Tecnología de Materiales y Tecnología Mecánica.




 

 

Links Relacionados

Mapa de visitas de esta página

Springer
Revista Programación Matemática

Springer

Artículo Mini Grid Morelos
Artículo Mini Grid Morelos

Contador de visitas

mod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_counter
mod_vvisit_counterHoy59
mod_vvisit_counterAyer53
mod_vvisit_counterEsta semana59
mod_vvisit_counterÚltima semana318
mod_vvisit_counterEste més267
mod_vvisit_counterUltimo més1980
mod_vvisit_countertodos los dìas431866