# A New Model for Reassignment of Tasks to Available Employees in Iraq’s Firms

Authors: Dhurgam Kalel Ibrahim Alsaad; Reza Ghanbari; Ali Akbar Sohrabi; Khatere Ghorbani Moghadam
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

Generalized assignment problem (GAP) is a well-known problem in the combinatorial optimization. This problem is a specific form of assignment problem (AP) when the employees can carry out more than one task simultaneously or each work can be assigned to more than one employee. In this paper, a new model is proposed for reassigning tasks on the available employees of Iraq companies when at least one of the jobholders is absent. Likewise, the returning workers from long holidays assumption are incorporated. Finally, a heuristic algorithm for solving reassignment tasks on laborers is introduced.


---

## Body

## 1. Introduction

Generalized assignment problem is one of the well-known problems in combinatorial optimization, which has been widely applied in many real-world situations. The significant achievement of the GAP came in 1975 when Ross and Soland introduced a new perspective of assignment problem (AP) [1], following which substantial papers have been published. In 1976, Sahni and Gonzalez [2] proved that GAP is an NP-hard problem. Therefore, many papers have been presented to solve this problem based on heuristic algorithms. Cattrysse and Van Wassenhove had an excellent survey about algorithms could be used to solve this problem [3]. Romejin and Morales [4] also introduced some greedy algorithms to solve this problem. Because being applicable, the GAP was influenced by many real-life problems. Balachandran, in 1976, used the GAP model to assign jobs to computer networks [5].From the scratch of GAP, many different models of GAP have been introduced. Mozzola and Neebe [6] proposed a min-max GAP, and it was called bottleneck GAP (BGAP). In this model, they tried to minimize the maximum fines of assignment of n jobs to m workers. In 1993, Mozzola and Neebe [7] introduced some algorithms to solve the BGAP. In 1989, Mozzola et al. [8] proposed a new model of GAP, where constraints had the nonlinear structure. This nonlinear feature was because of the interaction property between works which should be carried out by the same worker. Fu et al. [9] investigated the BGAP when works and workers were considered under uncertainty, and they proposed a state-of-the-art algorithm to solve their problem. Glover et al. [10] suggested a GAP model when performing a work by workers who have different efficiency levels, and it was called multilevel GAP (MGAP). Laguna et al. [11] proposed a Tabu search algorithm to solve this problem. Their algorithm was based on neighborhoods with ejection chain structure, and this feature reduces time consumption. Another GAP model was introduced by Nauss [12] in 2004. In this model, workers can violate the capacity constraint in exchange for extra costs, and they suggested a branch and bound algorithm to solve it. By investigation in the literature of GAP, we can meet many other types of GAPs ranging from dynamic to stochastic GAP models. In 2017, Xiong and Huai [13] considered a new outlook about GAP. They presented a nonlinear integer GAP model in which one or more than one person is required to carry out one single task. In this way, they suggested a new branch-and-bound algorithm to solve the quadratic integer GAP. See other models of GAP in [14–16].The model proposed in this paper is a combination of some previously discussed GAPs, and it is not similar to the other models. We attempt to model a prevalence problem of Iraq’s companies. In this country, employees require to have a long holiday because of their country’s policy and environment as well. This problem is a challenging problem for Iraq’s companies. Therefore, finding an excellent way to manage this phenomenon is essential, and it can increase the performance of Iraq’s firms. To deal with this problem, here, a comprehensive model is presented, where it can help managers of companies to find the best way to minimize the overtime of current employees, maximizing correlation between employees’ work and finally maximizing the workers’ skills.The rest of the paper is organized as follows: in Section2, a new GAP model for reassignment of tasks to available laborers is introduced. In Section 3, a model for employees to come back from vacation is suggested. We conclude in Section 4. Some numerical solution will be surveyed in the Appendix.


## 2. Mathematical Model

