Abstract
In this paper, parallel simulated annealing with genetic enhancement algorithm (HSG) is presented and applied to permutation flow shop scheduling problem which has been proven to be \(\mathcal{NP}\)-complete in the strong sense. The metaheuristics is based on a clustering algorithm for simulated annealing but introduces a new mechanism for dynamic SA parameters adjustment based on genetic algorithms. The proposed parallel algorithm is based on the master-slave model with cooperation. Fuzzy arithmetic on fuzzy numbers is used to determine the minimum completion times C max . Finally, the computation results and discussion of the algorithms performance are presented.
The work was supported by MNiSW Poland, within the grant No. N N514 232237.
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
Bożejko, W., Wodecki, M.: Solving the Flow Shop Problem by Parallel Simulated Annealing. In: Wyrzykowski, R., Dongarra, J., Paprzycki, M., Waśniewski, J. (eds.) PPAM 2001. LNCS, vol. 2328, pp. 236–244. Springer, Heidelberg (2002)
Dubois, D., Prade, H.: Theorie des Possibilites. In: Applications a la representation des connaissances en informatique. MASSON, Paris (1988)
Dumitru, V., Luban, F.: Membership functions, some mathematical programming models and production scheduling. Fuzzy Sets and Systems 8, 19–33 (1982)
Grabowski, J., Wodecki, M.: A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers & Operations Research 31, 1891–1909 (2004)
Izzettin, T., Serpil, E.: Fuzzy branch-and-bound algorithm for flow shop scheduling. Journal of Intelligent Manufacturing 15, 449–454 (2004)
Ishibuschi, H., Murata, T.: Scheduling with Fuzzy Duedate and Fuzzy Processing Time. In: Słowiński, R., Hapke, M. (eds.) Scheduling Under Fuzziness, pp. 113–143. Springer, Heidelberg (2000)
Nowicki, E., Smutnicki, C.: A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research 91, 160–175 (1996)
Osman, I., Potts, C.: Simulated Annealing for Permutation Flow-Shop Scheduling. OMEGA 17(6), 551–557 (1989)
Peng, J., Liu, B.: Parallel machine scheduling models with fuzzy processing times. Information Sciences 166, 49–66 (2004)
Ram, J.D., Sreenivas, T.H., Subramaniam, G.K.: Parallel simulated annealing algorithms. Journal of Parallel and Distributed Computing 37(2), 207–212 (1996)
Reeves, C.: A Genetic Algorithm for Flowshop Sequencing. Computers & Operations Research 22(1), 5–13 (1995)
Tsujimura, Y., Park, S.H., Change, I.S., Gen, M.: An effective method for solving flow shop problems with fuzzy processing times. Computers and Industrial Engieering 25(1-4), 239–242 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bożejko, W., Czapiński, M., Wodecki, M. (2010). Parallel Hybrid Metaheuristics for the Scheduling with Fuzzy Processing Times. In: Rutkowski, L., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds) Artifical Intelligence and Soft Computing. ICAISC 2010. Lecture Notes in Computer Science(), vol 6114. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13232-2_46
Download citation
DOI: https://doi.org/10.1007/978-3-642-13232-2_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13231-5
Online ISBN: 978-3-642-13232-2
eBook Packages: Computer ScienceComputer Science (R0)