Game theoretic approaches to parallel machine scheduling

Abstract

En un problema de programación de máquinas idénticas en paralelo que persigue minimizar dos criterios en particular, lapso y tiempo de terminación total, un mecanismo basado en la teoría de juegos es propuesto para solucionarlo. Se considera un juego bipersonal no-cooperativo de 2x2 en el que cada jugador busca minimizar alguno de estos criterios que propone el problema de producción. Cada escenario implica que los jugadores jueguen de manera simultanea y busquen minimizar los costos que están relacionados con los criterios a optimizar. El jugador que representa al trabajo tiene la opción de dejar al trabajo en su posición actual o moverlo a una posición previa, buscando minimizar su tiempo de terminación; mientras que el otro jugador, un agente controlador, toma la decisión de dejar al trabajo en la máquina actual o moverlo a otra, esperando balancear la carga de la máquina y minimizar el lapso. Como resultado de una serie de juegos repetidos entre estos agentes, el Frente de Pareto es construido, mostrando un conjunto de soluciones eficientes al problema.