Programación de trabajo fraccionada

Programación óptima del trabajo con algunos trabajos realizados en partes

La programación de trabajos fraccionada es una variante de la programación de trabajos óptima en la que se permite dividir los trabajos en partes y procesar cada parte por separado en la misma máquina o en una diferente. Dividir los trabajos en partes puede permitir mejorar el rendimiento general, por ejemplo, disminuyendo el intervalo de producción. Además, el problema computacional de encontrar un cronograma óptimo puede volverse más fácil, a medida que algunas de las variables de optimización se vuelven continuas. Por otro lado, dividir los puestos de trabajo podría resultar costoso.

Variantes

Hay varias variantes de problemas de programación de trabajos en los que se permite dividir los trabajos. Se pueden clasificar en términos generales en preferencia y división .

• En las variantes de preferencia, se deben procesar diferentes partes de un trabajo en diferentes momentos. En la notación de tres campos , se denotan por pmtn. Fueron estudiados por primera vez por McNaughton. ^[1]
• En las variantes de división, se pueden procesar simultáneamente diferentes partes de un trabajo en diferentes máquinas. Se denotan por división y fueron introducidos por Xing y Zhang. ^[2]

Programación de trabajos con preferencia

Se han estudiado varios problemas en la programación laboral con preferencia. Uno de ellos es la programación multiprocesador generalizada (GMS). Tiene dos variantes.

• En la primera variante, el número total de apropiaciones está limitado por algún número entero fijo.
• En la segunda variante, cada trabajo tiene un parámetro asociado que limita el número de veces que se puede adelantar a lo largo de un cronograma factible. ${\displaystyle j}$ ${\displaystyle j}$

En ambas variantes, el objetivo es encontrar un cronograma que minimice el intervalo de tiempo sujeto a las restricciones de preferencia.

Para máquinas idénticas , Shchepin y Vakhania ^[3] demuestran que, como máximo, con apropiaciones totales, el problema es NP-difícil , mientras que McNaughton ^[1] muestra un algoritmo de tiempo lineal con apropiaciones. ${\displaystyle n-2}$ ${\displaystyle n-1}$

Para máquinas uniformes , un algoritmo polinomial de González y Sahni ^[4] produce como máximo apropiaciones. Shachnai, Tamir y Woeginger ^[5] demostraron la dureza NP para el caso en el que el número de preferencia es estrictamente menor que . También presentaron un PTAS para GMS con un límite de preferencia global y otro PTAS para GMS con un límite de preferencia de trabajo cuando el número de máquinas es una constante fija. ${\displaystyle 2n-2}$ ${\displaystyle 2n-2}$

Soper y Strusevitch ^[6] estudian el caso especial en el que se permite como máximo una preferencia. Muestran que la minimización del makepan es polinómica para dos máquinas.

Muchos artículos estudian otras variantes de programación preventiva. Por ejemplo, Liu y Cheng ^[7] consideran la programación de una sola máquina con fechas de liberación y entrega del trabajo, donde no hay un límite firme en el número de apropiaciones, pero cada apropiación requiere dedicar tiempo a la "configuración del trabajo".

Algunos trabajos como Blazewicz et al. ^[8] o Deng et al. ^[9] estudian la programación preventiva para trabajos con paralelismo donde los trabajos deben procesarse simultáneamente en varios procesadores.

Programación de trabajos con división

Se han estudiado varios objetivos. Hay muchas variantes, incluidos diferentes tiempos de preparación. En la programación de máquinas, el "tiempo de preparación" se refiere al tiempo necesario para preparar una máquina para un trabajo o tarea específica. El tiempo de preparación dependiente de la secuencia es una situación en la que el tiempo de preparación requerido para un trabajo depende del trabajo anterior, en lugar de ser constante para todos los trabajos (tiempo de preparación del trabajo independiente).

Serafini ^[10] asume divisiones y apropiaciones ilimitadas y proporciona algoritmos de tiempo polinomial que minimizan la tardanza máxima y la tardanza máxima ponderada, para máquinas uniformes y no relacionadas.

Xing y Zhang ^[2] permiten divisiones ilimitadas y proporcionan algoritmos polinomiales para muchos criterios de optimización (como la duración, el retraso, la tardanza y más), con máquinas idénticas, uniformes y no relacionadas. Para el caso con tiempo de preparación de trabajo independiente, proporcionan un algoritmo de aproximación . ${\displaystyle 7/4}$

