ОПТИМАЛЬНОЕ ОБСЛУЖИВАНИЕ ТРЕБОВАНИЙ ДВУМЯ ПРИБОРАМИ ПРИ ЛИНЕЙНО УБЫВАЮЩИХ ФУНКЦИЯХ СТОИМОСТИ ВРЕМЕННЫХ ИНТЕРВАЛОВ
Аннотация
Рассматривается задача построения оптимального расписания обслуживания требований двумя параллельными приборами. В качестве целевой функции применяется линейная комбинация взвешенной суммы моментов завершения обслуживания требований и суммарной стоимости использования временных интервалов. В случае заданных для каждого из приборов линейно убывающих или постоянных последовательностей стоимостей временных интервалов предлагается точный псевдополиномиальный алгоритм динамического программирования.
Об авторах
А. В. Кононов
Институт математики им. С. Л. Соболева СО РАН
Россия
Россия
И. Н. Лущакова
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
Список литературы
1. 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.
2. Amazon EC2 Pricing Options [Electronic resource]. – 2016. – Mode of access : https://aws.amazon.com/ec2/pricing. – Date of access : 10.04.2016.
3. Wan, G. Scheduling with Variable Time Slot Costs / G. Wan, X. Qi // Naval Research Logistics. – 2010. – Vol. 57, no. 2. – P. 159–171.
4. 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.
5. 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.
6. 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.
7. Brucker, P. Scheduling Algorithms / P. Brucker. – Springer, 2004. – 367 p.
Рецензия
Для цитирования:
Кононов А.В., Лущакова И.Н. ОПТИМАЛЬНОЕ ОБСЛУЖИВАНИЕ ТРЕБОВАНИЙ ДВУМЯ ПРИБОРАМИ ПРИ ЛИНЕЙНО УБЫВАЮЩИХ ФУНКЦИЯХ СТОИМОСТИ ВРЕМЕННЫХ ИНТЕРВАЛОВ. Информатика. 2016;(3):80-86.
For citation:
Kononov A.V., Lushchakova I.N. SCHEDULING JOBS ON TWO PARALLEL MACHINES WITH LINEAR DECREASING TIME SLOT COSTS. Informatics. 2016;(3):80-86. (In Russ.)
Просмотров: 725
Послать статью по эл. почте 