Teoría del horario

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de noviembre de 2019; las comprobaciones requieren 10 ediciones .

La teoría de horarios  es una rama de las matemáticas discretas que se ocupa de problemas de ordenación. En el caso general, los problemas se formulan de la siguiente manera: Se especifica un determinado conjunto de trabajos (requisitos) con un determinado conjunto de características: la duración del procesamiento del requisito (el caso más simple), el costo del procesamiento del requisito, el momento llega la solicitud, la fecha límite para completar el servicio de la solicitud. Se da un determinado conjunto de máquinas (dispositivos) , en las que se deben cumplir los requisitos de acuerdo con un cierto orden.

Se plantea la tarea de optimización discreta : construir un cronograma que minimice el tiempo para completar el trabajo, el costo del trabajo, etc. El cronograma es una indicación de qué máquinas y en qué momento se deben atender los requisitos (trabajo realizado).

Las tareas de la teoría de la programación se pueden dividir en dos grupos:

• Interrumpir tareas. En cualquier momento, se puede interrumpir el servicio de un requerimiento en una máquina (con posibilidad de finalizar posteriormente en la misma u otra máquina) para atender otro requerimiento.
• tareas ininterrumpidas: todos los requisitos de la máquina se atienden de principio a fin sin interrupción.

Hay varias variantes de problemas de teoría de programación, algunos de ellos son NP-completos , algunos pertenecen a la clase de problemas polinómicos , para algunos problemas no fue posible demostrar la pertenencia a ninguna clase de complejidad. Existe la conjetura de que una tarea que permite interrupciones no es más difícil que una tarea sin interrupciones. Para la mayoría de los problemas se observa, excepto uno, donde para una variante sin interrupción se demuestra que pertenece a la clase de problemas polinómicos , mientras que para un problema similar con interrupciones no se demuestra que pertenece a ninguna clase de complejidad.

De acuerdo con la disciplina de realizar trabajos en máquinas, se pueden distinguir cuatro clases principales de tareas:

1. Taller abierto, línea abierta  : cada requisito tiene su propio subconjunto de máquinas, en cada una de las cuales debe recibir servicio durante algún tiempo. El orden de servicio en estas máquinas es arbitrario. Se establecen varias funciones objetivo.
2. Taller de trabajo, taller  : cada requisito tiene su propio subconjunto ordenado de máquinas (ruta), en el que debe recibir servicio en un orden determinado. Se establecen varias funciones objetivo.
3. Taller de flujo, línea de flujo : todas las máquinas están en orden,y cada requisito pasa por todas las máquinas en ese orden. El cronograma se establece por una permutación de requisitos. Como regla general, se minimiza el tiempo total para atender las solicitudes.
4. Tarea con plazos  : para cada requisito, se especifica el momento de llegada, el tiempo de servicio y la fecha de vencimiento para el final del servicio. El orden de servicio en los dispositivos es arbitrario. Es necesario encontrar un horario que respete los plazos. Si existe tal horario, se puede plantear el problema de minimizar el número de interrupciones.

La última tarea se denomina monoetapa , las tres primeras se denominan multietapa , ya que para cada requerimiento existen varias etapas u operaciones de servicio en distintos dispositivos. Son posibles varias combinaciones de restricciones y disciplinas de servicio, pero los algoritmos que son polinómicos en el tiempo de ejecución solo se conocen para los problemas más simples de estas clases.

En particular, para el problema de Flow shop en dos máquinas, existe el algoritmo de Johnson [1] de complejidad temporal , que construye un cronograma con el mínimo tiempo total de servicio.

Para una tarea con fechas de vencimiento con un número arbitrario de dispositivos e interrupciones del servicio, existe un algoritmo de complejidad de tiempo , que construye un cronograma que respeta las fechas de vencimiento [2] .

La solución de los problemas de Open shop y Job shop con un dispositivo sin interrupciones es alguna permutación de los requisitos, y para una función objetivo arbitraria estos problemas son NP-completos. Pero para algunas funciones objetivo específicas, se han encontrado algoritmos polinómicos. [3] [4] [5]

Los problemas de teoría de programación (scheduling) escritos en tiempo continuo tienen, por regla general, un conjunto infinito de soluciones factibles. El método de ordenamiento nos permite reducir los problemas de programación a problemas de optimización en conjuntos finitos de permutaciones de trabajos. Se formula un enunciado general del problema de la teoría de la programación (scheduling) en tiempo continuo, en el que se describen los componentes de la solución mediante funciones enteras de tiempo y que puede ser resuelto por el método de ordenación. [6]

