Resolución del job shop scheduling problem mediante reglas de prioridad

Abstract

Los problemas de planificación, o scheduling, aparecen con profusión en numerosos ámbitos de aplicación y destacan por su elevada complejidad computacional (en muchos casos son NP-duros). Por este motivo, su resolución suele requerir el empleo de algoritmos y técnicas avanzadas de Inteligencia Artificial. En el presente TFG se propone estudiar la resolución de un problema de scheduling clásico, el Job Shop Scheduling Problem (JSSP), mediante reglas de prioridad. Para este fin, además de estudiar la definición del JSSP con diferentes funciones objetivo (“makespan”, “tardiness”), se ha de realizar un trabajo previo de investigación en el que se localicen tanto los bancos de ejemplo, como las reglas de prioridad clásicas empleadas en la literatura para la resolución de estas versiones del problema. Por otro lado, como el objetivo es proporcionar soluciones a instancias del problema JSSP, se implementará un planificador basado en el algoritmo GT propuesto por B. Giffler y G. L. Thomson en 1960, lo que requerirá un estudio previo del mismo. Este algoritmo será guiado por algunas de las reglas de prioridad clásicas aplicables, que también tendrán que ser implementadas, entre ellas: “Shortest Processing Time” (SPT), “Longest Processing Time” (LPT) y Apparent Tardiness Cost (ATC). El trabajo recogerá también un estudio experimental, en el que se mostrarán las soluciones alcanzadas por el prototipo, para algunos bancos de instancias publicados en la literatura, y se compararán, cuando sea posible, con las soluciones o cotas superiores alcanzadas hasta el momento, para dichas instancias.