Abstract
We study three similar problems of scheduling of unrelated jobs on uniform parallel machines each having a distinct optimization criterion. In the first problem the criterion is the makespan minimization. In the second one the goal is to create a schedule, where the minimum of the completion times of the last jobs on the parallel machines is maximized (machine covering problem). In the third one the goal is to create a schedule with maximally uniform distribution of jobs among the machines. We propose the sufficient conditions of schedule optimality for these problems. First, optimality criteria for the analyzed problems were transformed into functions of makespan’s lower boundary deviation. This allows to define auxiliary optimization problems of the mixed-integer programming problems class. The objective of these auxiliary problems is to determine a perfect schedule - the one that gives the perfect value of the corresponding source criterion for the given volume of jobs. Perfect value allows us to determine the sufficient conditions of schedule optimality for all three problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Springer, New York (2008)
Zgurovsky, M., Pavlov, A.: Decision-Making in Network Systems with Limited Resources: Monograph. Naukova Dumka, Kyiv (2000)
Senthilkumar, P., Narayanan, S.: Literature review of single machine scheduling problem with uniform parallel machines. Intell. Inf. Manag. 2(8), 457–474 (2010)
Tawfeek, M.A., Elhady, G.F.: Hybrid algorithm based on swarm intelligence techniques for dynamic tasks scheduling in cloud computing. Int. J. Intell. Syst. Appl. (IJISA) 8(11), 61–69 (2016). https://doi.org/10.5815/ijisa.2016.11.07
Arya, L.K., Verma, A.: Child based level-wise list scheduling algorithm. Int. J. Mod. Educ. Comput. Sci. (IJMECS) 9(9), 24–31 (2017). https://doi.org/10.5815/ijmecs.2017.09.03
Kaur, S., Verma, A.: An efficient approach to genetic algorithm for task scheduling in cloud computing environment. Int. J. Inf. Technol. Comput. Sci. (IJITCS) 4(10), 74–79 (2012). https://doi.org/10.5815/ijitcs.2012.10.09
Chekuri, C., Bender, M.: An efficient approximation algorithm for minimizing makespan on uniformly related machines. J. Algorithms 41(2), 212–224 (2001)
Epstein, L., Sgall, J.: Approximation schemes for scheduling on uniformly related and identical parallel machines. In: Proceedings of 7th Annual European Symposium on Algorithms, pp. 151–162. Springer, Herzliya (1999)
Jeet, K., Dhir, R., Singh, P.: Hybrid black hole algorithm for bi-criteria job scheduling on parallel machines. Int. J. Intell. Syst. Appl. (IJISA) 8(4), 1–17 (2016). https://doi.org/10.5815/ijisa.2016.04.01
Sivasankaran, P., Ravi Kumar, M., Senthilkumar, P., Panneerselvam, R.: Heuristic to minimize makespan in uniform parallel machines scheduling problem. Udyog Pragati 33(3), 1–15 (2009)
Liao, C., Lin, C.: Makespan minimization for two uniform parallel machines. Int. J. Prod. Econ. 84(2), 205–213 (2003)
Koulamas, C., Kyparisis, G.: Makespan minimization on uniform parallel machines with release times. Eur. J. Oper. Res. 157(1), 262–266 (2004)
Liao, C., Lin, C.: Makespan minimization for multiple uniform machines. Comput. Ind. Eng. 54(4), 983–992 (2008)
Walter, R., Wirth, M., Lawrinenko, F.: Improved approaches to the exact solution of the machine covering problem. J. Sched. 20(2), 147–164 (2017)
Walter, R.: Comparing the minimum completion times of two longest-first scheduling-heuristics. CEJOR 21, 125–139 (2013)
Azar, Y., Epstein, L.: On-line machine covering. In: ESA: European Symposium on Algorithms: Algorithms – ESA 1997, pp. 23–36. Springer, Austria (1997)
Sperkach, M.: The problem of defining the maximum start moment of execution of tasks with a common tough due date on parallel machines with different speeds. Sci. J. 63, 12–18 (2015). NTUU “KPI”, Informatics, Operation and Computer Science
Zhdanova, O., Sperkach, M.: Scheduling tasks on parallel devices of various productivity to maximize uniformity of devices’ load. Sci. J. 1156, 92–106 (2015). V. Karazin Kharkiv National University, series Mathematical Modelling. Information Technology, Automated Control Systems
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Popenko, V., Sperkach, M., Zhdanova, O., Kokosiński, Z. (2020). On Optimality Conditions for Job Scheduling on Uniform Parallel Machines. In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Computer Science for Engineering and Education II. ICCSEEA 2019. Advances in Intelligent Systems and Computing, vol 938. Springer, Cham. https://doi.org/10.1007/978-3-030-16621-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-16621-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-16620-5
Online ISBN: 978-3-030-16621-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)