Programación de trabajos fraccionada

Programación óptima de trabajos con algunos trabajos realizados en partes

La programación fraccionada de trabajos es una variante de la programación óptima de trabajos 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 tiempo de fabricación. Además, el problema computacional de encontrar una programación óptima puede resultar más fácil, ya que algunas de las variables de optimización se vuelven continuas. Por otro lado, dividir los trabajos en partes puede resultar costoso.

Variantes

Existen varias variantes de problemas de programación de tareas en las que se permite dividir las tareas. Se pueden clasificar en general en preempción y división .

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

Programación de trabajos con prioridad

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

• En la primera variante, el número total de preempciones está limitado por un 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 interrumpir a lo largo de un cronograma factible. ${\displaystyle j}$ ${\displaystyle j}$

En ambas variantes, el objetivo es encontrar un cronograma que minimice el tiempo de realización sujeto a las restricciones de preempción.

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

Para máquinas uniformes , un algoritmo polinomial de Gonzalez y Sahni ^[4] produce como máximo preempciones. Shachnai, Tamir y Woeginger ^[5] demostraron la NP-dureza para el caso donde el número de preempciones es estrictamente menor que . También presentaron un PTAS para GMS con un límite de preempción global, y otro PTAS para GMS con un límite de preempción por 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 preempción y demuestran que la minimización de makespan 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 de trabajos, donde no hay un límite firme en el número de preempciones, pero cada preempción requiere dedicar tiempo a la "configuración del trabajo".

Algunos trabajos como el de 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 diversos objetivos. Existen 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íficos. El tiempo de preparación dependiente de la secuencia es una situación en la que el tiempo de preparación necesario para un trabajo depende del trabajo anterior, en lugar de ser constante para todos los trabajos (tiempo de preparación de trabajo independiente).

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

Xing y Zhang ^[2] permiten divisiones ilimitadas y brindan algoritmos polinómicos para muchos criterios de optimalidad (como tiempo de ejecución, retraso, etc.) con máquinas idénticas, uniformes y no relacionadas. Para el caso con tiempo de configuración de trabajo independiente, brindan un algoritmo de aproximación . ${\displaystyle 7/4}$

Son et al. ^[11] estudian la minimización de makespan en una sola máquina con una restricción de disponibilidad de 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 ramificación y acotación con el objetivo de minimizar la tardanza total con un tiempo de configuración de trabajo independiente. Yalaoui y Chu ^[13] proponen una heurística para el mismo problema, con el objetivo de minimizar el tiempo de preparación. Kim et al. ^{[14] sugieren un} algoritmo heurístico de dos fases con el objetivo de minimizar la tardanza total. Con el objetivo de minimizar el tiempo de preparación, Kim ^[15] estudia otra variante con tiempo de configuración familiar en la que no se requiere configuración cuando las piezas del mismo trabajo se producen consecutivamente. Y, Wang et al. ^[16] incluyen una propiedad de aprendizaje que mejora el tiempo de procesamiento de un trabajo de acuerdo con el efecto de aprendizaje. El aprendizaje tiene que reiniciarse si un trabajo se divide y procesa por una máquina diferente.

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 configuración dependientes de la secuencia y recursos de configuración limitados (los trabajos requieren operadores de configuración que son limitados) con el objetivo de minimizar el makespan. Krysta, Sanders y Vöcking ^[18] estudian la minimización de makespan utilizando la variante k-divisible, una variante en la que se permite que cada trabajo se divida en la mayoría de las máquinas diferentes. Muestran que esta variante y otra variante más general en la que cada trabajo tiene su propio parámetro de divisible son NP-hard. Ofrecen 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 el número de trabajos de división.

Referencias

1. McNaughton, Robert (octubre de 1959). "Programación con plazos y funciones de pérdida". Management Science . 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 paralelas con división de tareas". Matemáticas Aplicadas Discretas . 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 programación multiprocesador preemptiva y de taller abierto". Actas de la 2.ª conferencia internacional multidisciplinaria sobre programación: teoría y aplicaciones MISTA 2005. 2005.
4. Gonzalez, Teofilo; Sahni, Sartaj (1978-01-01). "Programación preferente de sistemas de procesadores uniformes". 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 costes de Makespan y de preempción en un sistema de máquinas uniformes". Algorithmica . 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). "Programas con una sola preempción en máquinas paralelas uniformes". Matemáticas Aplicadas Discretas . Reunión GO X, Rigi Kaltbad (Suiza), 10-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 publicación de trabajos, tiempos de entrega y penalizaciones por prelación". Information Processing Letters . 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 longitud de la programación". IEEE Transactions on Computers . 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 informática . 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". Investigación de operaciones . 44 (4): 617–628. doi :10.1287/opre.44.4.617. ISSN  0030-364X. JSTOR  172004.
11. Son, Trang Hong; Van Lang, Tran; Huynh-Tuong, Nguyen; Soukhal, Ameur (1 de enero de 2021). "Resolución para el problema de programación de trabajos con 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. Shim, Sang-Oh; Kim, Yeong-Dae (1 de marzo de 2008). "Un algoritmo de ramificación y acotación para un problema de programación de máquinas paralelas idénticas con una propiedad de división de trabajos". Computers & Operations Research . 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 paralelas con división de tareas y tiempos de configuración dependientes de la secuencia". IIE Transactions . 35 (2): 183–190. doi :10.1080/07408170304382. ISSN  0740-817X. S2CID  62630299.
14. Kim *, Y.-D.; Shim, S.-O.; Kim, S.-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 de 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 paralelas con partes predefinidas de trabajos y tiempo de configuració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). "Minimización del tiempo total de finalización para la programación de máquinas paralelas con división de tareas y aprendizaje". Computers & Industrial Engineering . 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". Computers & Operations Research . 126 : 105115. doi :10.1016/j.cor.2020.105115. ISSN  0305-0548. S2CID  225115689.
18. Krysta, Piotr; Sanders, 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 clase en 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.