A mathematical model to schedule manpower and solve using genetic
algorithm
SeyedHasanHataminasab^{1},
Seyed Mohsen Mirjalili^{*2}, MahdiehYavari^{3},
MohamadrezaPakdel^{4}
^{1}Department of
Business Management, Yazd Branch, Islamic Azad University, Yazd, Iran
Email: Hataminasab@iauyazd.ac.ir
^{2}Department of Industrial Management, Yazd Branch, Islamic Azad
University, Yazd, Iran
Email: mohsenmirjalili23@yahoo.com
^{3}Department of Industrial Management, Yazd Branch, Islamic Azad
University, Yazd, Iran
Email: m_yavari88@yahoo.com
^{4}Department of Business Management, Yazd Branch, Islamic Azad
University, Yazd, Iran
Email: pakdel_manager@yahoo.com
*Corresponding
Author: Mohsenmirjalili23@yahoo.com
Abstract
The
staffing schedule according to the objectives of the system and minimizing the
cost of production is among the most important factors in productivity.
Manpower planning as the means of ensuring the human resources needed to
achieve the organization's goals and its mathematical modeling is important for
planners. Given that to solve staffing timing issue is very time consuming, in
this paper, genetic algorithm is used to solve the proposed model. Therefore,
many mathematical models have been used to formulate the scheduling in
organizations and through a variety of methods have been tried to solve them.
Considering the absence right for the personnel is one of the advantages of the
proposed model. Since the cost is regarded as damage, the
problem has changed to the cover mode. First, parameters and all restrictions
are included with respect to information of the problem and modeling is
implemented; then, the problem is solved with genetic algorithm. Finally,
results of computations obtained based on different evaluations about the
personnel’s number suggest that in the given problem, 90 personnel can satisfy
restrictions and reduce penalties at the best.
Key
words: staff scheduling, genetic algorithm, work pattern, mathematical
modeling.
1. Introduction
Scheduling
is a tool for optimal use of available resources. Resources and jobs may have
various types in scheduling and along with the development of industrial world
the resources become more critical (1). The timing of the resources leads to
the increase of the efficiency and utilization of capacity, reduction of the
time required to complete tasks and ultimately the increase profitability of an
organization. Scheduling is the allocation process of resources limited to
activities over time and optimization of one or more objective function.
Resources include manpower, machines, materials, auxiliary equipment etc.
Appropriate scheduling of resources such as machines and human resources must
be considered as a necessity in today's competitive environment (2).
For
modeling optimization problems the problem should be described by mathematical
variables and relations so that the optimization problem to be simulated. A
general and initial model of the scheduling can be of maximizing or minimizing
types and can be defined as follows (3):
…
Based
on the system requirements this model can be divided into different classes.
Overall classification of the works done in the field of manpower planning in
is defined by three particular species: (4)
1.
Nurses' scheduling that conducted researches
are according to the planning of nursing care and services provided by them in
shifts and week days.
2.
The crew scheduling on the basis of services
provided by the working groups in subway stations, train, air and urban
transportation services
3.
Staff scheduling on the type of an individual's
work shift
Anthony
Wren in one of his papers studied in detail the topic of planning, scheduling
and shift of work and the relationship between them (5). According to him,
scheduling is to arrange the elements in a pattern of time or location in order
to reach or approach the objectives so that limits associated with these
elements are met completely or nearly (7,6).
Through
the expansion and development of the planning model, Aklin
evaluated three shifts with 30 nurses and then compared the results with the
results of the Forbidden Search (by Dazland). Results
were same in terms of the solution, but very different in terms of the
flexibility (8).
There
are few articles about the timing of railway crew by the use of genetic
algorithm to solve problems. For example, articles written by Van et al or Kalyng Wood which are generally used for short distances
(9).
A
number of useful articles to review solving techniques of projects scheduling
problems in case of limited resources have provided by Herolen
et al (10).
Bukter has examined 21 innovative scheduling methods to solve the projects
scheduling problem with limited resources (11). In addition, Bukter using critical path method and its computations has
proposed a more precise innovative algorithm (12). In recent years, Nuter et al have investigated algorithms based on a factor
to solve the mentioned problem and Lova et al have
presented methods based on priority rules (13).
In 1997, Jen and Cheng showed that in genetic algorithm,
to take the size of the initial population larger, the number of generations
and crossing rate may result in expansion of the search space and consequently
faster convergence of the algorithm (14). In 1999, Barndimart
solved the problem of flexible process program with multiobjective function
via a precise optimization algorithm. In the same year, Gedjati
presented an approach compound of metaheuristic methods on the basis of
genetic algorithm to solve the problem FJS (15).
Burus and Mario in a paper titled as “Reconstruction of nurses’ scheduling:
computational insight for the problem size parameters” tried to obtain insights
and perceive outcomes and outputs of the nurses’ scheduling various strategies.
Moreover, they considered limitation of the time and number of the nurses for
adaption with the real conditions.
Iyonis et al in a paper titled as “The twophase adaptive approach of
neighborhood variables to schedule nurses” attempted to solve nurses’
scheduling problem using the search algorithm in twophase variable
neighborhood. In their research, at first in order to show efficiency it is
recommended that the algorithm to be used for all nurses. Furthermore, according to evaluations, better results have
achieved in the samples and the available approach distinguishes itself from
other methods (17).
Komarodinet al in an article titled as “Quality problem of manpower
tasks list a methodology to solve tasks list quality by modification of the
personnel structure” attempted to at first introduce quality problem of
manpower tasks list and then to implement a threestage methodology which is
capable to assess personnel structure quality in order to achieve a
highquality personnel tasks list relying on current tasks algorithm. Based on the results, certain changes have
been suggested in personnel levels. Results also emphasize that the threestage
algorithm refers to better personnel structures about adaption with the tasks
list (18).
In another research titled as “An evolutionary approach
to nursing task list” Burus and Mario suggest a
metaheuristic evolutionary method to solve the problem of nursing task program
and indicate that how the proposed method operates continually in different
situations (19).
Mehran and Ashuk in their study titled as
“"Integer linear programming  explorationbased for heterogeneous scheduling,
parttime workers” tried to at first determine the personnel work shifts
appropriately and then assign the personnel according to a suitable scheduling
program. To do this, they use integer linear programming. Moreover, they
compared the results obtained randomly with the reference article and proved
the strength of the model (20).
Tesayand Lee in a paper titled as “Twophase modeling using genetic algorithm to
solve nursing scheduling” with the consideration of requirements, government
regulations and nurses’ shift preferences, at first arranged nurses’ work and
their vacation and via the genetic algorithm solved and optimized scheduling as
well as investigated any shift nurses’ violation of government regulations,
applied hospital management requirements and a fair schedule. At the second
stage, a list of nursing program was arranged and genetic algorithm to solve
the optimized program was proved. Results have shown that this algorithm is a
suitable tool to solve nursing schedule program. In addition, it can easily
modify different issues the hospital encounters (21).
2.Modelling the problem
The studied model considers the absence right
to reduce costs. The problem definition is as the following: weekly scheduling
is done for n personnel at s day shift so that the staff are divided
into work teams, any staff work time is represented by c*t day at a cycle of C
and scheduling is done based on the three factors of worker absence, weekly
need and cost reduction with regard to the firm weekly need to the staff.
·
Assumptions of the mathematical programming
model for staff scheduling is as follows:
ü The number of personnel is determined.
ü The number of work teams is determined.
ü The staff degree is clear.
ü Amount of the demand for any day shift is clear.
ü The number of day working shifts is determined.
ü Duration of each cycle is specified.
ü The number of the head operator is also specified for
each system.
ü The cost of not covered demand is clear.
ü The cost of the additional operator is identified.
ü The cost of each team is determined.
ü Noncoverage cost of each individual's day shift is
determined.
• Model objectives:
The main objective is to minimize all costs as follows:
1. Noncoverage cost of each individual's day shift
2. The cost of each team
3. The cost of not covered demand
4. The cost of the additional head operator
The aim of the model is to develop a work pattern for
each individual model with minimal additional costs to the system.
• integer programming formulation:
}I} = Representative of the operator
{K} The
representative of the personnel degree, k = 1, ....,Deg
}J} = The representative of day work shift, j = 1, ...., C * t
}T} = The representative of shift t = 1, ..., s
{H}= The
representative of the team, H = 1, ...., TIM
}C} = The representative of the work cycle
• Decision variables:
I _{XIJ} 1  person I is assigned to the day
shift J with staff degree of k or 0 otherwise.
O_{1}1 The person I is the senior staff. Or 0
otherwise
f_{Ih} 1 The person I is associated with the team h. Or 0 otherwise
• Parameters:
{N} = the number of operators
{D} = the number of degrees
{S} = number of shifts
{TIM} = number of teams
{DJk} = the day shift J demand
for personnel with degree k
{SHIFTI} = number of current working day shifts for
personnel I
{WDEMAND} = weight of the demand
{WHEAD} = weight of the operator
{WTEAM} = weight of the team
{Wdeg} = coefficient of degree
The proposed model:
S.t
The proposed algorithm
In many science and engineering problems
commonly we face an objective function that we want to optimize it. Engineering
issues are analyzed with different methods. Genetic algorithm can be classified
as a numerical method, direct and random search. Genetic algorithm is a
searching technique for solving problems using genetic model. This algorithm is
one of the populationbased algorithms which its basic idea is driven from the
evolution theory. Genetic algorithm is of the most powerful and widely used
algorithms in search and optimization problems. One reason for the popularity
of the genetic algorithm is that it does not require a high level of advanced
mathematical models. These algorithms follow the law of development. The
evolution is performed by chromosomes intercourse and the mutation is done on
them and chromosomes with more fitness have more chance to be transferred to
the future generations (22).
Total flow of the genetic algorithm
To be based on population means that more than
one solution is considered in any iteration. The set of solutions examined in any
iteration is called a population of solutions. Rules and recipes of genetic
algorithm are in such a way that the population of any iteration leads to the
definition or creation of the next iteration of the population. It should be
noted that initial solutions of the population could be selected at random from
the area justified or created by innovative methods. Children of birth may lead
to solutions better or worse than their parents. Acceptance of worse solutions
as the new generation's solutions depends on an approach that is used to
implement the genetic algorithm. In some approaches only those solutions are
accepted that are better than their parents and in some cases worse responses are
transmitted to future population. This process of generating new populations of
the previous one continues until the algorithm stops (23).
Steps of the algorithm are as follows:
1  The Beginning: Create a population of n
chromosomes randomly.
2. Valuation: Evaluate fitness of f (x) of
each chromosome x in the population.
3. New
population: Form a new population. Repeat these steps until the new population
is complete:
Selection: Select two chromosomes from the
population according to their fitness.
Composition: Regarding the possibility of
composition, combine parents to form new children.
Mutation: Regarding the possibility of
mutation, mutate children at any position of chromosome.
Approve: Include new children in the new
population.
Replacement: Apply the new population for
process of the algorithm.
Figure1. Total flow of the genetic algorithm
3. Design of genetic
algorithm to solve the model:
The algorithm is proposed to solve the
presented genetic model coded via MATLAB software and will be used to extract
the model solutions.
31. Solutions structure with
chromosome and creating the initial population:
In this study, for coding efficiency and increasing
understanding of the problem a matrix structure similar to figure 1 is used to
display the solution. Each column represents zero and a work shift and each row
represents a certain staff schedule. Due to the nature of decision variables x_{ij}, answer of a matrix is zero and one. The
amount of 1 to x_{ij} represents assignment
of shifts j to individual i and the size of the
matrix is in accordance with the number of individuals multiplied by the number
of current shifts.
in the model problem
21=7*3 and
N=X; hence, the matrix is X * 21.
Figure2. Structure of the answer
Columns 1 to 3 represent 3 shifts of Saturday, 4 to 6 represent
3 shifts of Sunday and so on until columns 19 to 21 that represent 3 shifts of
Friday. Since each staff has to work a shift per day, to satisfy the relation 5
the sum of each row should be 7 and values of zero and for 3 columns should be
created once. To satisfy the relation 6 the columns sum should be 30 demands per
day. Any chromosome which satisfies the relations 5 and 6 will be considered as
a possible chromosome and then to satisfy relations 7, 8 and 9 we assign
numbers 1 to 5 to sections of the matrix zero and 1 with the amount 1 so that 6
individuals to be allocated to each team. Next, numbers 1 and 2 is assigned as
degree to the matrix satisfied the relation 7 so that at to each column only
one of 1 to be belonged as the head operator and the relations 8 to 9 to be
satisfied. Considering this method, to
solve the problem limitations are satisfied automatically and the solution
providing the lowest cost is considered as the problem solution.
32. Genetic algorithm operators
321. Intersection operator
To generate new chromosomes is the basis of the
intersection operator. For this, vertical intersection operator has been used.
A random number was generated in the
interval
satisfaction degree
of the relation 5 will be effective and then the problematic chromosomes should
be rebalanced.
322. Mutation operator
Mutation operator is mostly to transform. Therefore, two
numbers are selected in intervals
and
for values i and j. If the selected x_{ij} is zero, it will be transformed to 1 and if x_{ij} is 1, it will be transformed to zero.
Then, only the satisfaction degree of relations 5 and 6 may become problematic
that should be modified.
33. How to select the parent population
To select the parent population, normalization method has
been applied to the present generation living. Normalization is done as the
following:
Where
represents standard deviation of
generation g and
rpresents the chromosome i life in generation g.
The parent population involves those chromosomes that the
value of
is nonzero.
34. Stop criterion
To stop the algorithm, the below criteria is used:
1Maximum of the generations
2 Minimum value of the generation allowed variance
Whenever one of the criteria is satisfied, the algorithm
will stop.
341. Parameters included in genetic algorithm:
Table1. Parameters included in genetic algorithm:
Maximum generation number

