Abstract
In the work there is considered an NP-hard flexible job shop problem. Its solution lies in allocation of operations to machines and determination of the sequence of their execution. There is also a method of construction of approximate algorithms presented, based on the idea of descent search, determining the allocation of operations. What is more, there were computational experiments conducted to investigate the correlation between the size of the neighborhood and the quality of solutions determined by the algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
1. Barnes J., Chambers J., Flexible job shop scheduling by tabu search, Graduate program in operations research and industrial engieering. The University of Texas at Austin, 1996.
2. Bożejko W., Uchroński M., Wodecki M., Parallel hybrid metaheuristics for the flexible job shop problem, Computers & Industrial Engineering 59 (2010) 323–333.
3. Bożejko W., Uchroński M.,Wodecki M., The new golf neighborhood for the flexible job shop problem, Proceedings of the ICCS 2010, Procedia Computer Science 1 (2010), Elsevier, 289–296.
4. Bożejko W., Uchroński M., Wodecki M., Parallel neuro-tabu search algorithm for the job shop scheduling problem, Proceedings of ICAISC 2013, Lecture Notes in Artificial Intelligence No. 7895, Springer (2013), 489–499.
5. Brandimarte P., Routing and scheduling in flexible job shop by tabu search, Annals of Operations Research, 41, 1993, 157–183.
6. Gao J., Sun L., Gen M., A hybrid genetic and varioble neighborhood descent algorithm for flexible job shop scheduling problem, Computers and Operations Research, 35, 2008, 2892–2907.
7. Hmida A., Haouari M., Huguet M., Lopez P., Discrepancy search for the flexible job shop scheduling problem, Computers and Operations Research, 37, 2010, 2192–2201.
8. Mastrolilli M., Gambardella L., Effective neighborhood functions for the flexible job shop problem, Journal of scheduling, 3(1), 2000, 3–20.
9. Nowicki, E., Smutnicki, C., (1996): A fast taboo search algorithm for the job shop problem, Management Science 42, 797–813.
10. Saidi-MehrabadM., Fattahi P., Flexible job shop scheduling with tabu search algorithm, Int. J. Adv. Manuf. Technol., 32, 2007, 563–570.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Bożejko, W., Uchroński, M., Wodecki, M. (2017). The k-opt algorithm analysis. The flexible job shop case. In: Mitkowski, W., Kacprzyk, J., Oprzędkiewicz, K., Skruch, P. (eds) Trends in Advanced Intelligent Control, Optimization and Automation. KKA 2017. Advances in Intelligent Systems and Computing, vol 577. Springer, Cham. https://doi.org/10.1007/978-3-319-60699-6_36
Download citation
DOI: https://doi.org/10.1007/978-3-319-60699-6_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-60698-9
Online ISBN: 978-3-319-60699-6
eBook Packages: EngineeringEngineering (R0)