Abstract
Fuzzy graph model can represent a complex, imprecise and uncertain problem, where classical graph model may fail. In this paper, we propose a fuzzy graph model to represent the examination scheduling problem of a university and introduce a genetic algorithm based method to find the robust solution of the scheduling problem that remains feasible and optimal or close to optimal for all scenarios of the input data. Fuzzy graph coloring method is used to compute the minimum number of days to schedule the examination. But problem arises if after the examination schedule is published, some students choose new courses in such a way that it makes the schedule invalid. We call this problem as fuzzy robust coloring problem (FRCP). We find the expression for robustness and based on its value, robust solution of the examination schedule is obtained. The concept of fuzzy probability of fuzzy event is used in the expression of robustness, which in turn, is used for fitness evaluation in genetic algorithm. Each chromosome in the genetic algorithm, used for FRCP, represents a coloring function. The validity of the coloring function is checked keeping the number of colors fixed. Fuzzy graphs with different number of nodes are used to show the effectiveness of the proposed method.
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
Blue, M., Bush, B., Puckett, J.: Unified approach to fuzzy graph problems. Fuzzy Sets and Systems 125(3), 355–368 (2002)
Goldberg, D.E., et al.: Genetic algorithms in search, optimization, and machine learning, vol. 412. Addison-Wesley, Reading (1989)
Hasuike, T.: Robust shortest path problem based on a confidence interval in fuzzy bicriteria decision making. Information Sciences 221, 520–533 (2013)
Lim, A., Wang, F.: Robust graph coloring for uncertain supply chain management. In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences, HICSS 2005, p. 81b. IEEE (2005)
Muñoz, S., Teresa Ortuño, M., Ramırez, J., Yáñez, J.: Coloring fuzzy graphs. Omega 33(3), 211–221 (2005)
Sunitha, M.: Studies on fuzzy graphs. Ph.D. thesis, Cochin University of Science and Technology (2001)
Sunitha, M., Vijayakumar, A.: Complement of a fuzzy graph. Indian Journal of Pure and Applied Mathematics 33(9), 1451–1464 (2002)
Wang, F., Xu, Z.: Metaheuristics for robust graph coloring. Journal of Heuristics 19(4), 529–548 (2013)
Yáñez, J., Ramırez, J.: The robust coloring problem. European Journal of Operational Research 148(3), 546–558 (2003)
Zadeh, L.A.: Fuzzy sets versus probability. Proceedings of the IEEE 68(3), 421 (1980)
Zadeh, L.A.: Probability measures of fuzzy events. Journal of Mathematical Analysis and Applications 23(2), 421–427 (1968)
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
Dey, A., Pradhan, R., Pal, A., Pal, T. (2015). The Fuzzy Robust Graph Coloring Problem. In: Satapathy, S., Biswal, B., Udgata, S., Mandal, J. (eds) Proceedings of the 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2014. Advances in Intelligent Systems and Computing, vol 327. Springer, Cham. https://doi.org/10.1007/978-3-319-11933-5_91
Download citation
DOI: https://doi.org/10.1007/978-3-319-11933-5_91
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11932-8
Online ISBN: 978-3-319-11933-5
eBook Packages: EngineeringEngineering (R0)