SCHEDULING JOBS ON TWO PARALLEL MACHINES WITH LINEAR DECREASING TIME SLOT COSTS
Abstract
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.
About the Authors
A. V. Kononov
Институт математики им. С. Л. Соболева СО РАН
Russian Federation
Russian Federation
I. N. Lushchakova
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
References
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.
Review
For citations:
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.)
Views: 726
Email this article 