The availability of doctors is a major problem that people are facing especially in the rural areas. On the other hand, there are some areas which have large number of doctors than actually required. Because of this uneven distribution of doctors, people in the remote areas remain deprived of medical facilities and are living an unhealthy lifestyle. This paper describes the optimization of schedule of doctors using graph coloring and backtracking approach so that they can be evenly distributed across various locations and the people who are currently not getting proper medical facilities will be able to get treatments on time. This technique serves two purposes, namely, resource optimization and cost optimization. An optimized schedule of doctors will be provided. Only the required number of doctors will be present at a particular location. The remaining doctors will be sent to some other locations. If implemented on a large scale such as in government schemes, this can be a great contribution to the society.

Graph coloring, resource optimization, cost optimization

[1] M. L. Ginsberg, “Dynamic Backtracking”, Journal of Artificial Intelligence Research 1, pp. 25-46, 1993.
[2] R. Dechter, D. Frost, “Backtracking Algorithms for Constraint Satisfaction Problems”, University of California, Irvine 1999.
[3] A. Mohamed, M. Yusoff, I. A. Mohtar, S. Mutalib, S. A. Rahman “Constraint Satisfaction Problem Using Modified Branch and Bound Algorithm”, WSEAS Transactions, Vol. 7, Issue 1, 2008.
[4] R. Marino, G. Parisi, F. R. Tersenghi “The Backtracking Survey Propagation Algorithm for Solving Random K-SAT Problems”, Nature Communications, 2016.
[5] S. Bhowmick, P. D. Hovland, “Improving the Performance of Graph Coloring Algorithms through Backtracking”, M. Bubak et al (Eds.): ICCS 2008, Part I, LNCS 5101, pp. 873-882, 2008.
[6] J.T. Camino, S. Mourgues, C. Artigues, L. Houssin, “A Greedy Approach Combined with Graph Coloring for Non-Uniform Beam Layouts Under Antenna Constraints in Multibeam Satellite Systems”, In the proceedings of 7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications, 2014.
[7] B. Hussin, A.S.H. Basari, A.S. Shibghatullah, S.A. Asmai, “ Exam Timetabling Using Graph Colouring Approach", In the proceedings of IEEE Conference on Open Systems (ICOS2011), Langkawi, Malaysia, 2011.
[8] N. Barnier, P. Brisset, “Graph coloring for Air Traffic Flow Management”, CP-AI-OR 2002, 4th Fourth International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimisation Problems, Mar 2002, Le Croisic, France, 2002.
[9] M. Zais, M. Laguna, “A graph coloring approach to the deployment scheduling and unit assignment problem”, Springer Science+Business Media New York (outside the USA) 2015.
[10] S.Ahmed, “Applications of Graph Coloring in Modern Computer Science”, IJCIT, ISSN 2078-5828 (PRINT), ISSN 2218-5224 (ONLINE), VOLUME 03, ISSUE 02, 2012.