ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ ПОСТРОЕНИЯ РАСПИСАНИЙ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С РАЗЛИЧНЫМИ МАРШРУТАМИ
Аннотация
Задача построения оптимального расписания обслуживания m приборами n требований с различными маршрутами является NP-трудной при любом m > 2 для всех регулярных критериев, рассматриваемых в теории расписаний. Для ее решения разработаны эвристические алгоритмы для трех регулярных критериев: минимизации общего времени обслуживания заданных требований; минимизации суммарного времени обслуживания n требований и минимизации суммарного запаздывания обслуживания n требований. Экспериментальное сравнение разработанных программ с одним из наиболее эффективных эвристических алгоритмов показало их превосходство по времени реализации и достаточно близкие результаты по качеству получаемых расписаний в случае, когда число m больше числа n. Неравенство m > n выполняется, в частности, для задач, возникающих при составлении
оптимальных расписаний движения поездов по одноколейным железным дорогам.
Об авторах
О. ГоламиИран
Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев,
2. Ю.Н. Сотсков, В.A. Струсевич. – М. : Наука. Гл. ред. физ.-мат. лит, 1989. – 328 с.
3. Sequencing and scheduling: Algorithms and complexity / E.L. Lawler [et al.] // Handbooks in
4. Operations Research and Management Science. Logistics of Production and Inventory. – North-
5. Holland, 1993. – P. 445–522.
6. Carlier, J. An algorithm for solving the job shop problem / J. Carlier, E. Pinson // Management
7. Science. – 1989. – Vol. 35, № 2. – P. 164–176.
8. Brucker, P. The job-shop problem and immediate selection / P. Brucker, B. Jurusch,
9. A. Kramer // Annals of Operations Research. – 1994. – Vol. 50. – P. 73–114.
10. Sotskov, Yu.N. NP-hardness of shop-scheduling problems with three jobs / Yu.N. Sotskov,
11. N.V. Shakhlevich // Discrete Applied Mathematics. – 1995. – Vol. 59, № 3. – P. 237–266.
12. Adams, J. The shifting bottleneck procedure for jobshop scheduling / J. Adams, E. Balas,
13. D. Zawack // Management Science. – 1988. – Vol. 34, № 3. – P. 391–401.
14. Balas, Е. Guided local search with shifting bottleneck job shop scheduling / E. Balas,
15. A. Vazacopoulos // Management Science. – 1998. – Vol. 44, № 2. – P. 262–275.
16. Glover, F. Tabu search – part 1 / F. Glover // ORSA Journal on Computing. – 1989. – Vol. 1,
17. № 2. – P. 190–206.
18. Dell’Amico, M. Applying tabu search to the job-shop scheduling problem / M. Dell’Amico,
19. M. Trubian // Annals of Operations Research. – 1993. – Vol. 41. – P. 231–252.
20. Britto, R.A. Combined approach of the shifting bottleneck and tabu search heuristics for minimizing total weighted tardiness in job shop scheduling problems / R.A. Britto, G.M. Delgadillo,
21. J.P. Villalobos // Third International Conference on Production Research (ICPR-AM06). – Brazil,
22.
23. Werner, F. Genetic algorithms for shop scheduling problems: a survey / F. Werner. – Germany, Magdeburg, 2011. – (Preprint 31/11, FMA. Otto-von-Guericke-University).
24. Szpigel, B. Optimal train scheduling on a single line railway / B. Szpigel // Operations Research. – 1973. – Vol. 72. – P. 344–351.
Рецензия
Для цитирования:
Голами О., Сотсков Ю.Н. ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ ПОСТРОЕНИЯ РАСПИСАНИЙ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С РАЗЛИЧНЫМИ МАРШРУТАМИ. Информатика. 2012;(4(36)):45-55.
Просмотров: 694
Послать статью по эл. почте 