Graph Coloring Applied to Medical Doctors Schedule
Conference Paper
توفيق, فردوس . 2016
رابط المنشور على الويب:
اسم المؤتمر:
The Tenth International Conference on Advanced Engineering Computing and Applications in Sciences ADVCOMP 2016
تاريخ المؤتمر:
الأحد, تشرين اﻷول (أكتوبر) 9, 2016
المنظمة الراعية:
the International Academy Research and Industry Association (IARIA)
مستخلص المنشور:
Graph Coloring Applied to Medical Doctors Schedule
Ferdous M O Tawfiq, Kholoud Khalid S Al-qahtani
King Saud University- Riyadh. Saudi Arabia
e-mails: {ftoufic@ksu.edu.sa, 432201096@student.ksu.edu.sa}
Abstract— Scheduling shifts is a tiresome and time
consuming task in any business, and particularly in hospitals
where errors are costly, rules are plentiful and changes are
rapid. The person performing this function (Rota Organizer)
will have to keep track of all the employees concerned,
distributing hours fairly and avoiding collisions. Rules
regulating working hours and breaks have to be followed
and the qualifications of individual employees need to be
considered. Hours are spent every day on this task in every
ward.The goal of this paper is to solve Doctors Scheduling
Problem (DSP) and initialize a fair roster for two wards of
Pediatric Department (PD) in Prince Sultan Military MedicalCity (PSMMC) in Saudi Arabia.So to find a solution ofDSP, we used Graph Coloring,which is one of the methods used mostly to solve this problem.
Keywords- graph coloring;doctors roster; greedy
algorithm.
I. INTRODUCTION
In the study of graphs, which are mathematical structures used to model pair wise relations between objects. A “graph” is made up of vertices (or nodes) and lines called edges that connect them.
Graphs can be used to model many types of relations and processes in physical, biological, social and information systems.Graph coloring has been studied extensively for the past decades. The surge for studying graph coloring in recent times has resulted in countless real-life problem applications, which include scheduling problems. Research presented in this paper aims to provide an effective procedure for solving Doctors Scheduling Problem (DSP) related to their shifts. DSP is a major problem faced by many hospitals all over the world. W e tried in two wards of PSMMC to establish a roster for one month as a beginning to achieve a general procedure for every month.
After exploring relevant references the problem will be described in details, followed by the formalation of relevant
coloring problem and its solution with recent results.
II. RELATED WORK
Nurses' rostering problem has been studied by many researchers[1][4][6]. Where reference [6] used graph coloring for scheduling with a specific different algorthim ( other than greedy algorithm). [1][4]used graph coloring to make the schedule by greedy algorithm but for a few number of nurses. In this paper graph coloring is used to solve doctors' scheduling problem (DSP) related to their shifts for one month in two wards of PSMMC.Realizing that establishing a general procedure to establish a roster for every month has not been done yet for any hospital in Saudi Arabia, this work might lead to a follow up by more reasearch. For the advanteges of this procedure to be clear, a needed comparison will be done shorlty.
III. STATEMENT OF THE PROBLEM
In this paper, we shall consider a scheduling problem for
Pediatric Department of Prince Sultan Military Medical City
(PSMMC) in Riyadh/ Saudi Arabia. It is considered one of
the top governmental hospitals with almost twenty seven
departments. There are more than five thousand doctors in
the hospital.
We communicated with Dr. Nawaf Al khayat (Dr.N.A.,) in
PD of PSMMIC; he is a consultant and supervisor of resident
doctors training in PSMMIC.
Usually, monthly doctors roster are made manually before the
end of each month. Rota organizer has the responsibility to
publish next month's roster. Even though making monthly
rosters manually requires great effort, it does not resolve all
conflicts. Instead, it has created more tedious adjustments to
accomplish needed tasks.
There are consultants, senior and junior doctors working in
this department. This paper is concerned with scheduling
shifts for junior and senior doctors in two of the department
wards for one month only.
There are three types of doctors: Consultants, Seniors (R3 &
R4) and Juniors (R1 & R2), where number indicates trainee
year. In PSMMC pediatric department, which has thirteen
wards, there are thirty eight resident doctors; R1, R2, R3 and
R4. It has been specified for us to work on scheduling shifts
for only two wards: PG (Pediatrics General) and PGICU
(Pediatrics General Intensive Care Unit) wards. In addition,
we were given the following information:
- Each working day consists of eight to eight and half
hours.
2. Each shift consists of twenty four hours.
3. Every doctor who has participated in a shift will not
be given anther shift for the next three days.
4. There are twenty two junior and sixteen senior
doctors.
5. In each working month there are doctors who are
excluded from participating in shifts due to other
responsibilities or personal circumstances.
We chose September 2016 to be the month we consider for
scheduling. In September, only eighteen doctors are excluded
which is the least number of doctors among other
remaining months. From list of names given to us by
Dr.N.A., we have listed doctors who will participate in
September shifts (S.S.). There are twelve juniors and eight
seniors available.
In the proposed solution for DSP ( Doctors Scheduling
Problem), we need to assign doctors into shifts.
IV. FORMULATION OF A GRAPH COLORING PROBLEM
First, we divided doctors into four shift groups. Each groups
has two seniors and four juniors based on department daily
requirement, and the fact that we only have twelve juniors
and eight seniors in this month.
Since both PG and PGICU involved doctors cannot
accomplished needed shifts while meeting restrictions of the
department, we had several options.
We chose to involve one doctor outside PG and PGICU,
each day of September to complement needed shifts. So we
had A, B, C and D groups to cover first four consecutive days
which will represent the same groups for the following four
days, and so on. This implies a need for additional four
juniors { SUB.1, SUB.2, SUB.3, SUB.4}, (SUB.1 refer to
first substitute for a junior), to complement required number
of doctors (8 senior and 16 juniors in conditions 3 above).
| Group | Doctors |
| A | , , , , , . |
| B | , , , , , . |
| C | , , , , , . |
| D | , , , , , |
| Table 1. Groups of S.S.D. | |
By using above data an incident matrix is initiated for S.S.D.It is a 24 × 24 matrix.
If any two doctors are in same group then ij-th entry is 1
otherwise it is 0.
Now, since the incident matrix is a big matrix ,we hadto divide it to4 submatrices (blocks) which includesall nonzero entries(for the sake of presenting results in apprpriate template)
| 0 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 0 | |
| Frist submatrix . |
||||||
| 0 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 0 | |
| second submatrix . | ||||||
| 0 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 0 | |
| Third submatrix . | ||||||
| 0 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 0 | |
| Fourth submatrix . | ||||||
Each block is submatrix, for first block say
where . coloum is for , coloum is for , …, and last coloum ( coloum) is for . Rows has been delt with in same way.So , and are submatrices in the same way.. ( is a matrix).
By using the incident matrix , a graph is constructed with
S.S.D. as vertices. If two doctors are in same group then they
are linked with an edge.
Next, we colored the graph by using Greedy algorithm. We
started with red as color number one and take color
number two to be yellow. Color number three is gray, also
color number four is orange and color number five is green,
we needed six colors, so the last color is going to be blue.
Now we will start with vertices representing seniors; first
senior each day will be colored by red. The second senior
adjacent to first one will be colored yellow. Since every day
there are four juniors adjacent to each other and to the red and
yellow seniors, the first one of these juniors every day
will be colored gray, the second one is orange, third one
green, and last one is blue. See the following Figure.
Figure1. A Colored Graph of The Doctors.
Above we have included substitutes in the coloring scheme to organize needed shifts. This means first day group will be repeated in fifth day, second group will be repeated in sixth day, third group will be repeated in seventh day and fourth group will be repeated in eighth day. So, to finish up the process the cycle will be repeated every four day.
| Group | Doctors |
| , , , | |
| , , , | |
| , , , | |
| , , , | |
| , , , | |
| , , , | |
| Table 2. Groups After Applying Graph Coloring. | |
Accordingly we formulated a table where S.S.D. doctors in G1,G2,…, G6 should be in the same ward if they are in the same group.
???????
Based on restrictions specified in Section 4 concerning the problem of making doctors roster for September 2016 in PD of PSMMC, we have divided doctors into shifts groups.
Then,we applied the graph theory to these groups so that each vertex represents a doctor and there is an edge between any two doctors in one shift group, see section 3.1 for details.
After graphing, we used Greedy Algorithm to color. We used six colors for twenty four vertices, where each four vertices have one color.
In the graph, doctors represented by vertices of the same color are grouped as one since they will be working in the same ward.
The shift groups (Table 1) are then used to form a matrix elements of first columns represent numbering of doctors and element of second column represent colors of these doctors which are numbering like that (1 is red, 2 is yellow, 3 is gray, 4 is orange, 5 is green and 6 is blue). We used this matrix to create code by Matlab. The output of this code is distribution in the wards.
V. RESULTS
The following table shows first phase of result: distribution of doctors in wards. In this table columns represent wards of the department, and rows represent names of doctors in shiftgroup. We note that each element represents the participation of specific doctor in a shift, i.e.,
| A | B | C | D | E | F | |
| Table 3. Distribution of Doctors in Wards After converting Result From Matlab. |
||||||
In this paper, we have finalized a roster for September 2016 shifts of two wards PG and PGICU in PD of PSMMC. This roster has taken into consideration departmental restrictions in doing so, we are hoping to have saved PG and PGICU from getting into misunderstandings, as well as any other relevant troubles. Instead of consuming time and effort to generate doctors roster, the staff can concentrate on other important medical duties.
At the end, we can confirm that steps leading to a roster of September 2016 as detailed in section 4, can be used and applied for other months, nurses as well as doctors.
| F | E | D | C | B | A | Day | Date |
| Sun. | 4 Sep. | ||||||
| Mon. | 5 | ||||||
| Tue. | 6 | ||||||
| Wed. | 7 | ||||||
| Thu. | 8 | ||||||
| Fri. | 9 | ||||||
| Sat. | 10 | ||||||
| Sun. | 11 | ||||||
| Mon. | 12 | ||||||
| Tue. | 13 | ||||||
| Wed. | 14 | ||||||
| Thu. | 15 | ||||||
| Fri. | 16 | ||||||
| Sat. | 17 | ||||||
| Sun. | 18 | ||||||
| Mon. | 19 | ||||||
| Tue. | 20 | ||||||
| Wed. | 21 | ||||||
| Thu. | 22 | ||||||
| Fri. | 23 | ||||||
| Sat. | 24 | ||||||
| Sun. | 25 | ||||||
| Mon. | 26 | ||||||
| Tue. | 27 | ||||||
| Wed. | 28 | ||||||
| Thu. | 29 | ||||||
| Fri. | 30 | ||||||
| Sat. | 1 Oct. | ||||||
| Table 4.The Final Roster For The PD. | |||||||
VII. FUTURE WORK
Many hospitals take a long time to prepare doctors roster, which is fair to everybody. Instead of consuming time in generating it, we hope to generalize in future work a software, where minimum data is required to have a roster for any month. Before this generalization is established we need to compare algorithms that can be used for the same purpose.
ACKNOWLEDGMENT
Thanks to Deanship of Scientific Research at King Saud University (KSU) for funding this work through undergraduate students research support program project on (USRSP).
REFERENCES
[1] Amponsah, S.K, Agyeman, E., Okran, K.G., Graph Coloring, an Approach to Nurses Scheduling. American- Eurasian Journal of Scientific Research 6(1). Ghana, 2011, 1-5.
[2] Butt, R., Introduction to Numerical Analysis Using Matlab. USA, 2007.
[3] Diestel, R., Graph Theory. Springer-Verlag, New Your, 2000, 98-103.
[4] Gideon, A., A Nurse Scheduling Using Graph Coloring. Master thesis submitted, Mathematics Department, Kwame Nkrumah University, Ghana, 2013, 1-4, 35, 53-77.
[5] Harju, T., Graph Theory. Lecture Notes in Mathematics, Finland, 2011, 53-60.
[6] Kumara, B.T.G.S., Perera, A.A.I, Automated System For Nurse Scheduling Using Graph Coloring. Indian Journal of Computer Science and Engineering (IJCSE), 2011, 476-485.
[7] Rosen, K., Discrete Mathematics and It's Applications. New York, 2012.
[8] Rosen, K., Chromatic Graph Theory. Michigan, 2009.
[9] Shekhar, S., Graph Theory. Lecture Notes in Mathematics, US, 2012, 137-139.
[10] Skogvold, A.; Saether, T.; Moseby, S.; Westby, P., Flexible Duty Roster for Doctors in Hospital, 2009, 1-3.
[11] West, D., Introduction to Graph Theory. New Jesey, 2001.
[12] Wilson, R., Introduction to Graph Theory. England, 1996.
[13] Wren, A., Scheduling, Timetabling and Rostering- a Special Relationship?. Lecture Notes in Computer Science. Springer-verlag, Berlin, 1996, 46-75.
[14] Dharwardker,A., 2006. The Vertex Coloring Algorithm. Available at: <http://www.dharwadker.org/vertex_colorin g/>, (March 2016).
[15] Greedy Coloring Algorithm.August 2015. Available at:
<https://www.youtube.com/watch?v=vGjsi8 NIpSE>
ملف مرفق:
| المرفق | الحجم |
|---|---|
 Graph Coloring Applied to Medical Doctors Schedule | 314.97 كيلوبايت |