МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ДЛЯ СИСТЕМЫ С ДВУМЯ ПРИБОРАМИ И ОДНИМ СЕРВЕРОМ
Аннотация
Рассматривается задача минимизации суммарного времени обслуживания множества тре-бований на множестве двух идентичных параллельных приборов. Перед обслуживанием требования необходима загрузка, которая осуществляется сервером. Известно, что задача NP-трудна в сильном смысле. В работе предлагаются две модели целочисленного линейного программирования и алгоритм имитации отжига (simulatedannealingalgorithm). Предложенные подходы тестируются на примерах задач, содержащих до 250 требований.
Об авторах
Ф. Вернер
Университет Магдебурга, Германия
Германия
Германия
С. А. Кравченко
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
К. Хасани
Исламский университет Азад, Иран
Иран
Иран
Список литературы
1. Hall, N. Parallel machine scheduling with a common server / N. Hall, C. Potts, C. Sriskandarajah // Discrete Applied Mathematics. – 2000. – Vol. 102. – P. 223–243.
2. Complexity results for parallel machine problems with a single server / P. Brucker [et al.] //Journal of Scheduling. – 2002. – Vol. 5. – P. 429–457.
3. Kravchenko, S.A. A heuristic algorithm for minimizing mean flow time with unit setups /S.A. Kravchenko, F. Werner // Information Processing Letters. – 2001. – Vol. 79. – P. 291–296.
4. Wang, G. An approximation algorithm for parallel machine scheduling with a common server / G. Wang, T.C.E. Cheng // J. of the Operational Research Society. – 2001. – Vol. 52. – P. 234–237.
5. Weng, M.X. Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective / M.X. Weng, J. Lu, H. Ren // International J. of Production Economics. – 2001. – Vol. 70. – P. 215–226.
6. Dunstall, S. Heuristic methods for the identical parallel machine flowtime problem with set-up times / S. Dunstall, A. Wirth // Computers & Operations Research. – 2005. – Vol. 32. – P. 2479–2491.
7. Azizoglu, M. Scheduling parallel machines to minimize weighted flowtime with family setup times / M. Azizoglu, S. Webster // International J. of Production Research. – 2003. – Vol. 41. – P. 1199–1215.
8. Guirchoun, S. Total completion time minimization in a computer system with a server and two parallel processors / S. Guirchoun, P. Martineau, J.-C. Billaut // Computers & Operations Research. – 2005. – Vol. 32. – P. 599–611.
9. Hasani, K. Two heuristics for minimizing the makespan for the two-machine scheduling problem with a single server / K. Hasani, S.A. Kravchenko, F. Werner. – Magdeburg, 2013. – 20 p. – (Preprint / Otto-von-Guericke-University Magdeburg, Faculty of Mathematics ; № 08/13).
Рецензия
Для цитирования:
Вернер Ф., Кравченко С.А., Хасани К. МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ДЛЯ СИСТЕМЫ С ДВУМЯ ПРИБОРАМИ И ОДНИМ СЕРВЕРОМ. Информатика. 2014;(1):15-24.
For citation:
Werner F., Kravchenko S.A., Hasani K. MINIMIZING MEAN FLOW TIME FOR THE TWO-MACHINE SCHEDULING PROBLEM WITH A SINGLE SERVER. Informatics. 2014;(1):15-24. (In Russ.)
Просмотров: 713
Послать статью по эл. почте 