In this section, we propose a new model to reassign work to available workers. This problem is a challenging problem in the Iraq country, and it goes back to their policies and rules. The cause of providing this correlation is that, in many of Iraq’s firms, it is prevalence that one or more than one employee needs long vacation. Therefore, managers follow to find the best way for reassigning work to current jobholders which can be considered as a special form of GAP. There exist following assumptions which should be embedded in the model:(i)
In the proposed model, employees are put into two different categories, namely, skillful and semiskilled(ii)
Employees have limited overtime(iii)
The amount of time required for each work is determined(iv)
The cost of overtime for each member is specified(v)
Each work needs a specific skill(vi)
The works which can be carried out by each employee are determined(vii)
The amount of current overtime for each jobholder is specified(viii)
The works of members, who need a long holiday, is also determined.(ix)
Each worker has specified overtime, and more cost should be paid if needed to work more than it(x)
This plan is constant and unchangeable until the new holiday does not hold(xi)
The cost of workers is different, and it goes back to their skills.With respect to the abovementioned assumptions, managers try to find the model which has the best performance. Before introducing our model, we require to define some parameters and variables which are utilized in our model.


### 2.1. Parameters

(i)
I: the number of employers I=1,2,…,m
(ii)
J: the number of jobs J=1,2,…,n
(iii)
H
i: the maximum overtime of the i-th employee
(iv)
π
i: the overtime cost paid for the i-th employee in the common time
(v)
t
i: the amount of time required by the i-th employee each day
(vi)
P
i: the uncommon overtime cost of the i-th employee Pi=3πi
(vii)
A
i: the set of current tasks of the i-th employee
(viii)
O: the set of works of members who required a long holiday should be assigned to available jobholders.
(ix)
C
i
j: the amount of correlation among i-th and j-th works.
(x)
a
i
j: the amount of skill of the i-th employee to do j-th work.
(xi)
M: a big number.


### 2.2. Variables

(i)
x
i
j is a Boolean variable which can be defined as follows:
(1)
x
i
j
=
1
,
if
i
−
th employee carries out
j
−
th task,
0
,
O.W.
(ii)
w
i: the amount of overtime of the i-th employee:
(iii)
δ
i: a Boolean variable.
(iv)
f
i
=
min
w
i
,
H
i.


### 2.3. Objective Functions of Suggested Model

In the proposed model, we endeavor to optimize three objectives:(i)
The first of all is minimizing employee overtime. It is because that many works, which can be reassigned to current employees, should be done in their overtime. Therefore, the first objective is as follows:(2)minZ1=∑i∈Ifiπi+δiwi−HiPi,wherefi=minwi,Hi. Because this objective function has a nonlinear structure, we can change it to linear form by defining the following constraints:(3)fi≤wi,∀i∈I,(4)fi≤Hi,∀i∈I,(5)wi≤fi+δiM,∀i∈I,(6)Hi≤fi+1−δiM,∀i∈I.Suppose ifwi≤Hi, then one must have δi=0. Constraints fi≤wi and wi≤fi+δiM guarantee that fi=wi. Similarly, When Hi≤wi, we can guarantee that fi=Hi, with respect to fi≤Hi and Hi≤fi+1−δiM constraints.δiwi−HiPi is another nonlinear structure. This expression can be linearized by defining the following constraints:(7)μi≤MδiPi,∀i∈I,μi≤1−δiM+wi−HiPi,∀i∈I,−1−δiM+wi−Hi≤μi∀i∈I.(ii)
The second objective of managers is to maximize the correlation between works of employees. This objective can be formulated as follows:(8)maxZ2=∑i∈I∑j∈Ai∑j′∈OCjj′xij.(iii)
Finally, in the third objective, managers try to increase the skill level of employees, and its objective function is as follows:(9)maxZ3=∑i∈I∑j∈Jxijaij.


### 2.4. Constraints of Suggested Model

