Skip to main content
SpringerLink
Log in
Book cover

International Conference on Computer Science, Engineering and Education Applications

ICCSEEA 2019: Advances in Computer Science for Engineering and Education II pp 103–112Cite as

On Optimality Conditions for Job Scheduling on Uniform Parallel Machines

  • Conference paper
  • First Online:

  • 709 Accesses

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 938))

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.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

References

  1. Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Springer, New York (2008)

    MATH  Google Scholar 

  2. Zgurovsky, M., Pavlov, A.: Decision-Making in Network Systems with Limited Resources: Monograph. Naukova Dumka, Kyiv (2000)

    Google Scholar 

  3. Senthilkumar, P., Narayanan, S.: Literature review of single machine scheduling problem with uniform parallel machines. Intell. Inf. Manag. 2(8), 457–474 (2010)

    Google Scholar 

  4. 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

    Article  Google Scholar 

  5. 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

    Article  Google Scholar 

  6. 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

    Article  Google Scholar 

  7. Chekuri, C., Bender, M.: An efficient approximation algorithm for minimizing makespan on uniformly related machines. J. Algorithms 41(2), 212–224 (2001)

    Article  MathSciNet  Google Scholar 

  8. 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)

    Google Scholar 

  9. 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

    Article  Google Scholar 

  10. 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)

    Google Scholar 

  11. Liao, C., Lin, C.: Makespan minimization for two uniform parallel machines. Int. J. Prod. Econ. 84(2), 205–213 (2003)

    Article  Google Scholar 

  12. Koulamas, C., Kyparisis, G.: Makespan minimization on uniform parallel machines with release times. Eur. J. Oper. Res. 157(1), 262–266 (2004)

    Article  Google Scholar 

  13. Liao, C., Lin, C.: Makespan minimization for multiple uniform machines. Comput. Ind. Eng. 54(4), 983–992 (2008)

    Article  Google Scholar 

  14. Walter, R., Wirth, M., Lawrinenko, F.: Improved approaches to the exact solution of the machine covering problem. J. Sched. 20(2), 147–164 (2017)

    Article  MathSciNet  Google Scholar 

  15. Walter, R.: Comparing the minimum completion times of two longest-first scheduling-heuristics. CEJOR 21, 125–139 (2013)

    Article  MathSciNet  Google Scholar 

  16. Azar, Y., Epstein, L.: On-line machine covering. In: ESA: European Symposium on Algorithms: Algorithms – ESA 1997, pp. 23–36. Springer, Austria (1997)

    Google Scholar 

  17. 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

    Google Scholar 

  18. 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

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, 37 Prosp. Peremohy, Kyiv, Ukraine

    Volodymyr Popenko, Maiia Sperkach & Olena Zhdanova

  2. Faculty of Electrical and Computer Engineering, Cracow University of Technology, 24 Warszawska Str., Cracow, Poland

    Zbigniew Kokosiński

Authors
  1. Volodymyr Popenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maiia Sperkach
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Olena Zhdanova
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zbigniew Kokosiński
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maiia Sperkach .

Editor information

Editors and Affiliations

  1. School of Educational Information Technology, Central China Normal University, Wuhan, Hubei, China

    Zhengbing Hu

  2. Mechanical Engineering Research Institute of the Russian Academy of Sciences, Moscow, Russia

    Sergey Petoukhov

  3. “Igor Sikorsky Kiev Polytechnic Institute”, National Technical University of Ukraine, Kiev, Ukraine

    Ivan Dychka

  4. Halmos College of Natural Sciences and Oceanography, Nova Southeastern University, Ft. Lauderdale, FL, USA

    Matthew He

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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

Publish with us

Policies and ethics

Search

Navigation