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 152–161Cite as

Study of Theoretical Properties of PSC-Algorithm for the Total Weighted Tardiness Minimization for Planning Processes Automation

  • Conference paper
  • First Online:

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

Abstract

We investigate and justify the efficiency of PSC-algorithm for solving the NP-hard in the strong sense scheduling problem of the total weighted tardiness of jobs minimization on one machine. The problem is used widely in the automation of planning processes in objects of different nature. As a result of the research, we identify and justify regions of the problem parameter values at which it is solved quickly and at which it requires a large computational effort. For each individual instance, a polynomial subalgorithm of \( O(n^{2} ) \) complexity constructs a sequence on which we determine the instance’s structure and its characteristics designating the instance’s complexity. We analyze the polynomial component of the PSC-algorithm which checks sufficient signs of optimality at all stages of the problem solving, in contrast to the existing methods. The optimal solution was achieved with the polynomial component for 27.3% of instances. We present experimental data on the solving time for problems with dimensions up to 300 jobs. We show that up to 68% of the generated benchmark instances are solved relatively quickly for any dimension. The PSC-algorithm is competitive by the computation time with the known method of Tanaka et al. and significantly exceeds it on instances from the determined regions of quick solving.

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.L.: Scheduling: Theory, Algorithms, and Systems. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-26580-3

    Book  MATH  Google Scholar 

  2. Heydari, M., Hosseini, S.M., Gholamian, S.A.: Optimal placement and sizing of capacitor and distributed generation with harmonic and resonance considerations using discrete particle swarm optimization. Int. J. Intell. Syst. Appl. (IJISA) 5(7), 42–49 (2013). https://doi.org/10.5815/ijisa.2013.07.06

    Article  Google Scholar 

  3. Wang, F., Rao, Y., Wang, F., Hou, Y.: Design and application of a new hybrid heuristic algorithm for flow shop scheduling. Int. J. Comput. Netw. Inf. Secur. (IJCNIS) 3(2), 41–49 (2011). https://doi.org/10.5815/ijcnis.2011.02.06

  4. Cai, Y.: Artificial fish school algorithm applied in a combinatorial optimization problem. Int. J. Intell. Syst. Appl. (IJISA) 2(1), 37–43 (2010). https://doi.org/10.5815/ijisa.2010.01.06

    Article  Google Scholar 

  5. Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16533-7

    Book  MATH  Google Scholar 

  6. Soltani, N., Soleimani, B., Barekatain, B.: Heuristic algorithms for task scheduling in cloud computing: a survey. Int. J. Comput. Netw. Inf. Secur. (IJCNIS) 9(8), 16–22 (2017). https://doi.org/10.5815/ijcnis.2017.08.03

    Article  Google Scholar 

  7. Garg, R., Singh, A.K.: Enhancing the discrete particle swarm optimization based workflow grid scheduling using hierarchical structure. Int. J. Comput. Netw. Inf. Secur. (IJCNIS) 5(6), 18–26 (2013). https://doi.org/10.5815/ijcnis.2013.06.03

    Article  Google Scholar 

  8. Mishra, M.K., Patel, Y.S., Rout, Y., Mund, G.B.: A survey on scheduling heuristics in grid computing environment. Int. J. Mod. Educ. Comput. Sci. (IJMECS) 6(10), 57–83 (2014). https://doi.org/10.5815/ijmecs.2014.10.08

    Article  Google Scholar 

  9. Sajedi, H., Rabiee, M.: A metaheuristic algorithm for job scheduling in grid computing. Int. J. Mod. Educ. Comput. Sci. (IJMECS) 6(5), 52–59 (2014). https://doi.org/10.5815/ijmecs.2014.05.07

    Article  Google Scholar 

  10. Hwang, K., Dongarra, J., Fox, G.: Distributed and Cloud Computing: From Parallel Processing to the Internet of Things. Morgan Kaufmann, Burlington (2012)

    Google Scholar 

  11. Brucker, P., Knust, S.: Complex Scheduling, 2nd edn. GOR-Publications Series, Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-23929-8

  12. Zgurovsky, M.Z., Pavlov, A.A.: Algorithms and software of the four-level model of planning and decision making. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications, 1st edn. Studies in Systems, Decision and Control, vol. 173, pp. 407–518. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-98977-8_9

  13. Zgurovsky, M.Z., Pavlov, A.A.: The total weighted tardiness of tasks minimization on a single machine. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications, 1st edn. Studies in Systems, Decision and Control, vol. 173, pp. 107–217. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-98977-8_4

  14. Tanaka, S., Fujikuma, S., Araki, M.: An exact algorithm for single-machine scheduling without machine idle time. J. Sched. 12(6), 575–593 (2009). https://doi.org/10.1007/s10951-008-0093-5

    Article  MathSciNet  MATH  Google Scholar 

  15. Kanet, J., Birkemeier, C.: Weighted tardiness for the single machine scheduling problem: an examination of precedence theorem productivity. Comput. Oper. Res. 40(1), 91–97 (2013). https://doi.org/10.1016/j.cor.2012.05.013

    Article  MathSciNet  MATH  Google Scholar 

  16. Kanet, J.: One-machine sequencing to minimize total tardiness: a fourth theorem for Emmons. Oper. Res. 62(2), 345–347 (2014). https://doi.org/10.1287/opre.2013.1253

    Article  MathSciNet  MATH  Google Scholar 

  17. Karakostas, G., Kolliopoulos, S., Wang, J.: An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates. ACM Trans. Algorithms 8(4), 1–16 (2012). https://doi.org/10.1145/2344422.2344430

    Article  MathSciNet  MATH  Google Scholar 

  18. Zgurovsky, M.Z., Pavlov, A.A.: Introduction. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications, 1st edn. Studies in Systems, Decision and Control, vol. 173, pp. 1–14. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-98977-8_1

  19. Tanaka, S., Fujikuma, S., Araki, M.: OR-library: weighted tardiness (2013). https://sites.google.com/site/shunjitanaka/sips/benchmark-results-sips. Accessed 08 Nov 2018

  20. Fisher, M.L.: A dual algorithm for the one machine scheduling problem. Math. Progr. 11(1), 229–251 (1976). https://doi.org/10.1007/BF01580393

    Article  MathSciNet  MATH  Google Scholar 

  21. Ding, J., Lü, Z., Cheng, T.C.E., Xu, L.: Breakout dynasearch for the single-machine total weighted tardiness problem. Comput. Indust. Eng. 98(C), 1–10 (2016). https://doi.org/10.1016/j.cie.2016.04.022

    Article  Google Scholar 

  22. Pavlov, A.A., Misura, E.B., Melnikov, O.V., Mukha, I.P.: NP-hard scheduling problems in planning process automation in discrete systems of certain classes. In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds.) Advances in Computer Science for Engineering and Education. ICCSEEA 2018. Advances in Intelligent Systems and Computing, vol. 754, pp. 429–436. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91008-6_43

Download references

Author information

Authors and Affiliations

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

    Alexander Anatolievich Pavlov, Elena Borisovna Misura, Oleg Valentinovich Melnikov, Iryna Pavlovna Mukha & Kateryna Igoryvna Lishchuk

Authors
  1. Alexander Anatolievich Pavlov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elena Borisovna Misura
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Oleg Valentinovich Melnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Iryna Pavlovna Mukha
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Kateryna Igoryvna Lishchuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexander Anatolievich Pavlov .

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

Pavlov, A.A., Misura, E.B., Melnikov, O.V., Mukha, I.P., Lishchuk, K.I. (2020). Study of Theoretical Properties of PSC-Algorithm for the Total Weighted Tardiness Minimization for Planning Processes Automation. 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_14

Download citation

Publish with us

Policies and ethics

Search

Navigation