Hijo y col. ^[11] el estudio hace la minimización de la duración en una sola máquina con una restricción de disponibilidad de la máquina con un límite inferior en la longitud de cada parte de un trabajo que se divide.

Para máquinas idénticas , Shim y Kim ^[12] sugieren un algoritmo de bifurcación y vinculación con el objetivo de minimizar la tardanza total con un tiempo de preparación del trabajo independiente. Yalaoui y Chu ^[13] proponen una heurística para el mismo problema, con el objetivo de minimizar el makepan. Kim y cols. ^{[14] sugieren un} algoritmo heurístico de dos fases con el objetivo de minimizar la tardanza total. Con el objetivo de minimizar el makespan, Kim ^[15] estudia otra variante con tiempo de preparación familiar en la que no se requiere preparación cuando se producen piezas del mismo trabajo consecutivamente. Y Wang et al. ^[16] incluyen una propiedad de aprendizaje que mejora el tiempo de procesamiento de un trabajo según el efecto de aprendizaje. El aprendizaje debe reiniciarse si un trabajo se divide y procesa en otra máquina.

Para máquinas uniformes , Kim y Lee ^[17] estudian una variante con máquinas dedicadas (hay algunas máquinas dedicadas para cada trabajo), tiempos de preparación dependientes de la secuencia y recursos de preparación limitados (los trabajos requieren operadores de preparación limitados) con la objetivo minimizar el makepan. El estudio de Krysta, Sanders y Vöcking ^[18] realiza la minimización del intervalo utilizando la variante k-splitable, una variante en la que cada trabajo puede dividirse en la mayoría de las máquinas diferentes. Muestran que esta variante y otra variante más general donde cada trabajo tiene su propio parámetro de división, son NP-difíciles. Proporcionan algunos algoritmos de aproximación, pero su resultado principal es un algoritmo de tiempo polinomial para ambos problemas, para un número fijo de máquinas. Muestran que permitir un número limitado de divisiones reduce la complejidad de la programación. ${\displaystyle k}$

En todos estos trabajos, no existe un límite global en cuanto al número de puestos de trabajo divididos.

Referencias