(i)
Each current employee should carry out at least one task which is as follows:
(10)
∑
i
∈
I
x
i
j
′
≥
1
,
∀
j
′
∈
O
.
(ii)
Each jobholder has official hours in which he/she can accomplish his/her work. We can formulate this constraint as follows:
(11)
∑
j
∈
J
T
i
j
+
∑
j
′
∈
O
T
i
j
′
x
i
j
=
t
i
+
w
i
,
∀
i
∈
I
.This constraint actually expresses that the total time each worker requires to perform his/her works and also new task after reassignment should be equal tot+w.With respect to the abovementioned information, the proposed model is as follows:(12)minZ1=∑i∈Ifiπi+μi,(13)maxZ2=∑i∈I∑j∈Ai∑j′∈OCjj′xij(14)maxZ3=∑i∈I∑j∈JXijaij,(15)s.t.∑i∈Ixij′≥1,∀j′∈O,(16)∑j∈JTij+∑j′∈OTij′xij=ti+wi,∀i∈I,(17)fi≤wi,∀i∈I,(18)fi≤Hi,∀i∈I,(19)wi≤fi+δiM,∀i∈I,(20)Hi≤fi+1−δiM,∀i∈I,(21)μi≤MδiPi,∀i∈I,(22)μi≤1−δiM+wi−HiPi,∀i∈I,(23)−1−δiM+wi−Hi≤μi∀i∈I,(24)xij∈0,1,∀i∈I,j∈J,(25)μi≥0,∀i∈I,(26)wi,≥0∀i∈I,(27)δi∈0,1.Our proposed model is a combination of some previously proposed GAPs which are discussed in the Section2 (see [5, 6, 9–12]). In this model, objective function (12) and constraint (16) are now proposed. Our model is a multiobjective optimization problem (it has three objective functions), while the other proposed models are single-objective optimization problems.Example 1.
Consider a company has 4 employees and 10 works. In this company, due to some reasons, the 4th member needs to take a long holiday. Managers try to find the best approach to assign his work to available workers. In order to use the proposed model to solve this problem, we need some information which is given in Tables1–7.Table 1
Maximum overtime.
i
=
1
i
=
2
i
=
3
i
=
4
H
i
2
3
4
4Table 2
Current employees’ tasks.
i
=
1
i
=
2
i
=
3
i
=
4
A
i
2
1,4
5
3,6Table 3
Work hours of employees.
i
=
1
i
=
2
i
=
3
i
=
4
t
i
8
7
5
4Table 4
Common and uncommon overtime costs.
i
=
1
i
=
2
i
=
3
i
=
4
π
i
15000
50000
50000
35000
p
i
215000
150000
150000
105000Table 5
Required time to carry out tasks by employees.
j
=
1
j
=
2
j
=
3
j
=
4
j
=
5
j
=
6
i
=
1
8
8
7
5
6
2
i
=
2
5
4
5
6
5
3
i
=
3
6
7
4
5
8
4
i
=
4
8
2
3
5
5
7Table 6
Skill level.
j
=
1
j
=
2
j
=
3
j
=
4
j
=
5
j
=
6
i
=
1
0.9
0.8
0.5
0.7
0.1
0.6
i
=
2
0.7
0.6
0.5
0.5
0.3
0.7
i
=
3
0.8
0.7
0.6
0.9
0.9
0.9
i
=
4
0.9
0.8
0.7
0.8
0.8
0.3Table 7
Correlation among tasks.
j
=
3
j
=
6
i
=
1
0.8
0.9
i
=
2
0.4
0.7
i
=
3
1
0.5
i
=
4
0.9
0.3
i
=
5
0.9
0.5
i
=
6
0.8
1This problem was solved by using CPLEX package in C++ in different states. First of all, we solved it when only the first objective was considered. The CPLEX result in this state was 760000, and the result showed that the first employee should have 2 hours of overtime, whereas the second and third jobholders should have 3 hours of overtime. The second state was when the second objective function was considered and the optimal solution was 2.9, and with respect to the third objective function, the optimal solution was 1.4. In the final state, we considered three objective functions simultaneously, and based on the importance of each objective, we put the coefficient of 0.5, 0.3, and 0.2 to the first, second, and third objective function, respectively (based on their importance for decision makers). The result of CPLEX showed that the optimal solution for the first and second objective function was stable, whereas the optimal solution of the third objective function increased to 1.1.


## 2.1. Parameters

(i)
I: the number of employers I=1,2,…,m
(ii)
J: the number of jobs J=1,2,…,n
(iii)
H
i: the maximum overtime of the i-th employee
(iv)
π
i: the overtime cost paid for the i-th employee in the common time
(v)
t
i: the amount of time required by the i-th employee each day
(vi)
P
i: the uncommon overtime cost of the i-th employee Pi=3πi
(vii)
A
i: the set of current tasks of the i-th employee
(viii)
O: the set of works of members who required a long holiday should be assigned to available jobholders.
(ix)
C
i
j: the amount of correlation among i-th and j-th works.
(x)
a
i
j: the amount of skill of the i-th employee to do j-th work.
(xi)
M: a big number.


