ПОСТРОЕНИЕ РАСПИСАНИЙ ДЛЯ ОДНОСТАДИЙНЫХ СИСТЕМ ОБСЛУЖИВАНИЯ
Аннотация
Приведен обзор результатов, полученных в лаборатории математической кибернетики ОИПИ НАН наук Беларуси по решению задач теории расписаний для одностадийных детерминированных систем обслуживания.
Об авторах
В. С. Гордон
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
М. Я. Ковалев
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Я. М. Шафранский
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. – М.: Наука, 1975. – 256 с.
2. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. – М.: Наука, 1984. – 382 с.
3. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, 1989. – 328 с.
4. Tanaev V.S., Gordon V.S., Shafransky Y.M. Scheduling Theory. Single-Stage Systems. – Dordrecht; Boston; London: Kluwer Academic Publ., 1994. – 380 p.
5. Tanaev V.S., Sotskov Y.N., Strusevich V.A. Scheduling Theory. Multi-Stage Systems. – Dordrecht; Boston; London: Kluwer Academic Publ., 1994. – 404 p.
6. Танаев В.С., Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 1998. – 290 с.
7. Сотсков Ю.Н., Сотскова Н.Ю. Теория расписаний. Системы с неопределенными числовыми параметрами. – Мн.: ОИПИ НАН Беларуси, 2004. – 290 с.
8. Handbook of Scheduling: Algorithms, Models and Performance Analysis. – USA, Boca Raton: CRC Press, 2004. – 1120 p.
9. Гордон В.С. Об оптимальных расписаниях с прерываниями процесса обслуживания // Известия АН БССР. Сер. физ.-мат. наук. – 1974. – № 5. – С. 129-130.
10. Гордон В.С. Детерминированная система обслуживания с минимаксным критерием оптимальности и частично упорядоченным множеством требований // Автоматизация технической подготовки производства. – 1977. – Вып. 4. – С. 70-75.
11. Гордон В.С., Танаев В.С. О минимаксных задачах теории расписаний с одним прибором // Известия АН БССР. Сер. физ.-мат. наук. – 1983. – № 3. – С. 3-9.
12. Гордон В.С. Параллельный алгоритм минимизации максимального штрафа за обслуживание требований одним прибором // Известия АН СССР. Техническая кибернетика. – 1989. – № 3. – С. 181-186.
13. Azharonok E., Gordon V., Werner F. Single machine preemptive scheduling with special cost functions // Optimization. – 1995. – V. 34. – P. 1211-1216.
14. Гордон В.С. Параллельные алгоритмы решения задач теории расписаний // Автоматика и телемеханика. – 1992. – № 5. – С. 97-106.
15. Гордон В.С., Зятьков Е.А. Параллельные вычисления в задачах теории расписаний. – Мн.: Ин-т техн. кибернетики АН Беларуси, 1993. – 68 с.
16. Гордон В.С., Танаев В.С. Детерминированная система обслуживания с одним прибором и ступенчатыми функциями штрафа // Вычислительная техника в машиностроении. – Мн.: Ин-т техн. кибернетики АН БССР, 1971, сент. – С. 3-8.
17. Танаев В.С., Гордон В.С. О построении расписаний с наименьшим взвешенным числом запаздывающих требований // Известия АН БССР. Сер. физ.-мат. наук. – 1983. – № 6. – С. 3-9.
18. Гордон В.С. Допустимые относительно директивных сроков расписания с наименьшим суммарным штрафом // Оптимизация, принятие решений, микропроцессорные системы. – София: Изд-во Болгарской академии наук, 1985. – С. 153-156.
19. Гордон В.С., Баранова Е.В. Об одной задаче минимизации суммарного штрафа за обслуживание требований одним прибором // Известия АН БССР. Сер. физ.-мат. наук. – 1984. – № 1. – С. 113.
20. Gordon V., Potapneva E., Werner F. Single machine scheduling with deadlines, release and due dates // Optimization. – 1997. – V. 42. – P. 219-244.
21. Гордон В.С., Потапнева Е.В. Построение расписаний для вложенных интервалов обслуживания требований // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 1998. – № 2. – С. 111-116.
22. Gordon V., Werner F., Yanushkevich O. Scheduling with deadlines and nested processing intervals for a single machine // Operations Research Proceedings 1999. – Berlin: Springer, 2000. – P. 378-382.
23. Гордон В.С., Вернер Ф., Янушкевич О.А. О задаче минимизации взвешенного числа запаздывающих требований с жесткими директивными сроками и вложенными интервалами обслуживания // Доклады Национальной академии наук Беларуси. – 2000. – Т. 44. – № 1. – С. 39-42.
24. Gordon V., Werner F., Yanushkevich O. Single machine preemptive scheduling to minimize the weighted number of late jobs with deadlines and nested release/due date intervals // RAIRO Operations Research. – 2001. – V. 35. – P. 71-83.
25. Kravchenko S.A. On the complexity of minimizing the number of late jobs in unit time open shop // Discrete Applied Mathematics. – 2000. – V. 100. – P. 127-132.
26. Brucker P., Kravchenko S.A. Scheduling equal processing time jobs to minimize the we-ighted number of late jobs. – Osnabrück, 2004. – 24 p. (Preprints / Universität Osnabrück; Heft 254).
27. Brucker P., Kravchenko S.A. Complexity of mean flow time scheduling problems with release dates. – Osnabrück, 2004. – 24 p. (Preprints / Universität Osnabrück; Heft 251).
28. Гордон В.С. Детерминированные одностадийные системы обслуживания с прерываниями // Вычислительная техника в машиностроении. – Мн.: Ин-т техн. кибернетики АН БССР, 1973, июнь. – С. 30-38.
29. Гордон В.С., Танаев В.С. Директивные сроки в однофазных детерминированных системах обслуживания // Оптимизация систем сбора, передачи и обработки аналоговой и дискрет-ной информации в локальных ИВС. – Мн.: Ин-т техн. кибернетики АН БССР, 1973. – С. 51-58.
30. Гордон В.С., Танаев В.С. Прерывания в детерминированных системах с параллельными приборами и неодновременным поступлением требований на обслуживание // Оптимизация систем сбора, передачи и обработки аналоговой и дискретной информации в локальных ИВС. – Мн.: Ин-т техн. кибернетики АН БССР, 1973. – С. 36-50.
31. Танаев В.С. Прерывания в детерминированных системах обслуживания с параллельными идентичными приборами // Известия АН БССР. Сер. физ.-мат. наук. – 1973. – № 6. – С. 44-48.
32. Tuzikov A., Makhaniok M., Männer R. Bicriterion scheduling of identical processing time jobs by uniform processors // Computers and Operations Research. – 1998. – V. 25. – № 1. – P. 31-35.
33. Ковалев М.Я. Эффективные ε-приближенные алгоритмы оптимизации мультипликативных функционалов // Весцi АН БССР. Сер. фiз.-мат. навук. – 1985. – № 4. – C. 13-20.
34. Ковалев М.Я., Шафранский Я.М. Построение ε-приближенных алгоритмов оптимизации функций на последовательно конструируемых множествах // ЖВМ и МФ. – 1986. – № 7. – C. 1006-1018.
35. Ковалев М.Я. Интервальные ε-приближенные алгоритмы для задач отыскания оптимального пути в графе // Весцi АН БССР. Сер. фiз.-мат. навук. – 1988. – № 2. – C. 15-20.
36. Kovalyov M.Y. A rounding technique to construct approximation algorithms for knapsack and partition type problems // Applied Mathematics and Computer Science. – 1996. – V. 6. – № 4. – P. 101-113.
37. Kovalyov M.Y. Improving the complexities of approximation algorithms for optimization problems // Operations Research Letters. – 1995. – V. 17. – P. 85-87.
38. Ковалев М.Я. Минимизация взвешенной суммы запаздывающих требований при обслуживании одним прибором // ЖВМ и МФ. – 1991. – Т. 31. – № 1. – C. 1731-1739.
39. Kovalyov M.Y., Potts C.N., Van Wassenhove L.N. A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work // Mathematics of Operations Research. – 1994. – V. 19. – № 1. – P. 86-94.
40. Janiak A., Kovalyov M.Y. Single machine scheduling subject to deadlines and resource dependent processing times // European Journal of Operational Research. – 1996. – V. 94. – P. 284-291.
41. Kovalyov M.Y., Kubiak W. A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs // Journal of Heuristics. – 1997. – V. 20. – P. 75-79.
42. Kovalyov M.Y., Kubiak W. A fully polynomial approximation scheme for the weighted earliness-tardiness problem // Operations Research. – 1999. – V. 47. – № 5. – P. 757-761.
43. Kubiak W., Cheng J., Kovalyov M.Y. Fast fully polynomial approximation schemes for mi-nimizing completion time variance // European Journal of Operational Research. – 2002. – V. 137. – P. 303-309.
44. Ковалев М.Я., Тузиков А.В. Построение ε-аппроксимации множества Парето некоторых двухкритериальных задач // Математические вопросы автоматизации проектирования и испытаний. – Мн.: Ин-т техн. кибернетики АН БССР, 1986. – С. 126-130.
45. Cheng T.C.E., Janiak A., Kovalyov M.Y. Bicriterion single machine scheduling with reso-urce dependent processing times // SIAM Journal on Optimization. – 1998. – V. 8. – P. 617-630.
46. Ковалев М.Я. Построение ε-приближенных алгоритмов решения некоторых NP-трудных задач // Теория и методы автоматизации проектирования сложных систем и автоматизации научных исследований. – Мн.: Ин-т техн. кибернетики АН БССР, 1985. – С. 15-18.
47. Ковалев М.Я. Построение ε-приближенного решения задачи обслуживания требований в заданные сроки // Весцi АН БССР. Сер. фiз.-мат. навук. – 1990. – № 1. – C. 88-92.
48. Ковалев М.Я. Приближенное решение задачи минимизации суммарного запаздывания требований // Весцi АН БССР. Сер. фiз.-мат. навук. – 1985. – № 5. – C. 110.
49. Kovalyov M.Y., Werner F. Approximation schemes for scheduling jobs with common due date to minimize total tardiness // Journal of Heuristics. – 2002. – V. 8. – P. 415-428.
50. Ковалев М.Я. ε-приближенный алгоритм решения задачи «минимум суммы квадратов» // Сложность и методы решения задач оптимизации. – Мн.: Ин-т техн. кибернетики АН БССР, 1984. – С. 21-27.
51. Тузиков А.В. О двухкритериальной задаче теории расписаний с учетом изменения длительностей обслуживания // ЖВМ и МФ. – 1984. – № 10. – С. 1585-1590.
52. Approximation scheduling algorithms: a survey / M.Y. Kovalyov, Y.M. Shafransky, V.A. Strusevich et al. // Optimization. – 1989. – № 6. – P. 859-878.
53. Гордон В.С. Минимизация стоимости, связанной с переменными директивными сроками, в задаче теории расписаний с одним прибором // Автоматика и телемеханика. – 1992. – № 2. – С. 105-112.
54. Gordon V.S. A note on optimal assignment of slack due-dates in single-machine scheduling // European Journal of Operational Research. – 1993. – V. 70. – P. 311-315.
55. Cheng T.C.E., Gordon V.S. Optimal assignment of due-dates for preemptive single-machine scheduling // Mathl. Comput. Modelling. – 1994. – V. 20. – P. 33-40.
56. Gordon V.S., Strusevich V.A. Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment // Comp. Oper. Res. – 1999. – V. 26. – P. 157-177.
57. Gordon V.S., Proth J.-M., Strusevich V. Single machine scheduling with precedence constraints and SLK due date assignment // Operations Research Proceedings 2003. – Heidelberg: Springer-Verlag, 2004. – P. 157-163.
58. Gordon V.S., Kubiak W. Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs // Information Processing Letters. – 1999. – V. 68. – № 3. – P. 153-159.
59. Cheng T.C.E., Chen Z-L., Shakhlevich N.V. Common due date assignment and scheduling with ready times // Comp. Oper. Res. – 2002. – V. 29. – P. 1957-1967.
60. Chu C., Gordon V. TWK due date determination and scheduling: NP-hardness and polynomially solvable case // Int. J. Mathl. Algorithms. – 2001. – V. 2. – P. 251-267.
61. Cheng T.C.E., Kovalyov M.Y. Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness // European Journal of Operational Research. – 1999. – V. 114. – № 2. – P. 403-410.
62. Gordon V.S., Proth J.-M., Chu C. A survey of the state-of-the-art of common due date assignment and scheduling // European Journal of Operational Research. – 2002. – V. 139. – P. 1-25.
63. Gordon V.S., Proth J.-M., Chu C. Due date assignment and scheduling: SLK, TWK and other due date assignment models // Production Planning & Control. – 2002. – V. 13. – P. 117-132.
64. Gordon V., Proth J.-M., Strusevich V. Scheduling with due date assignment // Handbook of Scheduling: Algorithms, Models and Performance Analysis. – Boca Raton: CRC Press, 2004. – P. 21-1– 21-22.
65. Гордон В.С., Смотряев В.Н., Тарасевич А.А. Построение оптимальных расписаний при назначении директивных сроков // Информатика. – 2004. – № 1. – С. 17-27.
66. Kovalyov M.Y., Tuzikov A.V. Sequencing groups of jobs on a single machine subject to precedence constraints // Applied Mathematics and Computer Science. – 1994. – V. 4. – P. 635-641.
67. Cheng T.C.E., Kovalyov M.Y., Tuzikov A.V. Single machine group scheduling with two ordered criteria // Journal of the Operational Research Society. – 1996. – V. 47. – P. 315-320.
68. Janiak A., Kovalyov M.Y. Single machine group scheduling with ordered criteria // Annals of Operations Research. – 1995. – V. 57. – P. 191-201.
69. Janiak A., Shafransky Y.M., Tuzikov A.V. Sequencing with ordered criteria, precedence and group technology constraints // Informatica. 2001. – V. 12. – № 1. – P. 61-88.
70. Blazewicz J., Kovalyov M.Y. Complexity of two group scheduling problems // Journal of Scheduling. – 2002. – V. 5. – P. 477-485.
71. Cheng T.C.E., Kovalyov M.Y. Single machine batch scheduling with deadlines and resource dependent processing times // Operations Research Letters. – 1995. – V. 17. – P. 243-249.
72. Brucker P., Kovalyov M.Y. Single machine batch scheduling to minimize the weighted number of late jobs // Mathematical Methods of Operations Research. – 1996. – V. 43. – P. 1-8.
73. Cheng T.C.E., Gordon V. S., Kovalyov M.Y. Single machine scheduling with batch deliveries // European Journal of Operational Research. – 1996. – V. 94. – P. 277-283.
74. Cheng T.C.E., Gordon V. Batch delivery scheduling on a single machine // Journal of the Operational Research Society. – 1994. – V. 45. – № 10. – P. 1211-1215.
75. Cheng T.C.E., Kovalyov M.Y., Lin B.M.T. Single machine scheduling to minimize batch delivery and job earliness penalties // SIAM Journal on Optimization. – 1997. – V. 7. – P. 547-559.
76. Parallel-machine batching and scheduling to minimize total completion time / T.C.E. Cheng, Z.-L. Chen, M.Y. Kovalyov, B.M.T. Lin // IIE Transactions. – 1996. – V. 28. – P. 953-956.
77. Cheng T.C.E., Kovalyov M.Y. Batch scheduling and common due date assignment on a single machine // Discrete Applied Mathematics. – 1996. – V. 70. – P. 231-245.
78. Kovalyov M.Y., Shafransky Y.M. Batch scheduling with deadlines on parallel machines: an NP-hard case // Information Processing Letters. – 1997. – V. 64. – P. 69-74.
79. Kovalyov M.Y. Batch scheduling and common due date assignment problem: an NP-hard case // Discrete Applied Mathematics. – 1997. – V. 80. – P. 251-254.
80. Parallel machine batch scheduling with deadlines and sequence-independent setup times / P. Brucker, M.Y. Kovalyov, Y.M. Shafransky, F. Werner // Annals of Operations Research. – 1998. – V. 83. – P. 23-40.
81. Pattloch M., Schmidt G., Kovalyov M.Y. Heuristic algorithms for lotsize scheduling with application in the tobacco industry // Computers and Industrial Engineering. – 2001. – V. 39. – P. 235-253.
82. Cheng T.C.E., Janiak A., Kovalyov M. Single machine batch scheduling with resource dependent setup and processing times // European Journal of Operational Research. – 2001. – V. 135. – P. 177-183.
83. Kovalyov M.Y., Pattloch M., Schmidt G. A polynomial algorithm for lot-size scheduling of two task types // Information Processing Letters. – 2002. – V. 83. – P. 229-235.
84. Cheng T.C.E., Liu Z., Shafransky Y.M. A note on the complexity of family scheduling to minimize the number of late jobs // Journal of Scheduling. – 2001. – V. 4. – P. 225-229.
85. Cheng T.C.E., Kovalyov M.Y. An exact algorithm for batching and scheduling two part types in a mixed shop: a technical note // International Journal of Production Economics. – 1998. – V. 55. – № 1. – P. 53-56.
86. Cheng T.C.E., Kovalyov M.Y. Parallel machine batching and scheduling with deadlines // Journal of Scheduling. – 2000. – V. 3. – P. 109-123.
87. Cheng T.C.E., Kovalyov M.Y. Single machine batch scheduling with sequential job processing // IIE Transactions. – 2001. – V. 33. – P. 413-420.
88. Cheng T.C.E., Kovalyov M.Y. Single supplier scheduling for multiple deliveries // Annals of Operations Research. – 2001. – V. 107. – P. 51-63.
89. Ng C.T., Cheng T.C.E., Kovalyov M. Batch scheduling with controllable setup and processing times to minimize total completion time // Journal of the Operational Research Society. – 2003. – V. 54. – P. 499-506.
90. Ng C.T., Cheng T.C.E., Kovalyov M.Y. Single machine batch scheduling with jointly compressible setup and processing times // European Journal of Operational Research. – 2003. – V. 153. – P. 211-219.
91. Kovalyov M.Y., Potts C.N., Strusevich V.A. Batching decisions for assembly production systems // European Journal of Operational Research. – 2004. – V. 157. – P. 620-642.
92. Cheng T.C.E., Kovalyov M.Y., Chakhlevitch K.N. Batching in a two-stage flowshop with dedicated machines in the second stage // IIE Transactions. – 2004. – V. 36. – P. 87-93.
93. Scheduling a batching machine / P. Brucker, A. Gladky, H. Hoogeveen et al. // Journal of Scheduling. – 1998. – V. 1. – P. 31-54.
94. Potts C.N., Kovalyov M.Y. Scheduling with batching: a review // European Journal of Operational Research. – 2000. – V. 120. – P. 228-249.
95. Шафранский Я.М. Оптимизация детерминированных систем обслуживания с древовидным частичным порядком // Известия АН БССР. Сер. физ.-мат. наук. – 1978. – № 2. – С. 119.
96. Танаев В.С. Некоторые оптимизируемые функции одностадийного производства // Доклады АН БССР. – 1965. – Т. IX. – № 1. – С. 11-14.
97. Гордон В.С., Танаев В.С. Детерминированные системы обслуживания с одним прибором, древовидным упорядочением требований и экспоненциальными функциями штрафа // Вычислительная техника в машиностроении. – Мн.: Ин-т техн. кибернетики АН БССР, 1973, июнь. – С. 3-10.
98. Танаев В.С. К теории расписаний // Доклады АН БССР. – 1964. – Т. VIII. – № 12. – С. 792-794.
99. Шафранский Я.М. Об оптимальном упорядочении в детерминированных системах с древовидным частичным порядком обслуживания // Известия АН БССР. Сер. физ.-мат. наук. – 1978. – № 2. – С. 120.
100. Гордон В.С., Шафранский Я.М. Оптимальное упорядочение при последовательно-параллельных ограничениях предшествования // Доклады АН БССР. – 1978. – Т. XXII. – № 3. – С. 244-247.
101. Гордон В.С., Шафранский Я.М. Об оптимальном упорядочении при последовательно-параллельных ограничениях предшествования // Известия АН БССР. Сер. физ.-мат. наук. – 1978. – № 5. – С. 135.
102. Шафранский Я.М. О задаче минимизации функций на множестве перестановок частично упорядоченных элементов. // Известия АН БССР. Сер. физ.-мат. наук. – 1980. – № 5. – I. – С. 132; 1982. – № 1. – II. – С. 113.
103. Шафранский Я.М. Об одном свойстве приоритето-порождающих функций // Известия АН БССР. Сер. физ.-мат. наук. – 1981. – № 6. – С. 15-18.
104. Шафранский Я.М. Об алгоритме отыскания минимума приоритето-порождающих функций на специальных множествах перестановок. I, II // Известия АН БССР. Сер. физ.-мат. наук. – 1982. – № 3. – С. 38-42; 1983. – № 1. – С. 15-20.
105. Ковалев М.Я. Область сходимости одного алгоритма минимизации приоритето-порождающих функционалов // Алгоритмы и программы решения задач оптимизации. – Мн.: Ин-т техн. кибернетики АН БССР, 1983. – С. 21-35.
106. Shafransky Y.M., Tuzikov A.V. Construction of all optimal permutations under preceden-ce constraints // Тр. Института математики НАН Беларуси. Дискретная математика. – 2001. – Т. 8. – С. 106-113.
107. Complexity results for parallel machine problems with a single server / P. Brucker, C. Dhaenens-Flipo, S.A. Kravchenko et al. // Journal of Scheduling. – 2002. – V. 5. – P. 429–457.
108. Glass C.A., Shafransky Y.M., Strusevich V.A. Scheduling for parallel dedicated machines with a single server // Naval Research Logistics. – 2000. – V. 47. – P. 304-328.
109. Cheng T.C.E., Kovalyov M.Y. Scheduling a single server in a two-machine flow shop // Computing. – 2003. – V. 70. – P. 167-180.
Рецензия
Для цитирования:
Гордон В.С., Ковалев М.Я., Шафранский Я.М. ПОСТРОЕНИЕ РАСПИСАНИЙ ДЛЯ ОДНОСТАДИЙНЫХ СИСТЕМ ОБСЛУЖИВАНИЯ. Информатика. 2004;(4(04)):54-64.
Просмотров: 571
Послать статью по эл. почте 