The number of each generation population

Minimum variance

Maximum allowed need (second)

1000

200

5

3600

342. Computational results
To solve the model, a real problem with the below
specifications was used that is presented by table.
According to the problem internal parameters, we solved
the intended problem with 45, 60, 75, 90 and 100 personnel. Computational
results are as the following table:
Table2. Internal parameters of the problem
Internal parameters of the problem

The personnel number

X

Shift number

3

Time interval

7

Teams number

5

Degrees number

2

Team leaders number

0.033

Shifts demand

30

Shift weight

10

Head operator weight

3

Team weight

5

Degree coefficient

3

Conclusion
In the present paper, an integerprogramming
approach to solve a generalized manpower scheduling program has been presented
as a new mathematical model with multi shifts mode and with the assumption of
individuals’ personnel degree and coverage mode. In other words, in the case of
an individual’s absence due to the inclusion of damage costs to the system, the
model changes to the coverage mode. The proposed model was created regarding
the problem parameters and then the genetic algorithm was applied in order to
solve the model in a larger scale. All internal parameters of the problem were
assumed definite. According to the problem and personnel values, we realized
that involvement of 90 personnel and consideration of one shift for any
personnel per day may cause the lowest cost, satisfy the model limitations
better and decrease loses. Thus, it is suggested that in order to schedule the
staff the firms should employ a meta heuristicalgorithm like the genetic algorithm for a better decision; as
well as, since human resource is considered as the organization’s capital,
planners and designers of the human resource could schedule the personnel program
through the identification and inclusion of different factors of scheduling and
thus satisfy the staff and improve their consent and productivity of the
organization.
Table3. Computational results
problem