1. McNaughton, Robert (octubre de 1959). "Programación con Plazos y Funciones de Pérdidas". Ciencias de la gestión . 6 (1): 1–12. doi :10.1287/mnsc.6.1.1. ISSN  0025-1909.
2. Xing, Wenxun; Zhang, Jiawei (15 de julio de 2000). "Programación de máquinas en paralelo con división de trabajos". Matemática Aplicada Discreta . 103 (1): 259–269. doi :10.1016/S0166-218X(00)00176-1. ISSN  0166-218X.
3. Shchepin, Evgeny y Nodari Vakhania. "Nueva dureza NP estricta de multiprocesador preventivo y programación de tienda abierta". Actas de la segunda conferencia internacional multidisciplinaria sobre programación: teoría y aplicaciones MISTA 2005 . 2005.
4. González, Teófilo; Sahni, Sartaj (1 de enero de 1978). "Programación preventiva de sistemas de procesador uniforme". Revista de la ACM . 25 (1): 92-101. doi : 10.1145/322047.322055 . ISSN  0004-5411.
5. Shachnai, Hadas; Tamir, Tami; Woeginger, Gerhard J. (1 de julio de 2005). "Minimización de los costos de preferencia y makespan en un sistema de máquinas uniformes". Algorítmica . 42 (3): 309–334. doi :10.1007/s00453-005-1171-0. ISSN  1432-0541. S2CID  14256666.
6. Soper, Alan J.; Strusevich, Vitaly A. (31 de mayo de 2019). "Horarios con preferencia única en máquinas paralelas uniformes". Matemática Aplicada Discreta . Reunión GO X, Rigi Kaltbad (CH), 10 al 14 de julio de 2016. 261 : 332–343. doi : 10.1016/j.dam.2018.03.007 . ISSN  0166-218X. S2CID  126307013.
7. Liu, Zhaohui; Cheng, TC Edwin (30 de abril de 2002). "Programación con fechas de liberación de empleo, tiempos de entrega y penalizaciones anticipadas". Cartas de Procesamiento de Información . 82 (2): 107–111. doi :10.1016/S0020-0190(01)00251-4. hdl : 10397/32337 . ISSN  0020-0190.
8. Blazewicz; Drabowski; Weglarz (mayo de 1986). "Programación de tareas multiprocesador para minimizar la duración de la programación". Transacciones IEEE en computadoras . C-35 (5): 389–393. doi :10.1109/TC.1986.1676781. ISSN  1557-9956. S2CID  18188390.
9. Deng, Xiaotie; Gu, Nian; Brecht, Tim; Lu, Kaicheng (2000). "Programación preventiva de trabajos paralelos en multiprocesadores". Revista SIAM de Computación . 30 (1): 145–160. doi :10.1137/S0097539797315598. ISSN  0097-5397. S2CID  1717179.
10. Serafini, Paolo (1996). "Programación de trabajos en varias máquinas con la propiedad de división de trabajos". La investigación de operaciones . 44 (4): 617–628. doi :10.1287/opre.44.4.617. ISSN  0030-364X. JSTOR  172004.
11. Hijo, Trang Hong; Van Lang, Tran; Huynh-Tuong, Nguyen; Soukhal, Ameur (1 de enero de 2021). "Resolución del problema de programación de trabajos de división limitada en una sola máquina en ventanas de tiempo disponibles". Revista de Inteligencia Ambiental y Computación Humanizada . 12 (1): 1179-1196. doi :10.1007/s12652-020-02162-0. ISSN  1868-5145. S2CID  255752164.
12. Calce, Sang-Oh; Kim, Yeong-Dae (1 de marzo de 2008). "Un algoritmo de bifurcación y vinculación para un problema de programación de máquinas paralelas idéntico con una propiedad de división de trabajos". Investigación de operaciones y computadoras . Parte Número especial: Nuevas tendencias en análisis de ubicación. 35 (3): 863–875. doi :10.1016/j.cor.2006.04.006. ISSN  0305-0548.
13. YALAOUI, FAROUK; CHU, CHENGBIN (1 de febrero de 2003). "Un enfoque heurístico eficiente para la programación de máquinas en paralelo con división de trabajos y tiempos de configuración dependientes de la secuencia". Transacciones IIE . 35 (2): 183-190. doi :10.1080/07408170304382. ISSN  0740-817X. S2CID  62630299.
14. Kim *, Y.-D.; Calza, S.-O.; Kim, SB-B.; Choi, Y.-C.; Yoon, HM (1 de noviembre de 2004). "Programación de máquinas paralelas considerando una propiedad de división de trabajos". Revista Internacional de Investigación sobre Producción . 42 (21): 4531–4546. doi :10.1080/00207540410001720745. ISSN  0020-7543. S2CID  60729549.
15. Kim, Hyun-Jung (1 de febrero de 2018). "Límites para la programación de máquinas en paralelo con partes predefinidas de trabajos y tiempo de preparación". Anales de investigación de operaciones . 261 (1): 401–412. doi :10.1007/s10479-017-2615-z. ISSN  1572-9338. S2CID  254228092.
16. Wang, Chenjie; Liu, Changchun; Zhang, Zhi-hai; Zheng, Li (1 de julio de 2016). "Minimizar el tiempo total de finalización de la programación de máquinas paralelas con división de trabajos y aprendizaje". Informática e Ingeniería Industrial . 97 : 170–182. doi :10.1016/j.cie.2016.05.001. ISSN  0360-8352.
17. Kim, Hyun-Jung; Lee, Jun-Ho (1 de febrero de 2021). "Programación de máquinas dedicadas paralelas uniformes con división de trabajos, tiempos de configuración dependientes de la secuencia y múltiples servidores". Investigación de operaciones y computadoras . 126 : 105115. doi : 10.1016/j.cor.2020.105115. ISSN  0305-0548. S2CID  225115689.
18. Krysta, Piotr; Lijadoras, Peter; Vöcking, Berthold (2003). "Programación y asignación de tráfico para tareas con capacidad de división limitada". En Rovan, Branislav; Vojtáš, Peter (eds.). Fundamentos matemáticos de la informática 2003 . Apuntes de conferencias sobre informática. vol. 2747. Berlín, Heidelberg: Springer. págs. 500–510. doi :10.1007/978-3-540-45138-9_44. hdl : 11858/00-001M-0000-0014-6BD1-8 . ISBN 978-3-540-45138-9.