## 2.2. Variables

(i)
x
i
j is a Boolean variable which can be defined as follows:
(1)
x
i
j
=
1
,
if
i
−
th employee carries out
j
−
th task,
0
,
O.W.
(ii)
w
i: the amount of overtime of the i-th employee:
(iii)
δ
i: a Boolean variable.
(iv)
f
i
=
min
w
i
,
H
i.


## 2.3. Objective Functions of Suggested Model

In the proposed model, we endeavor to optimize three objectives:(i)
The first of all is minimizing employee overtime. It is because that many works, which can be reassigned to current employees, should be done in their overtime. Therefore, the first objective is as follows:(2)minZ1=∑i∈Ifiπi+δiwi−HiPi,wherefi=minwi,Hi. Because this objective function has a nonlinear structure, we can change it to linear form by defining the following constraints:(3)fi≤wi,∀i∈I,(4)fi≤Hi,∀i∈I,(5)wi≤fi+δiM,∀i∈I,(6)Hi≤fi+1−δiM,∀i∈I.Suppose ifwi≤Hi, then one must have δi=0. Constraints fi≤wi and wi≤fi+δiM guarantee that fi=wi. Similarly, When Hi≤wi, we can guarantee that fi=Hi, with respect to fi≤Hi and Hi≤fi+1−δiM constraints.δiwi−HiPi is another nonlinear structure. This expression can be linearized by defining the following constraints:(7)μi≤MδiPi,∀i∈I,μi≤1−δiM+wi−HiPi,∀i∈I,−1−δiM+wi−Hi≤μi∀i∈I.(ii)
The second objective of managers is to maximize the correlation between works of employees. This objective can be formulated as follows:(8)maxZ2=∑i∈I∑j∈Ai∑j′∈OCjj′xij.(iii)
Finally, in the third objective, managers try to increase the skill level of employees, and its objective function is as follows:(9)maxZ3=∑i∈I∑j∈Jxijaij.


## 2.4. Constraints of Suggested Model

(i)
Each current employee should carry out at least one task which is as follows:
(10)
∑
i
∈
I
x
i
j
′
≥
1
,
∀
j
′
∈
O
.
(ii)
Each jobholder has official hours in which he/she can accomplish his/her work. We can formulate this constraint as follows:
(11)
∑
j
∈
J
T
i
j
+
∑
j
′
∈
O
T
i
j
′
x
i
j
=
t
i
+
w
i
,
∀
i
∈
I
.This constraint actually expresses that the total time each worker requires to perform his/her works and also new task after reassignment should be equal tot+w.With respect to the abovementioned information, the proposed model is as follows:(12)minZ1=∑i∈Ifiπi+μi,(13)maxZ2=∑i∈I∑j∈Ai∑j′∈OCjj′xij(14)maxZ3=∑i∈I∑j∈JXijaij,(15)s.t.∑i∈Ixij′≥1,∀j′∈O,(16)∑j∈JTij+∑j′∈OTij′xij=ti+wi,∀i∈I,(17)fi≤wi,∀i∈I,(18)fi≤Hi,∀i∈I,(19)wi≤fi+δiM,∀i∈I,(20)Hi≤fi+1−δiM,∀i∈I,(21)μi≤MδiPi,∀i∈I,(22)μi≤1−δiM+wi−HiPi,∀i∈I,(23)−1−δiM+wi−Hi≤μi∀i∈I,(24)xij∈0,1,∀i∈I,j∈J,(25)μi≥0,∀i∈I,(26)wi,≥0∀i∈I,(27)δi∈0,1.Our proposed model is a combination of some previously proposed GAPs which are discussed in the Section2 (see [5, 6, 9–12]). In this model, objective function (12) and constraint (16) are now proposed. Our model is a multiobjective optimization problem (it has three objective functions), while the other proposed models are single-objective optimization problems.Example 1.
Consider a company has 4 employees and 10 works. In this company, due to some reasons, the 4th member needs to take a long holiday. Managers try to find the best approach to assign his work to available workers. In order to use the proposed model to solve this problem, we need some information which is given in Tables1–7.Table 1
Maximum overtime.
i
=
1
i
=
2
i
=
3
i
=
4
H
i
2
3
4
4Table 2
Current employees’ tasks.
i
=
1
i
=
2
i
=
3
i
=
4
A
i
2
1,4
5
3,6Table 3
Work hours of employees.
i
=
1
i
=
2
i
=
3
i
=
4
t
i
8
7
5
4Table 4
Common and uncommon overtime costs.
i
=
1
i
=
2
i
=
3
i
=
4
π
i
15000
50000
50000
35000
p
i
215000
150000
150000
105000Table 5
Required time to carry out tasks by employees.
j
=
1
j
=
2
j
=
3
j
=
4
j
=
5
j
=
6
i
=
1
8
8
7
5
6
2
i
=
2
5
4
5
6
5
3
i
=
3
6
7
4
5
8
4
i
=
4
8
2
3
5
5
7Table 6
Skill level.
j
=
1
j
=
2
j
=
3
j
=
4
j
=
5
j
=
6
i
=
1
0.9
0.8
0.5
0.7
0.1
0.6
i
=
2
0.7
0.6
0.5
0.5
0.3
0.7
i
=
3
0.8
0.7
0.6
0.9
0.9
0.9
i
=
4
0.9
0.8
0.7
0.8
0.8
0.3Table 7
Correlation among tasks.
j
=
3
j
=
6
i
=
1
0.8
0.9
i
=
2
0.4
0.7
i
=
3
1
0.5
i
=
4
0.9
0.3
i
=
5
0.9
0.5
i
=
6
0.8
1This problem was solved by using CPLEX package in C++ in different states. First of all, we solved it when only the first objective was considered. The CPLEX result in this state was 760000, and the result showed that the first employee should have 2 hours of overtime, whereas the second and third jobholders should have 3 hours of overtime. The second state was when the second objective function was considered and the optimal solution was 2.9, and with respect to the third objective function, the optimal solution was 1.4. In the final state, we considered three objective functions simultaneously, and based on the importance of each objective, we put the coefficient of 0.5, 0.3, and 0.2 to the first, second, and third objective function, respectively (based on their importance for decision makers). The result of CPLEX showed that the optimal solution for the first and second objective function was stable, whereas the optimal solution of the third objective function increased to 1.1.