Personnel number

Objective function (cost)

Time (second)

1

45

1713

1350

2

60

1472

533

3

75

1252

384

4

90

1019

138

5

100

1863

121

References
1.
Adams, J., Balas, E., &Zawack, D. (1988). The shifting bottleneck procedure for jobshop scheduling. Management Science, 34(3), 391401.
2.
TavakoliMoghadam,
R., Fatemi – Ghomi, S.M.T.,
Afsari, F. and Safari N. “A mathematical model for
Manpower scheduling solved by tabu search”. Amirkabir J. of Science and Technology, Vol.16
, No. 61B, 2005. p.p. 1322.
3.
Asgharpour MJ.
(1998). The book "linear programming" Tehran
University Press.
4.
TavakkoliMoghaddam, R.
and Islami, Sh., (2006). Paper "presentation of
a new mathematical model for staff scheduling and solving it using a genetic
algorithm,
ُsharifacademic research journal, No.
36, pp. 2131.
5.
Wern,
A., “Scheduling, time tabling and rosteringa special
Relat", School of Computer studies, University
of Leeds (1995).
6.
Warner, D. and Prawda, J., “A
mathematical programming model for scheduling nursing personnel in a
hospital", Management Science, 19, pp. 411422 (1972).
7.
Miller, H., Pierskalla, W. and Rath, G., “Nurse scheduling using mathematical
programming", Operations Research, 24, pp. 875870 (1976).
8.
Aickelin, U.
and Dowlands, K.A., “Exploiting problem structure in
a genetic algorithm approach to nurse rostering
problem", Journal of Scheduling, 3, pp. 139153 (2000).
9.
Kwan, R.S.K., Wren, A. and Kwan, A.S.K., “Hybrid genetic algorithms
for scheduling Bus and train driver", School of Computer Studies,
University of Leeds (2000).
10.
Herroelen,
W., Demeulemeester, E., De Reyck,
B., “ResourceConstrained Project Scheduling: a Survey of Recent Developments”,
Computers & Operations Research, Vol. 25, 1998, pp. 279–302.
11.
Boctor,
F.F., “Heuristics for Scheduling Projects with Resource Restrictions and
Several Resource–Duration Modes”, International Journal of Production Research,
Vol. 31, 1993, pp. 2547–2558.
12.
Boctor,
F.F, “ResourceConstrained Project Scheduling by Simulated Annealing”,
International Journal of Production Research, Vol. 34, 1996, pp. 2335–2351.
13.
NotezKnotts,
G., Dror, M., Hartman, B., “AgentBased Project
Scheduling”, IIE Transactions, Vol. 32, 2000. p.p 387401.
14.
Gen, M., Cheng, R., “Genetic Algorithms and Engineering Design”,
John Wiley & Sons, (1997)
15.
Brandimarte,
P., “Theory and Methodology, Exploiting Process Plan Flexibility in Production
Scheduling: A MultiObjective Approach”, European Journal of Operational
Research, 114, 1999, pp. 5971.
16.
BroosMaenhout,
Mario Vanhoucke.” Reconstructing nurse schedules:
Computational insights in the problem size parameters” Elsevier Journal, Omega
41 (2013) 903–918.
17.
Ioannis X. Tassopoulos, Ioannis P. Solos, Grigorios N. Beligiannis.” Α
two phase adaptive variable neighborhood approach for nurse rostering”
Elsevier Journal, Computers &OperationsResearch60, (2015)150–169
.
18.
Komarudin , MarieAnne Guerry , Tim De Feyter , Greet VandenBerghe.” The
roster quality staffing problem – A methodology for improving the roster
quality by modifying the personnel structure” European Journal of Operational
Research, 230
(2013) 551–562.
19.
BroosMaenhout , Mario Vanhoucke.” An evolutionary
approach for the nurse rerostering problem” Computers
& Operations Research 38 (2011) 1400–1411.
20.
MehranHojati,
Ashok S. Patil.” An integer linear programmingbased
heuristic for scheduling heterogeneous, parttime service employees” European
Journal of Operational Research 209 (2011) 37–50.
21.
Sherman H.A. Li,ChangChun
Tsai. ” A twostage modeling with genetic algorithms for the nurse scheduling problem:
Expert Systems with Applications”, 36, (2009), 9506–9512.
22.
Monajjemi,
AM., MasoodianNematbakhsh, N (2009). "Automatic
timing table design for university courses using genetic algorithms",
Faculty of Engineering, University of Isfahan, Educational Technology Journal,
Volume 4, Issue 2, pp. 113127.
23.
Nasrsdrabady, AR.,Taghavi, N., (2004). The book
"Introduction tometaheuristic algorithm" ,Pendare Pars Publications.