Top

Published in:

2018 | OriginalPaper | Chapter

Single Machine Weighted Tardiness Problem: An Algorithm and Experimentation System

Authors : Kacper Petrynski, Robert Szost, Iwona Pozniak-Koszalka, Leszek Koszalka, Andrzej Kasprzak

Published in: Computational Collective Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper concentrates on the created algorithm for solving the single machine total weighted tardiness problem (SMTWT). The algorithm is based on searching the solution space along with the tree rules. The properties of the algorithm are studied taking into account the results of experiments made using the designed and implemented experimentation system. This system allows testing various configurations of the algorithm as well as comparing the effects obtained by this algorithm with effects of known meta-heuristic algorithms, which are based on Simulated Annealing and Invasive Weed Optimization. The paper shows that the proposed algorithm requires some improvements, however seems to be promising.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Chess Problem: CSA Algorithm Based on Simulated Annealing and Experimentation System

next chapter Large-Scale Evolutionary Optimization Using Multi-Layer Strategy Differential Evolution

Pinedo, M.: Planning and Scheduling in Manufacturing and Services. Springer, New York (2005). https://doi.org/10.1007/978-1-4419-0910-7CrossRefMATH

Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problem. Ann. Discrete Math. 1, 343–362 (1977)MathSciNetCrossRef

Cheng, T.C.E., Ng, C.T., Yuan, J.J., Liu, Z.H.: Single machine scheduling to minimize total weighted tardiness. Eur. J. Oper. Res. 165, 423–443 (2005)MathSciNetCrossRef

Geiger, M.J.: On heuristic search for the single machine total weighted tardiness problem – some theoretical insights and their empirical verification. Eur. J. Oper. Res. 207, 1235–1243 (2010)MathSciNetCrossRef

Congram, R.K., Pons, C.N., Van de Velde, S.I.: An iterated dyna-search algorithm for the single machine total weighted tardiness scheduling problem. J. Comput. 14, 52–67 (2000)

Ferrolho, A. Crisostomo, M.: Single machine total weighted tardiness problem with genetic algorithm. IEEE (2007)

Krol, D., Zydek, D., Koszalka, L.: Problem-indepenent approach to multiprocessor dependent task scheduling. Int. J. Electron. Telecommun. 58(4), 369–379 (2012)CrossRef

Bilge, U., Kurtulan, M., Kirac, F.: A tabu search algorithm for the single machine total weighted tardiness problem. Eur. J. Oper. Res. 176, 1423–1435 (2007)MathSciNetCrossRef

Van Laarhoven, P.J., Aarts, E.H., Lenstra, J.K.: Job shop scheduling by simulated annealing. Oper. Res. 40(1), 113–125 (1992)MathSciNetCrossRef

10.

Szumega, J.: Metaheuristic algorithms for solving the single machine total weighted tardiness problem. Report of Faculty of Electronics, Wroclaw University of Science and Technology, Wroclaw (2015)

11.

Sabamoniri, S., Asghari, K., Hosseini, J.M.: Solving single machine total weighted tardiness problem using variable structure learning automata. Int. J. Comput. Appl. (2012)

12.

Cakar, T., Koker, R.: Solving single machine total weighted tardiness problem with unequal release date using neurohybrid particle swarm optimization approach. Comput. Intell. Neurosci. (2015)

13.

Tasgetiren, M.F., Sevkli, M., Liang, Y-C., Gencyilmaz, G.: Particle swarm optimization algorithm for single machine total weighted tardiness problem. In: Proceedings of Congress on Evolutionary Computation (2004)

14.

Kostrzewa, D., Josinski, H.: The comparison of an adapted evolutionary algorithm with the invasive weed optimization algorithm based on the problem of predetermining the progress of distributed data merging process. In: Cyran, K.A., Kozielski, S., Peters, J.F., Stańczyk, U., Wakulicz-Deja, A. (eds.) Man-Machine Interactions. Advances in Intelligent and Soft Computing, vol. 59, pp. 505–514. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00563-3_53CrossRef

15.

Henderson, D., Jacobson, S.H., Johnson, A.W.: The theory and practice of simulated annealing. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics. International Series in Operations Research and Management Science, vol. 57, pp. 287–319. Springer, Boston (2003). https://doi.org/10.1007/0-306-48056-5_10CrossRef

16.

Bogalinski, P., Davies, D., Koszalka, L., Pozniak-Koszalka, I., Kasprzak, A.: Evaluation of strip nesting algorithms: an experimentation system for the practical users. J. Intell. Fuzzy Syst. 27(2), 611–623 (2014)

17.

Hudziak, M., Pozniak-Koszalka, I., Koszalka, L., Kasprzak, A.: Multi-agent pathfinding in the crowded environment with obstacles: algorithms and experimentation system. J. Intell. Fuzzy Syst. 32(2), 1561–1578 (2017)CrossRef

Title: Single Machine Weighted Tardiness Problem: An Algorithm and Experimentation System
Authors: Kacper Petrynski
Robert Szost
Iwona Pozniak-Koszalka
Leszek Koszalka
Andrzej Kasprzak
Publisher: Springer International Publishing
Book: Computational Collective Intelligence
Print ISBN: 978-3-319-98445-2

Electronic ISBN: 978-3-319-98446-9

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-98446-9_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner