Abstract
This paper deals with scheduling of tasks in cyclic flexible job shop scheduling problem (CFJSSP). We have proposed a new method of computing cyclic time for CFJSSP. This method is based on the known properties of the job shop problem as well as new properties of cyclic scheduling. We have developed two versions of proposed method: sequential and parallel. The parallel version is dedicated to the computing devices supporting vector processing. Finally, we have developed double paralyzed simulated annealing algorithms: fine grained - vector processing, multiple walk - multi core processing. Computation results, provided on market multicore processors, are presented for a set of benchmark instances from the literature.
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
Barnes, J.W., Chambers, J.B.: Flexible Job Shop Scheduling by tabu search, Graduate program in operations research and industrial engineering, Technical Report ORP 9609, University of Texas, Austin (1996)
Bożejko, W., Uchroński, M., Wodecki, M.: Parallel hybrid metaheuristics for the flexible job shop problem. Computers & Industrial Engineering 59, 323–333 (2010)
Bożejko, W., Uchroński, M., Wodecki, M.: The new golf neighborhood for the flexible job shop problem. In: Proceedings of the ICCS 2010. Procedia Computer Science, vol. 1, pp. 289–296. Elsevier (2010)
Bożejko, W.: On single-walk parallelization of the job shop problem solving algorithms. Computers & Operations Research 39, 2258–2264 (2012)
Bożejko, W., Pempera, J., Smutnicki, C.: Parallel Tabu Search Algorithm for the Hybrid Flow Shop Problem. Computers and Industrial Engineering 65, 466–474 (2013)
Brucker, P., Kampmeyer, T.: Cyclic job shop scheduling problems with blocking. Annals of Operations Research 159, 161–181 (2008)
Grabowski, J., Skubalska, E., Smutnicki, C.: On Flow Shop Scheduling with Release and Due Dates to Minimize Maximum Lateness. Journal of the Operational Research Society 34(7), 615–620 (1983)
Grabowski, J., Pempera, J.: New block properties for the permutation flow shop problem with application in tabu search. Journal of Operational Research Society 52, 210–220 (2001)
Hurink, E., Jurisch, B., Thole, M.: Tabu search for the job shop scheduling problem with multi-purpose machine. Operations Research Spektrum 15, 205–215 (1994)
Jia, H.Z., Nee, A.Y.C., Fuh, J.Y.H., Zhang, Y.F.: A modified genetic algorithm for distributed scheduling problems. International Journal of Intelligent Manufacturing 14, 351–362 (2003)
Kacem, I., Hammadi, S., Borne, P.: Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics Part C 32(1), 1–13 (2002)
Kampmeyer, T.: Cyclic Scheduling Problems, Ph. D. Thesis, University Osnabrück (2006)
Kechadi, M., Low, K.S., Goncalves, G.: Recurrent neural network approach for cyclic job shop scheduling problem. Journal of Manufacturing Systems 32, 689–699 (2013)
Mastrolilli, M., Gambardella, L.M.: Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling 3(1), 3–20 (2000)
Pempera, J., Smutnicki, C., Żelazny, D.: Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm. Procedia Computer Science 18, 936–945 (2013)
Xia, W., Wu, Z.: An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem. Computers and Industrial Engineering 48, 409–425 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Bożejko, W., Pempera, J., Wodecki, M. (2015). Parallel Simulated Annealing Algorithm for Cyclic Flexible Job Shop Scheduling Problem. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L., Zurada, J. (eds) Artificial Intelligence and Soft Computing. ICAISC 2015. Lecture Notes in Computer Science(), vol 9120. Springer, Cham. https://doi.org/10.1007/978-3-319-19369-4_53
Download citation
DOI: https://doi.org/10.1007/978-3-319-19369-4_53
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19368-7
Online ISBN: 978-3-319-19369-4
eBook Packages: Computer ScienceComputer Science (R0)