informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-135Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGМИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ДЛЯ СИСТЕМЫ С ДВУМЯ ПРИБОРАМИ И ОДНИМ СЕРВЕРОМMINIMIZING MEAN FLOW TIME FOR THE TWO-MACHINE SCHEDULING PROBLEM WITH A SINGLE SERVERВернерФ.WernerF.face@neicon.ruКравченкоС. А.KravchenkoS. A.kravch@newman.bas-net.byХасаниК.HasaniK.face@neicon.ruУниверситет Магдебурга, ГерманияGermanyОбъединенный институт проблем информатики НАН БеларусиBelarusИсламский университет Азад, ИранIslamic Republic of Iran201404102016011524Copyright © Вернер Ф., Кравченко С.А., Хасани К., 20162016Вернер Ф., Кравченко С.А., Хасани К.Werner F., Kravchenko S.A., Hasani K.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/135

Рассматривается задача минимизации суммарного времени обслуживания множества тре-бований на множестве двух идентичных параллельных приборов. Перед обслуживанием требования необходима загрузка, которая осуществляется сервером. Известно, что задача NP-трудна в сильном смысле. В работе предлагаются две модели целочисленного линейного программирования и алгоритм имитации отжига (simulatedannealingalgorithm). Предложенные подходы тестируются на примерах задач, содержащих до 250 требований.

The problem of scheduling jobs on two parallel machines to minimize the sum of completion times is considered. Each job requires a setup which is done by a single server. It is known that this problem is strongly NP-hard. Two mixed integer linear programming models and a simulated annealing algorithm are proposed. The performance of these algorithms is evaluated for instances with up to 250 jobs.

ReferencesHall, N. Parallel machine scheduling with a common server / N. Hall, C. Potts, C. Sriskandarajah // Discrete Applied Mathematics. – 2000. – Vol. 102. – P. 223–243.Hall, N. Parallel machine scheduling with a common server / N. Hall, C. Potts, C. Sriskandarajah // Discrete Applied Mathematics. – 2000. – Vol. 102. – P. 223–243.Complexity results for parallel machine problems with a single server / P. Brucker [et al.] //Journal of Scheduling. – 2002. – Vol. 5. – P. 429–457.Complexity results for parallel machine problems with a single server / P. Brucker [et al.] //Journal of Scheduling. – 2002. – Vol. 5. – P. 429–457.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.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.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.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.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.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.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.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.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.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.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.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.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).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).

The authors declare that there are no conflicts of interest present.