Рассматривается задача минимизации суммарного времени обслуживания множества тре-бований на множестве двух идентичных параллельных приборов. Перед обслуживанием требования необходима загрузка, которая осуществляется сервером. Известно, что задача NP-трудна в сильном смысле. В работе предлагаются две модели целочисленного линейного программирования и алгоритм имитации отжига (simulatedannealingalgorithm). Предложенные подходы тестируются на примерах задач, содержащих до 250 требований.
Вернер Ф. , Кравченко С. А., Хасани К. МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ДЛЯ СИСТЕМЫ С ДВУМЯ ПРИБОРАМИ И ОДНИМ СЕРВЕРОМ. Информатика. 2014;(1):15-24.
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).
