informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-72Research ArticleСТАТЬИ ПО МАТЕРИАЛАМ КОНФЕРЕНЦИЙARTICLES ON THE MATERIALS CONFERENCEОПТИМАЛЬНОЕ ОБСЛУЖИВАНИЕ ТРЕБОВАНИЙ ДВУМЯ ПРИБОРАМИ ПРИ ЛИНЕЙНО УБЫВАЮЩИХ ФУНКЦИЯХ СТОИМОСТИ ВРЕМЕННЫХ ИНТЕРВАЛОВSCHEDULING JOBS ON TWO PARALLEL MACHINES WITH LINEAR DECREASING TIME SLOT COSTSКононовА. В.KononovA. V.alvenko@math.nsc.ruЛущаковаИ. Н.LushchakovaI. N.IrinaLushchakova@yandex.ruИнститут математики им. С. Л. Соболева СО РАНRussian FederationБелорусский государственный университет информатики и радиоэлектроникиBelarus201630092016038086Copyright © Кононов А.В., Лущакова И.Н., 20162016Кононов А.В., Лущакова И.Н.Kononov A.V., Lushchakova I.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/72

Рассматривается задача построения оптимального расписания обслуживания требований двумя параллельными приборами. В качестве целевой функции применяется линейная комбинация взвешенной суммы моментов завершения обслуживания требований и суммарной стоимости использования временных интервалов. В случае заданных для каждого из приборов линейно убывающих или постоянных последовательностей стоимостей временных интервалов предлагается точный псевдополиномиальный алгоритм динамического программирования.

We consider a scheduling problem with two parallel machines to minimize the sum of total weighted completion time and total machine time slot costs. In the case of the constant or linear decreasing sequences of time slotcosts we suggest an exact pseudopolynomial DP algorithm.

ReferencesZhao, G. Cost-aware scheduling algorithm based on PSO in Cloud Computing Environment / G. Zhao // Intern. J. of Grid and Distributed Computing. – 2014. – Vol. 7, no. 1. – P. 33–42.Zhao, G. Cost-aware scheduling algorithm based on PSO in Cloud Computing Environment / G. Zhao // Intern. J. of Grid and Distributed Computing. – 2014. – Vol. 7, no. 1. – P. 33–42.Amazon EC2 Pricing Options [Electronic resource]. – 2016. – Mode of access : https://aws.amazon.com/ec2/pricing. – Date of access : 10.04.2016.Amazon EC2 Pricing Options [Electronic resource]. – 2016. – Mode of access : https://aws.amazon.com/ec2/pricing. – Date of access : 10.04.2016.Wan, G. Scheduling with Variable Time Slot Costs / G. Wan, X. Qi // Naval Research Logistics. – 2010. – Vol. 57, no. 2. – P. 159–171.Wan, G. Scheduling with Variable Time Slot Costs / G. Wan, X. Qi // Naval Research Logistics. – 2010. – Vol. 57, no. 2. – P. 159–171.Zhao, Y. On scheduling with non-increasing time slot cost to minimize total weighted completion time / Y. Zhao, X. Qi, M. Li [Electronic resource]. – 2016. – Mode of access : http://link.springer.com/article/10.1007/s10951-015-0462-9#/page-1. – Date of access : 10.04.2016.Zhao, Y. On scheduling with non-increasing time slot cost to minimize total weighted completion time / Y. Zhao, X. Qi, M. Li [Electronic resource]. – 2016. – Mode of access : http://link.springer.com/article/10.1007/s10951-015-0462-9#/page-1. – Date of access : 10.04.2016.Bruno, J. Scheduling independent tasks to reduce mean finishing time/ J. Bruno, E.G. Coffman, Jr., R. Sethi // Communications of the ACM. – 1974. – Vol. 17. – P. 382–387.Bruno, J. Scheduling independent tasks to reduce mean finishing time/ J. Bruno, E.G. Coffman, Jr., R. Sethi // Communications of the ACM. – 1974. – Vol. 17. – P. 382–387.Sequencing and Scheduling: Algorithms and Complexity / E.L. Lawler [et al.] // Handbooks in Operations Research and Management Science. – North-Holland, Amsterdam, 1993. – Vol. 4. – P. 445–522.Sequencing and Scheduling: Algorithms and Complexity / E.L. Lawler [et al.] // Handbooks in Operations Research and Management Science. – North-Holland, Amsterdam, 1993. – Vol. 4. – P. 445–522.Brucker, P. Scheduling Algorithms / P. Brucker. – Springer, 2004. – 367 p.Brucker, P. Scheduling Algorithms / P. Brucker. – Springer, 2004. – 367 p.

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