## 3. Suggested Model for Employees to Comeback from Vacation

In Section2, a new model, which reassigns tasks to available workers, was presented. In Iraq, employees who have a long vacation should come back to their company. Therefore, managers should find the best approach to cover this matter. In this section, we want to incorporate this assumption in the suggested method. As a result, we need to define the following parameters:(i)
S: the set of employees who need a long vacation(ii)
Oi: the set of tasks the i-th jobholder is responsible for before going to vacationThere exist some notes which should be noticed when the employees want to come back to their work(iii)
Managers tend to assign tasks to employees, who worked before vacation, if their skill level is higher than current jobholders.(iv)
Managers try to reassign the remaining works with the best possible way.(v)
The skill level of each member is an increasing function. It means that the skill level depends on time which workers spend on the work.Another important matter, which should be considered, is the correlation among current tasks and works which are carried out after reassignment. For this purpose,Cjj′i parameter is defined as follows:(28)Cjj′i=Cj′,xij′=0,Cjj′+lt,xij′=1.Herej∈Ai∪Ai′, where Ai′ express the set of tasks which do not concern the i-th employee, but the i-th jobholder should do the tasks after reassignment. Furthermore, lt is an increasing function depends on time.Regarding to the prior information, the new model for reassignment of tasks for available workers after coming back jobholders, who were in vacation, is similar to (12) except the second objective function and constraint (6) which are as follows:(29)maxZ2=∑i∈I∑j∈Ai∑j′∈OCjj′ixij′∑j∈AiTij+∑j′∈O−O′Tij′xij=ti+wi,∀i∈I.We suggest the heuristic algorithm to reassign works to current employees in the Appendix.


## 4. Conclusions and Future Work

In this paper, a new model is proposed for reassigning tasks on the available employees of Iraq companies, when at least one of jobholders was absent. Likewise, the returning workers from long holidays assumption were incorporated. Finally, a heuristic algorithm for solving reassignment tasks on laborers was introduced. Some algorithms such as branch-and-bound algorithm and heuristic algorithms can be developed for solving multiobjective optimization problems.



---

*Source: 2673793-2020-04-08.xml*