Analyzing the timetable of nurses at government hospital using graph coloring with Integer Linear Programming / Nurul Irdina Azhar, Nur Amira Natasya Mohd Zainuddin and Lidiya Lai Muhammad Firdaus Lai

The increase of patients in hospitals reflects the importance of nurses in caring for these patients. Nursing management is both mundane and tedious, and also highly scientific, technical, and service-oriented. Therefore, the work schedule for the nurses is critically important in order to avoid eccentricity or deviation of tasks and collision of shifts between different nurses. Usually, the nurses' timetable is done manually, which will be a hassle to satisfy the nurses’ preferences and making it fair in a short amount of time. Thus, conflict resolution of the timetable can be solved by using Graph Coloring model. This study demonstrates the application of Graph Coloring model theory in schedulling the timetable of nurses at governments’s hospital. Graph Coloring can be defined as a method where colors are assigned to certain constraints to find optimal solution by determining minimal colorings for the corresponding graph. The objective of the study is to optimize the nurse’s work schedule by applying the graph coloring and to compare the efficiency of nurses’ timetable before and after at government hospital using graph coloring. This study will used the data of the nurses’ timetable of the nurse for a month from a government hospital, and formulate a model using the Graph Coloring theory, which is, by grouping the factor, constructing conflict matrix, and construct the color network graph. The performance is evaluated by using the integer linear programming. The result of the study, which is the timetable generated by using Phython will be used to achieve the first objective and it will be compared with the timetable collected originally from the government hospital, in order to achieve the second objective.