Dos formas de reducir los problemas originales a problemas de orden se basan en los conceptos de soluciones compactas (activas) y cuasi-compactas (semiactivas). [7] En el preprint anterior de V. V. Shmelev [6] , se generalizan los conceptos de soluciones compactas y cuasi -compactas y, sobre esta base, se propone un nuevo concepto de soluciones monótonas . Cada solución monótona es a la vez compacta y cuasi-compacta, por lo que generalmente hay menos soluciones de este tipo. Esto simplifica la solución de problemas de pedido.

Para describir problemas dinámicos de asignación de recursos con retardos complejos, incluidos los vectoriales y distribuidos, que incluyen problemas de teoría de programación (scheduling), Shmelev V.V. en 1983 [6]  fue el primero en utilizar de forma implícita y continua el tiempo de la operación de convolución . . Posteriormente, utilizó esta operación de forma explícita para tiempo discreto y formuló la formulación general del problema de la teoría de programación (scheduling) en forma de problema de programación dinámica lineal con convoluciones . [8] [9] Esta declaración le permite describir de manera simple y compacta una gran cantidad de problemas dinámicos, incluidos aquellos con variables enteras . Shmelev V. V. extendió sus resultados sobre el método de las funciones de penalización exactas a este escenario.

Notas

1. ↑ SM Johnson , Programas de producción óptimos de dos y tres etapas con tiempos de configuración incluidos, Naval Res. Iniciar sesión. Cuarto de galón. I (1954) 61-68.
2. ↑ Tanaev V.S., Gordon V.S., Shafransky Ya.M.  Teoría de los horarios. Sistemas de una etapa.- M.: Nauka, 1984.
3. ↑ El zoológico de programación . Consultado el 27 de abril de 2013. Archivado desde el original el 28 de abril de 2013. (indefinido)
4. ↑ CiteSeerX - Programación de una sola máquina sujeta a retrasos por precedencia . Consultado el 27 de abril de 2013. Archivado desde el original el 28 de abril de 2013. (indefinido)
5. ↑ Resultados de complejidad para problemas de programación . Consultado el 27 de abril de 2013. Archivado desde el original el 28 de abril de 2013. (indefinido)
6. ↑ 1 2 3 V. V. Shmelev. Método de ordenamiento en problemas de programación. Preimpresión. Moscú: VNIISI . 1983. La preimpresión está disponible en el sitio web de la Biblioteca Electrónica Científica eLIBRARY.RU en la lista de publicaciones de Shmelev V.V.
7. ↑ Conway R. V., Maxwell V. L., Miller L. V.  Teoría del horario.- M.: "Nauka", 1975, sección 6.5.
8. ↑ Shmelev V.V. Tareas dinámicas de programación. Automatización y Telemecánica , 1997, No. 1, 121-125.
9. ↑ Shmelev V.V. Método de funciones de penalización exactas para problemas de optimización de enteros mixtos lineales. Disertación para el grado de Doctor en Ciencias Físicas y Matemáticas, M.: ISA RAN, 2000, capítulo 6. La disertación y su resumen están disponibles en el sitio web de la Biblioteca Electrónica Científica eLIBRARY.RU en la lista de publicaciones de Shmelev V.V.

Literatura

• Richard W. Conway, William L. Maxwell, Louis W. Miller . Teoría de la programación
  • Conway R. V., Maxwell V. L., Miller L. V. Teoría del horario. Moscú: La edición principal de la literatura física y matemática de la editorial Nauka, 1975.
• Tanaev V. S. , Shkurba V. V. Introducción a la teoría de la programación. (Serie "Biblioteca de Economía y Matemáticas"), Moscú: La edición principal de la literatura física y matemática de la editorial "Nauka", 1975.
• Levin VI Métodos lógicos estructurales en la teoría de la programación. Penza: Editorial Penz. estado tecnología academia, 2006.
• Lazarev A. A. Teoría del horario. Estimaciones del error absoluto y esquema de solución aproximada de problemas de programación . Tutorial. (UIP RAS, MIPT) - M.: MIPT, 2008. - 222 p. ISBN 978-5-7417-0257-4
• Lazarev A. A., Musatova E. G., Gafarov E. R., Kvaratskhelia A. G. Teoría del horario. Problemas de planificación ferroviaria . M.: UIP RAN, 2012. 92 p. ISBN 978-5-91450-102-7 .
• Brucker P. Algoritmos de programación . Heidelberg, Springer. Quinta ed. ISBN 978-3-540-24804-0 (publicación oficial en el portal del editor).
• Algoritmos de programación de Peter Brucker . Heidelberg, Springer. Quinta ed. ISBN 978-3-540-24804-0 Archivado el 21 de febrero de 2016 en Wayback Machine .

publicaciones de divulgación científica

• Shkurba V. V. " El problema de las tres máquinas ". — M.: Nauka, 1976. — 96 p., ilustración.