Makespan

En investigación de operaciones , la duración de un proyecto es el tiempo que transcurre desde el inicio del trabajo hasta el final. Este tipo de problema de programación de proyectos con recursos restringidos multimodo (MRCPSP) busca crear la programación lógica más corta del proyecto, mediante el uso eficiente de los recursos del proyecto, agregando la menor cantidad posible de recursos adicionales para lograr el mínimo de duración. ^[1] El término aparece comúnmente en el contexto de programación .

Ejemplo

Hay un proyecto complejo que se compone de varias subtareas. Nos gustaría asignar tareas a los trabajadores, de forma que el proyecto finalice en el menor tiempo posible. Como ejemplo, supongamos que el "proyecto" es alimentar a las cabras. Hay tres cabras que alimentar, un niño solo puede alimentar a una cabra a la vez y hay dos niños que pueden alimentarlas: Shmuel alimenta a cada cabra en 10 minutos y Shifra alimenta a cada cabra en 12 minutos. Son posibles varios horarios:

1. Si dejamos que Shmuel alimente a todas las cabras, entonces el makepan es 30 (3×10 para Shmuel, 0 para Shifra);
2. Si dejamos que Shifra alimente una cabra y Shmuel dos cabras, entonces el makepan es 20 (2×10 para Shmuel, 12 para Shifra trabajando al lado y en paralelo a Shmuel);
3. Si dejamos que Shifra alimente dos cabras y Shmuel una cabra, entonces el makepan es 24 (2×12 para Shifra, 10 para Samuel trabajando al lado y en paralelo a Shifra);
4. Si dejamos que Shifra alimente a todas las cabras, entonces el makepan es 36 (3×12 para Shifra, 0 para Shmuel).

Entonces, en este caso, el segundo programa alcanza el intervalo de tiempo más corto, que es 20.

Tipos de problemas de minimización de makepan

• Regla de Johnson : hay n trabajos y 2 estaciones diferentes. Considere utilizar esta regla para secuenciar trabajos que deben pasar por ambos centros de trabajo.
• Programación del taller de trabajo : hay n trabajos y m estaciones idénticas. Cada trabajo debe ejecutarse en una sola estación. Generalmente esto se considera un problema en línea.
• Programación de taller abierto : hay n trabajos y m estaciones diferentes. Cada trabajo deberá pasar algún tiempo en cada estación, en un orden libre.
• Programación de taller de flujo : hay n trabajos y m estaciones diferentes. Cada trabajo debe pasar algún tiempo en cada estación, en un orden predeterminado.
• Minimización justa del makepan: al asignar tareas a los agentes, es necesario minimizar el makepan y evitar la envidia. Si se le da un trabajo al trabajador más rápido, debe ser compensado por su esfuerzo extra. Mu'alem presenta un marco general para problemas de optimización con garantía libre de envidia mediante pagos monetarios. ^[2]

Referencias

1. Afshar-Nadjafi, Behrouz (2018). "Un procedimiento de solución para el problema de programación preventiva de proyectos multimodo con posibilidad de cambio de modo hasta la reanudación". Computación e Informática Aplicada . 14 (2): 192-201. doi : 10.1016/j.aci.2014.02.003 . S2CID  62145189.
2. Mu'alem A (2014). "Feria por diseño: mecanismos multidimensionales libres de envidia". Juegos y comportamiento económico . 88 : 29–46. doi :10.1016/j.geb.2014.08.001.