Hacer espacio

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

Ejemplo

Hay un proyecto complejo que se compone de varias subtareas. Nos gustaría asignar tareas a los trabajadores, de modo que el proyecto finalice en el menor tiempo posible. Como ejemplo, supongamos que el "proyecto" es alimentar a las cabras. Hay tres cabras para 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 cronogramas:

1. Si dejamos que Shmuel alimente a todas las cabras, entonces el tiempo de alimentación es 30 (3×10 para Shmuel, 0 para Shifra);
2. Si dejamos que Shifra alimente una cabra y Shmuel dos cabras, entonces el tiempo de trabajo 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 makespan 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 tiempo de vida es 36 (3×12 para Shifra, 0 para Shmuel).

En este caso, el segundo programa alcanza el período de fabricación más corto, que es 20.

Tipos de problemas de minimización de makespan

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

Referencias

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