# Piecewise Linear Model for Multiskilled Workforce Scheduling Problems considering Learning Effect and Project Quality

Authors: Shujin Qin; Shixin Liu; Hanbin Kuang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Workforce scheduling is an important and common task for projects with high labour intensities. It becomes particularly complex when employees have multiple skills and the employees’ productivity changes along with their learning of knowledge according to the tasks they are assigned to. Till now, in this context, only little work has considered the minimum quality limit of tasks and the quality learning effect. In this research, the workforce scheduling model is developed for assigning tasks to multiskilled workforce by considering learning of knowledge and requirements of project quality. By using piecewise linearization to learning curve, the mixed 0-1 nonlinear programming model (MNLP) is transformed into a mixed 0-1 linear programming model (MLP). After that, the MLP model is further improved by taking account of the upper bound of employees’ experiences accumulation, and the stable performance of mature employees. Computational experiments are provided using randomly generated instances based on the investigation of a software company. The results demonstrate that the proposed MLPs can precisely approach the original MNLP model but can be calculated in much less time.


---

## Body

## 1. Introduction

Workforce scheduling is one of the key tasks in modern project management. Since human resource costs keep rising, project managers have to pay more attention to workforce scheduling in projects. An optimal employee scheduling solution can align employee with anticipated demand, ensure project quality, and reduce production costs. Compared with traditional resource constrained project scheduling problems, multiskilled workforce scheduling has more complex features, that is, more options of skills, nonlinear learning effects, project quality requirements, and so forth. This research works on multiskilled workforce scheduling problems considering learning effect and project quality (MSWSP-LE&PQ), which constitute the significance and value of this paper.Multiskilled workforce scheduling problems (MSWSP) have been widely studied in the last few decades [1, 2]. Néron [3] developed the classical resource constrained project scheduling model to a basic multiskilled workforce scheduling model by assuming that each employee can perform more than one type of task. Brucker et al. [4] analysed the features and complexity of some main mathematical models, covering specific aspects in the field of workforce scheduling. According to Brucker et al., the workforce scheduling model is NP-hard, even for a two-task case. Then, metaheuristics were designed to tackle these complex problems. Valls et al. [5] presented a biobjective model and a hybrid genetic algorithm to solve the MSWSP in service centres. Shahnazari-Shahrezaei et al. [6] handled the MSWSP by particle swarm optimization and elite tabu search. Chen and Zhang [7] proposed an ant colony optimization algorithm to deal with the MSWSP in software industry. However, few of these aforementioned methods considered the learning effects of workforce.The phenomenon of learning effect arises in work activities where the experiences accumulation improves skill performance of individual employee. In recent years, in workforce scheduling model, the learning effect on productivity is described in two perspectives: discrete and continuous.In the discrete perspective, multiple levels are used to differentiate the performance of employees in the same activity. Employees with a higher skill level, due to more experiences, can perform certain tasks better or faster than employees with a lower skill level. Models considering multiple levels are mainly described as integer and linear. Eitzen et al. [8] introduced a set covering approach to handle the multiskilled rostering problem with multiple skill levels. Cezik and L’Ecuyer [9] proposed an iterative cutting-plane algorithm to solve the multilevel MSWSP in call centre. These models follow a linear pattern and can be calculated with high efficiency. However, according to De Bruecker et al. [1], employees’ skill levels which appeared in the literatures are mainly defined based on task requirements. The generations of skill levels are classified according to the scope of the overall employees’ productivity, and individual employee’s productivity is estimated based on these skill levels. However, the classified skill levels may not perfectly reflect the individual employee’s learning effect.In the continuous perspective, learning curves are incorporated into the workforce scheduling model. Wright [10] initially put forward a log-linear model to study the learning effect in aircraft production. Since then, various learning curves have been introduced and applied in different areas, such as Plateau model, Stanford B model, S-curve model, Jaber-Glock learning curve model, 2-parameter exponential model, 3-parameter exponential model, and 3-parameter hyperbolic model [11–13]. Grosse et al. [13] systematically compared performance of existing well-known learning curves using a large set of empirical data and showed how to select appropriate learning curves based on task characteristics. According to their analysis, the S-curve, the 3-parameter hyperbolic, and the 3-parameter exponential models worked well on average. C. Otto and A. Otto [14] proposed a precedence graph approach based on learning from multiple sources of information available to generate new feasible assembly line balances in mass production of complex product. Glock et al. [15] modified the 3-parameter exponential function to describe the production processes and adopted a S-curve as the demand function in workforce scheduling problem. Both of the functions were validated using available empirical data. Zamiska et al. [16] investigated worker learning and forgetting phenomenon in dual resource constrained systems. The phenomenon was modelled considering a task-type factor in dual resource constrained systems to demonstrate how the task-type affects the performance of training. Though the models mentioned above can obviously simulate the learning process more precisely than the discrete ones by importing the learning curves, the nonlinearity caused by modelling learning curves makes the models difficult to solve, and consequently, the production in those model is mainly monoskilled. However, in complex production, when multiple workers with different skills are involved in tasks, the workforce scheduling becomes even complicated.Employees’ work experiences not only promote productivity, but also improve project quality. Project quality management, mentioned in the literatures, was achieved mainly through selecting proper resources, activity scheduling, and work process monitoring [17, 18]. Glock and Jaber [19], Icmeli-Tukel and Rom [20], and Tiwari et al. [21] investigated project quality and cost trade-off scheduling problem with rework factor. Pinker and Shumsky [22] took both efficiency and quality learning processes into account and presented a service process model. Heimerl and Kolisch [23] combined the multiskill and the learning curves together in IT-projects and presented a mixed nonlinear programming model for minimizing the scheduling costs. They solved the nonlinear model by a primal-dual interior filter line search algorithm. Since the solutions obtained by their algorithm can hardly be proved as global optimal, they calculated each instance for 50 times using random starting points to partially overcome local optimality. After that, the effect of learning curves on the individual production quality was not considered in their study. To the best of our knowledge, there are limited literatures which simultaneously consider the productivity promoting and the quality improving caused by the learning effect.In this research, a nonlinear model for the MSWSP-LE&PQ is put forward through investigating the effect of skill experiences accumulation on productivity promoting and quality improving. In consideration of the nonlinearity of learning functions, a piecewise linearization approach is proposed to construct the multiple levels for individual employee’s each skill. Then, the model is transformed into a mixed integer linear one, which can be handled by linear programming solver. In accordance with actual situations, two kinds of improvements are incorporated into the model to further enhance solving performance. Through designing and testing the orthogonal experiments based on a lot of instances, results of the nonlinear model and the linearized models are compared and analysed. The improved piecewise linear model is demonstrated to be significantly better than the others. Coupled with the orthogonal experimental results, the impacts of various parameters on model complexity are discussed.The rest of this paper is organized as follows. In Section2, a detailed description of problems is provided in this study and a nonlinear programming model is introduced. In Section 3, the mathematical piecewise linear model for multiskilled workforce scheduling is put forward, and the formal expressions of the improvements on the model are provided. In Section 4, an orthogonal experiment is designed, and the experimental results are thoroughly discussed. Section 5 provides the limitation and the future work for this research.


## 2. Model

### 2.1. Learning Effect

Since the learning curve was found by Wright [10] in 1936, it has been developed into various forms [13]. According to [13], the 3-parameter exponential function has the best performance in individual models compared with other learning curves. Heimerl and Kolisch [23] employed an adaptation of the 3-parameter exponential learning function [24] due to its ability to depict steady-state unit production time and its mathematical tractability. To simplify the modelization, in this research, employees are considered as individual and the skills of employees are assumed as mutually independent. Based on these literatures and assumptions, the following learning curve model is presented in this study.Given an initial experiencezws0 of employee w with skill s at the start of period 0, the experience zwst of employee w with skill s at the end of period t can be calculated by (1)zwst=zws0+∑τ=1txwsτ,where xwsτ is the workload allocated to employee w with skill s in the τth period. With the accumulation of experiences, the unit production time will decrease progressively. As shown in Figure 1, a learning curve τwszws describes the unit production time, that is, the amount of time that employee w requires to complete an additional workload unit after having completed zws workload units using skill s, which can be expressed as(2)τwszws=τwsub-τwslbe-λwszws+τwslb,where τwslb≥0 represents the steady-state unit production time, τwsub≥0 is the first-unit production time, and λws≥0 is the learning rate. According to (2), the amount of time ωwst that employee w requires to complete extra xwst workload units with skill s in period t with experience zwst-1 can be calculated by the following formula:(3)ωwst=∫zwst-1zwst-1+xwstτwsdzws.Figure 1
Learning curve for unit production time.As an employee’s experience accumulates, the quality of the task that the employee completes improves. In Grosse and Glock [25], a description for failure rate is given at the end of their article. According to their research, the amount of errors made by employees decreases over time. Based on our investigation, the quality learning effect has much similarity with the productivity learning effect. Hence, a modified 3-parameter exponential learning function is put forward to describe the quality learning processes. As shown in Figure 2, the quality qwst of the task for employee w who has zwst-1 experience of skill s can be defined by (4)qwst=qwsub-qwsub-qwslbe-αwszwst-1,where qwsub≥0 represents the steady-state production quality, qwslb≥0 is the first-unit production quality, and αws≥0 is the learning rate of learning curve for individual production quality.Figure 2
Learning curve for individual production quality.


### 2.2. Mathematical Model

The MSWSP-LE&PQ can be explained as follows: assume that a project schedule is given. LetT be the set of periods, and T denote the project duration. Time period t∈T is defined as the time span [t-1,t). Without loss of generality, in this paper, the period length of a week is assumed. The project requires the set S of skills. In the context of IT projects, skills indicate programming, architecture, security, hardware, and so forth. For period t∈T, the project requests qualified rst workload units of skill s∈S. The workload can be recorded as a qualified workload, only when they are completed by employees, whose skill level is equal or higher than the minimum quality limit of the task with skill s in period t, Qst. In this study, the minimum quality limits of the overall tasks are assumed to have the same value which is equal to the project quality standard.The set of employees is denoted asW. For performing tasks, each employee w∈W has Rwt time units and an experience zwst of skill s in period t. The cost per unit time of employee w denotes cw. In the tth period, the workload allocated to employee w with skill s is xwst, and correspondingly the production quality and the time requested are qwst and ωwst, respectively. The main objective for the problem is to minimize the total cost.Compared to the traditional MSWSP, the workforce allocation in this study needs to meet not only the skill requirements, but also project quality standards.We introduce the following additional decision variables:(5)uwst=1Theworkthatemployeewperformswithskillsinperiodtisqualified;0Otherwise.Then, the mathematical model of the MSWSP-LE&PQ can be formulated as the following mixed 0-1 nonlinear programming model (MNLP):(6)MNLP:min∑w∈W∑s∈S∑t∈Tcwωwst(7)s.t.∑w∈Wxwstμwst≥rsts∈S,t∈T(8)∑s∈Sωwst≤Rwtw∈W,t∈T(9)qwst-Qstμwst≥0w∈W,s∈S,t∈T(10)xwst≥0w∈W,s∈S,t∈T(11)μwst∈0,1w∈W,s∈S,t∈T,where the objective function (6) is to minimize the cost of workforce. Constraint (7) ensures the total qualified work with each skill in each period to meet the request for the project. Constraint (8) limits the total time that the employee performs in each period. Constraint (9) judges whether the quality of the task that employee performs reaches the standard. Constraints (10) and (11) describes the decision variables.


## 2.1. Learning Effect

Since the learning curve was found by Wright [10] in 1936, it has been developed into various forms [13]. According to [13], the 3-parameter exponential function has the best performance in individual models compared with other learning curves. Heimerl and Kolisch [23] employed an adaptation of the 3-parameter exponential learning function [24] due to its ability to depict steady-state unit production time and its mathematical tractability. To simplify the modelization, in this research, employees are considered as individual and the skills of employees are assumed as mutually independent. Based on these literatures and assumptions, the following learning curve model is presented in this study.Given an initial experiencezws0 of employee w with skill s at the start of period 0, the experience zwst of employee w with skill s at the end of period t can be calculated by (1)zwst=zws0+∑τ=1txwsτ,where xwsτ is the workload allocated to employee w with skill s in the τth period. With the accumulation of experiences, the unit production time will decrease progressively. As shown in Figure 1, a learning curve τwszws describes the unit production time, that is, the amount of time that employee w requires to complete an additional workload unit after having completed zws workload units using skill s, which can be expressed as(2)τwszws=τwsub-τwslbe-λwszws+τwslb,where τwslb≥0 represents the steady-state unit production time, τwsub≥0 is the first-unit production time, and λws≥0 is the learning rate. According to (2), the amount of time ωwst that employee w requires to complete extra xwst workload units with skill s in period t with experience zwst-1 can be calculated by the following formula:(3)ωwst=∫zwst-1zwst-1+xwstτwsdzws.Figure 1
Learning curve for unit production time.As an employee’s experience accumulates, the quality of the task that the employee completes improves. In Grosse and Glock [25], a description for failure rate is given at the end of their article. According to their research, the amount of errors made by employees decreases over time. Based on our investigation, the quality learning effect has much similarity with the productivity learning effect. Hence, a modified 3-parameter exponential learning function is put forward to describe the quality learning processes. As shown in Figure 2, the quality qwst of the task for employee w who has zwst-1 experience of skill s can be defined by (4)qwst=qwsub-qwsub-qwslbe-αwszwst-1,where qwsub≥0 represents the steady-state production quality, qwslb≥0 is the first-unit production quality, and αws≥0 is the learning rate of learning curve for individual production quality.Figure 2
Learning curve for individual production quality.


## 2.2. Mathematical Model

The MSWSP-LE&PQ can be explained as follows: assume that a project schedule is given. LetT be the set of periods, and T denote the project duration. Time period t∈T is defined as the time span [t-1,t). Without loss of generality, in this paper, the period length of a week is assumed. The project requires the set S of skills. In the context of IT projects, skills indicate programming, architecture, security, hardware, and so forth. For period t∈T, the project requests qualified rst workload units of skill s∈S. The workload can be recorded as a qualified workload, only when they are completed by employees, whose skill level is equal or higher than the minimum quality limit of the task with skill s in period t, Qst. In this study, the minimum quality limits of the overall tasks are assumed to have the same value which is equal to the project quality standard.The set of employees is denoted asW. For performing tasks, each employee w∈W has Rwt time units and an experience zwst of skill s in period t. The cost per unit time of employee w denotes cw. In the tth period, the workload allocated to employee w with skill s is xwst, and correspondingly the production quality and the time requested are qwst and ωwst, respectively. The main objective for the problem is to minimize the total cost.Compared to the traditional MSWSP, the workforce allocation in this study needs to meet not only the skill requirements, but also project quality standards.We introduce the following additional decision variables:(5)uwst=1Theworkthatemployeewperformswithskillsinperiodtisqualified;0Otherwise.Then, the mathematical model of the MSWSP-LE&PQ can be formulated as the following mixed 0-1 nonlinear programming model (MNLP):(6)MNLP:min∑w∈W∑s∈S∑t∈Tcwωwst(7)s.t.∑w∈Wxwstμwst≥rsts∈S,t∈T(8)∑s∈Sωwst≤Rwtw∈W,t∈T(9)qwst-Qstμwst≥0w∈W,s∈S,t∈T(10)xwst≥0w∈W,s∈S,t∈T(11)μwst∈0,1w∈W,s∈S,t∈T,where the objective function (6) is to minimize the cost of workforce. Constraint (7) ensures the total qualified work with each skill in each period to meet the request for the project. Constraint (8) limits the total time that the employee performs in each period. Constraint (9) judges whether the quality of the task that employee performs reaches the standard. Constraints (10) and (11) describes the decision variables.


## 3. Linear Reformulation

### 3.1.  Linearization of Learning Curve

As a nonlinear mixed integer programming model, the MNLP model is hard to solve. In this section, a piecewise linear processing method is adopted to linearize the MNLP model.We introduce the following notations:K: the set of experience levels, K=1,2,…,kmax,zwsk: the lower bound of experience of level k for employee w using skill s, and the range of the experience in experience level k is zwsk,zwsk+1,τwsk: the unit work time for employee w with skill s in experience level k.Note that the improvement of productivity in the learning curve is more significant in the initial stage and will be decreasing along with experiences accumulating. Then, the learning curve is divided into pieces along vertical axis according to the employee’s unit production time, and the corresponding pieces along horizontal axis represent experience intervals. The specific division method is explained in the following paragraph.While the experiences of employeew with skill s accumulate from 0 to +∞, the unit production time decreases by τwsub-τwslb. Along the vertical axis (unit production time), the τwsub-τwslb is divided into kmax-1 pieces, and each piece with length of (τwsub-τwslb)/(kmax-1), as shown in Figure 3.Figure 3
Division of the learning curve.After the division, the lower boundzwsk of experience level k for employee w with skill s can be calculated by(12)zwsk=-1λwsln⁡kmax-1kmax-k,w∈W,s∈S,k∈K∖1.The amount of timeωwst that employee w takes to complete extra xwst units with skill s in experience level k can be estimated by(13)ω~wst=12τwsk+τwsk+1·xwst,w∈W,s∈S,t∈T,k∈K.


### 3.2. Linearization for Quality Curve

The skill is qualified only when the experiences of the skill meet a certain standard. Constraint (9) can be replaced with the following two formulas:(14)zwstQ=1αwsln⁡1-qwslb-ln⁡1-Qst,w∈W,s∈S,t∈T,(15)zwst-1-zwstQμwst≥0,w∈W,s∈S,t∈T.


### 3.3. Piecewise Linear Model of MNLP

We introduce the following additional decision variables:ηwst: the qualified workload that employee w completes with skill s in period t:(16)ywstk=1Theexperienceofemployeewusingskillsatthestartofperiodtisinlevelk0Otherwise.The MNLP model can be approximately reformulated as the following mixed 0-1 linear programming model (MLP1) based on linearization of learning curves and quality constraints:(17)MLP1:min∑w∈W∑s∈S∑t∈Tcwωwst(18)s.t.∑w∈Wηwst≥rsts∈S,t∈T(19)∑s∈Sωwst≤Rwtw∈W,t∈T(20)zwst-1-zwstQμwst≥0w∈W,s∈S,t∈T(21)zwst=zws0+∑τ=1txwsτw∈W,s∈S,t∈T(22)zwskywstk≤zwst-1≤zwsk+1+M11-ywstkw∈W,s∈S,t∈T,k∈K∖kmax(23)∑k∈K∖kmaxywstk=1w∈W,s∈S,t∈T(24)ωwst≥12τwsk+τwsk+1·xwst-M21-ywstkw∈W,s∈S,t∈T,k∈K∖kmax(25)ηwst≤xwstw∈W,s∈S,t∈T(26)ηwst≤M3μwstw∈W,s∈S,t∈T(27)xwst≥0w∈W,s∈S,t∈T(28)ηwst≥0w∈W,s∈S,t∈T(29)μwst∈0,1w∈W,s∈S,t∈T(30)ywstk∈0,1w∈W,s∈S,t∈T,k∈K∖kmax,where M1,M2,M3 represent sufficient large positive numbers. Constraint (20) is to judge whether the workload that employee w completes using skill s in period t is qualified. Constraint (21) calculates the experience zwst of employee w using skill s at the end of period t. Constraint (22) confirms the experience level of employee w using skill s at the start of period t. Constraint (23) ensures that, in each period, each employee can only operate one skill in a unique experience level. Constraint (24) limits the working time that the employee w completes xwst workload units with skill s in period t. Constraints (25) and (26) describe the relationships of decision variables xwst, ηwst, and μwst. Constraints (27)–(30) identify the decision variables.


### 3.4.  Model Improvement

The model MLP1 can be further improved in the following two ways.Firstly, in a periodt∈T, the amount of workload that employee w can complete with skill s has an upper bound; namely,(31)xwst≤xwstmax,w∈W,s∈S,t∈T,where xwstmax represents the maximum workload employee w can complete using skill s, assuming that employee w devotes full time to the task which requires skill s in period t. Accordingly, the experience upper bound zwstmax of employee w in skill s at the start of period t can be calculated as(32)zwstmax=zws0+∑τt-1xwsτmax,w∈W,s∈S,t∈T,zwst≤zwstmax,w∈W,s∈S,t∈T.It is evident that only dividing the experience level in the interval[zws0,zwsTmax] can further improve the accuracy of the linearization of learning curve.Secondly, senior employees’ experience levels can be treated as constants. A subset of employeesW∗={w∣τwszws0-τwslb≤ε,s∈S} is defined, to represent the group of the senior employees, where the workload that a senior employee completes is assumed as qualified.Based on the above analysis, the MLP1 can be updated as follows:(33)MLP2:min∑w∈W∑s∈S∑t∈Tcwωwsts.t.∑w∈W∖W∗ηwst+∑w∈W∗xwst≥rsts∈S,t∈T∑s∈Sωwst≤Rwtw∈W,t∈Tzwst-1-zwstQμwst≥0w∈W∖W∗,s∈S,t∈Tzwst=zws0+∑τ=1txwsτw∈W∖W∗,s∈S,t∈Tzwskywstk≤zwst-1≤zwsk+1+M11-ywstk∀w∈W∖W∗,s∈S,t∈T,k∈K∖kmax∑k∈K∖kmaxywstk=1w∈W∖W∗,s∈S,t∈Tωwst≥12τwsk+τwsk+1·xwst-M21-ywstk∀w∈W∖W∗,s∈S,t∈T,k∈K∖kmaxωwst=τwszws0·xwstw∈W∗,s∈S,t∈Tηwst≤xwst∀w∈W∖W∗,s∈S,t∈Tηwst≤M3μwst∀w∈W∖W∗,s∈S,t∈Txwst≥0w∈W,s∈S,t∈Tηwst≥0∀w∈W∖W∗,s∈S,t∈Tμwst∈0,1∀w∈W∖W∗,s∈S,t∈Tywstk∈0,1∀w∈W∖W∗,s∈S,t∈T,k∈K∖kmax.The models MLP2 and MLP1 have the same objective function and similar constraints. Considering the senior employees, with the expense of a little lower model accuracy, a greater degree of reduction in the amount of variables and constraints can be obtained in the model.


## 3.1.  Linearization of Learning Curve

As a nonlinear mixed integer programming model, the MNLP model is hard to solve. In this section, a piecewise linear processing method is adopted to linearize the MNLP model.We introduce the following notations:K: the set of experience levels, K=1,2,…,kmax,zwsk: the lower bound of experience of level k for employee w using skill s, and the range of the experience in experience level k is zwsk,zwsk+1,τwsk: the unit work time for employee w with skill s in experience level k.Note that the improvement of productivity in the learning curve is more significant in the initial stage and will be decreasing along with experiences accumulating. Then, the learning curve is divided into pieces along vertical axis according to the employee’s unit production time, and the corresponding pieces along horizontal axis represent experience intervals. The specific division method is explained in the following paragraph.While the experiences of employeew with skill s accumulate from 0 to +∞, the unit production time decreases by τwsub-τwslb. Along the vertical axis (unit production time), the τwsub-τwslb is divided into kmax-1 pieces, and each piece with length of (τwsub-τwslb)/(kmax-1), as shown in Figure 3.Figure 3
Division of the learning curve.After the division, the lower boundzwsk of experience level k for employee w with skill s can be calculated by(12)zwsk=-1λwsln⁡kmax-1kmax-k,w∈W,s∈S,k∈K∖1.The amount of timeωwst that employee w takes to complete extra xwst units with skill s in experience level k can be estimated by(13)ω~wst=12τwsk+τwsk+1·xwst,w∈W,s∈S,t∈T,k∈K.


## 3.2. Linearization for Quality Curve

The skill is qualified only when the experiences of the skill meet a certain standard. Constraint (9) can be replaced with the following two formulas:(14)zwstQ=1αwsln⁡1-qwslb-ln⁡1-Qst,w∈W,s∈S,t∈T,(15)zwst-1-zwstQμwst≥0,w∈W,s∈S,t∈T.


## 3.3. Piecewise Linear Model of MNLP

We introduce the following additional decision variables:ηwst: the qualified workload that employee w completes with skill s in period t:(16)ywstk=1Theexperienceofemployeewusingskillsatthestartofperiodtisinlevelk0Otherwise.The MNLP model can be approximately reformulated as the following mixed 0-1 linear programming model (MLP1) based on linearization of learning curves and quality constraints:(17)MLP1:min∑w∈W∑s∈S∑t∈Tcwωwst(18)s.t.∑w∈Wηwst≥rsts∈S,t∈T(19)∑s∈Sωwst≤Rwtw∈W,t∈T(20)zwst-1-zwstQμwst≥0w∈W,s∈S,t∈T(21)zwst=zws0+∑τ=1txwsτw∈W,s∈S,t∈T(22)zwskywstk≤zwst-1≤zwsk+1+M11-ywstkw∈W,s∈S,t∈T,k∈K∖kmax(23)∑k∈K∖kmaxywstk=1w∈W,s∈S,t∈T(24)ωwst≥12τwsk+τwsk+1·xwst-M21-ywstkw∈W,s∈S,t∈T,k∈K∖kmax(25)ηwst≤xwstw∈W,s∈S,t∈T(26)ηwst≤M3μwstw∈W,s∈S,t∈T(27)xwst≥0w∈W,s∈S,t∈T(28)ηwst≥0w∈W,s∈S,t∈T(29)μwst∈0,1w∈W,s∈S,t∈T(30)ywstk∈0,1w∈W,s∈S,t∈T,k∈K∖kmax,where M1,M2,M3 represent sufficient large positive numbers. Constraint (20) is to judge whether the workload that employee w completes using skill s in period t is qualified. Constraint (21) calculates the experience zwst of employee w using skill s at the end of period t. Constraint (22) confirms the experience level of employee w using skill s at the start of period t. Constraint (23) ensures that, in each period, each employee can only operate one skill in a unique experience level. Constraint (24) limits the working time that the employee w completes xwst workload units with skill s in period t. Constraints (25) and (26) describe the relationships of decision variables xwst, ηwst, and μwst. Constraints (27)–(30) identify the decision variables.


## 3.4.  Model Improvement

The model MLP1 can be further improved in the following two ways.Firstly, in a periodt∈T, the amount of workload that employee w can complete with skill s has an upper bound; namely,(31)xwst≤xwstmax,w∈W,s∈S,t∈T,where xwstmax represents the maximum workload employee w can complete using skill s, assuming that employee w devotes full time to the task which requires skill s in period t. Accordingly, the experience upper bound zwstmax of employee w in skill s at the start of period t can be calculated as(32)zwstmax=zws0+∑τt-1xwsτmax,w∈W,s∈S,t∈T,zwst≤zwstmax,w∈W,s∈S,t∈T.It is evident that only dividing the experience level in the interval[zws0,zwsTmax] can further improve the accuracy of the linearization of learning curve.Secondly, senior employees’ experience levels can be treated as constants. A subset of employeesW∗={w∣τwszws0-τwslb≤ε,s∈S} is defined, to represent the group of the senior employees, where the workload that a senior employee completes is assumed as qualified.Based on the above analysis, the MLP1 can be updated as follows:(33)MLP2:min∑w∈W∑s∈S∑t∈Tcwωwsts.t.∑w∈W∖W∗ηwst+∑w∈W∗xwst≥rsts∈S,t∈T∑s∈Sωwst≤Rwtw∈W,t∈Tzwst-1-zwstQμwst≥0w∈W∖W∗,s∈S,t∈Tzwst=zws0+∑τ=1txwsτw∈W∖W∗,s∈S,t∈Tzwskywstk≤zwst-1≤zwsk+1+M11-ywstk∀w∈W∖W∗,s∈S,t∈T,k∈K∖kmax∑k∈K∖kmaxywstk=1w∈W∖W∗,s∈S,t∈Tωwst≥12τwsk+τwsk+1·xwst-M21-ywstk∀w∈W∖W∗,s∈S,t∈T,k∈K∖kmaxωwst=τwszws0·xwstw∈W∗,s∈S,t∈Tηwst≤xwst∀w∈W∖W∗,s∈S,t∈Tηwst≤M3μwst∀w∈W∖W∗,s∈S,t∈Txwst≥0w∈W,s∈S,t∈Tηwst≥0∀w∈W∖W∗,s∈S,t∈Tμwst∈0,1∀w∈W∖W∗,s∈S,t∈Tywstk∈0,1∀w∈W∖W∗,s∈S,t∈T,k∈K∖kmax.The models MLP2 and MLP1 have the same objective function and similar constraints. Considering the senior employees, with the expense of a little lower model accuracy, a greater degree of reduction in the amount of variables and constraints can be obtained in the model.


## 4. Orthogonal Experiment

To test the performance of the models, plenty of instances generated randomly are calculated using models of MNLP, MLP1, and MLP2. The MNLP model is solved using LINGO with a global solver, and the MLP1 and MLP2 models are solved using CPLEX 12.61. The experiments are conducted on a PC with the 2.50 GHz processors and 4 GB memory.


### 4.1. Instances Generation

In the experiments, 27 instance sets are generated and each set contains 10 random instances. The experiment contains two types of parameters: constant parameters (CP) and orthogonal parameters (OP). They are shown in Tables1 and 2, respectively.Table 1
Constant parameters.
Parameter
Parameter definition
Value
Q
s
t
Project quality standard
98.7%
τ
w
s
u
b
First-unit production time (h/LOC)
0.065
τ
w
s
l
b
Steady-state unit production time (h/LOC)
0.015
λ
w
s
Learning rate of learning curve (efficiency)
0.000064
q
w
s
u
b
Steady-state production quality
1
q
w
s
l
b
First-unit production quality
0.96
α
w
s
Learning rate of learning curve (quality)
0.00117
c
w, w∈W1
Wage for junior employee (Yuan/h)
20
c
w, w∈W2
Wage for middle employee (Yuan/h)
40
c
w, w∈W3
Wage for senior employee (Yuan/h)
60
R
w
t
Limit of work time per period (h)
40
z
w
s
0, w∈W1, s∈Sw
Initial experience interval for junior employee (LOC)
[700, 1000]
z
w
s
0, w∈W2, s∈Sw
Initial experience interval for middle employee (LOC)
[5000, 10000]
z
w
s
0, w∈W3, s∈Sw
Initial experience interval for senior employee (LOC)
[100000, 300000]
z
w
s
0, w∈W, s∉Sw
Initial experience interval for amateur skill (LOC)
100Table 2
Orthogonal parameters.
Parameter
Definition
Level 1
Level 2
Level 3
W
The number of employees
6
9
12
S
The number of skills
3
4
5
T
Project cycle (weeks)
8
12
16
p
t
Turnover rate of employee
10%
20%
30%
S
w
-
Average number of skills each employee masters
[1,  1.4]
[1.6,  2]
[2.2,  2.6]
ϕ
Task tightness
0.85
0.9
0.95
V
Coefficient of variation
[0, 0.3]
[0.4, 0.7]
[0.8, 1.1]The CPs contain project quality standard, parameters of individual employee’s production and quality learning curves, limit of work time per period, wages, and initial experience interval for different educated employees. The values of CPs stay the same in all instances. The OPs contain scale parameters, turnover rates, average number of skills each employee masters, task tightness, and variation coefficient. The values of OPs differ in different instance sets. The data are provided according to the investigation to a software company. In order to explain the project quality standard, the defect rate has to be firstly introduced. The defect rate can be measured by the number of coding errors per kilo-line of code (KLOC) in completed software, and the expected defect rate can be determined by customers. Hence, the project quality standard can be defined as one minus the expected defect rate. The project cycle has several periods and each period length is assumed as a week. Then, each employee is supposed to have 40 available hours in each period. Note that, three levels for each OP are designed, as shown in Table2. The definitions of the task tightness and the coefficient of variation are described in Appendices A and B, respectively.Based on the turnover rate of employee, the proportion of junior employee, middle employee, and senior employee can be generated, shown in Table3.Table 3
Employee structure (%).
Turnover
Junior
Middle
Senior
10
10
17.1
72.9
20
20
28.8
51.2
30
30
35.7
34.3An orthogonal experiment design with the seven OPs and three levels for each parameter is generated according to Table2, shown in Appendix C. There are 27 sets of values assigned to OPs in the orthogonal design, and for each set, 10 instances are generated randomly.


### 4.2. Computational Results

The original MNLP model is firstly calculated using Lingo. However, most of the instances failed to reach optimal solutions within two hours. Then, MLP1 and MLP2 models are handled using CPLEX 12.61. When the maximum experience levelkmax equals 5, all the instances can obtain optimal solution within 1 hour. Then, Constraint (31) is incorporated into MLP1 and MLP2, and the updated models MLP1+(31) and MLP2+(31) succeeded to reduce the maximum computing time to less than 40 seconds.Table4 shows the computational results obtained by solving the models. Column 2 shows the average gaps between objective values and lower bounds of MNLP model calculated by Lingo within the time limitation of 7200 seconds. Columns 3–7 show the average computation time taken by different models. Column 8 shows the average gaps between the optimal solution obtained by MLP2+(31) and the lower bound obtained by MNLP within the time limitation of 7200 seconds.Table 4
Results for models.
Instance set
Gap-I
CPU (s)
Gap-II
MNLP
MLP1
MLP2
MLP1+(31)
MLP2+(31)
1
0
404
0.53
0.52
0.53
0.38
0.08%
2
0
634
0.54
0.53
0.46
0.37
0.10%
3
0
479
0.52
0.44
0.44
0.41
0.06%
4
1.76%
7200
13.83
7.80
2.80
2.54
1.62%
5
1.55%
7200
10.47
14.35
3.19
3.40
1.47%
6
2.03%
7200
44.37
31.81
7.80
6.50
1.89%
7
1.57%
7200
5.57
6.80
1.78
1.72
1.48%
8
3.45%
7200
191.85
331.13
32.95
38.90
2.91%
9
4.32%
7200
1997.34
3446.71
35.75
34.95
4.19%
10
4.23%
7200
14.08
11.82
2.78
2.82
3.85%
11
4.27%
7200
6.04
7.30
2.25
2.31
3.80%
12
4.96%
7200
46.70
45.74
15.09
14.35
3.29%
13
0.04%
7200
39.69
13.28
1.71
1.28
0.05%
14
#
7200
23.82
14.83
2.11
1.76
0.30%
15
0
1352
21.59
9.42
0.86
0.59
0.00%
16
1.93%
7200
1.76
1.35
1.31
1.06
1.87%
17
1.64%
7200
1.93
1.48
1.69
1.39
1.05%
18
1.48%
7200
1.60
1.38
1.40
1.23
1.41%
19
2.66%
7200
132.45
115.70
6.52
5.55
1.75%
20
1.07%
7200
141.75
243.43
12.26
12.15
0.97%
21
1.65%
7200
135.26
163.46
6.53
5.62
0.85%
22
4.57%
7200
4.02
3.58
2.04
1.86
4.20%
23
6.06%
7200
7.89
7.27
2.24
2.27
2.74%
24
3.27%
7200
2.30
2.08
1.56
1.48
3.16%
25
#
7200
21.15
2.13
1.93
1.72
0.06%
26
0.07%
5293
22.82
11.79
2.26
1.98
0.81%
27
#
7200
30.96
12.61
4.52
4.07
0.16%
Average
2.19%
6168.96
108.18
166.99
5.73
5.65
1.63%According to Table4, the calculation results are summarized as follows. (1) The piecewise linearization method can effectively improve the calculation performance of MNLP model. When using MNLP model, only 4 small-sized sets of instances can obtain optimal solutions within 7200 seconds. Using piecewise linearization method, in contrast, all of the instances can get optimal results within an average of 2-3 minutes. (2) After the incorporation of Constraint (31), the calculation performance of the updated MLP1 and MLP2 models is further improved; that is, the average computation time is decreased to 5-6 seconds. (3) The piecewise linearization method may effectively improve the accuracy of MNLP model in a limited time. Through the comparison between Column 2 and Column 8, it can be observed that the solutions obtained by MLP models are mainly closer to the lower bound than that obtained by MNLP model.On the basis of data in Table4, MLP2+(31) model has the best performance for the instances in this study. Then, the effect of OPs on computation time are analyzed based on the MLP2+(31) model’s experimental results, shown in Table 5.Table 5
Average computation time on different parameter levels.
K
i
j
W
S
T
p
t
S
w
-
ϕ
V
K
1
j
9.91
4.88
1.16
1.40
2.10
4.13
2.36
K
2
j
2.98
2.41
4.41
4.38
7.17
6.55
7.55
K
3
j
4.08
9.67
11.39
11.18
7.69
6.27
7.05
R
j
6.93
7.26
10.23
9.79
5.59
2.42
5.19Table5 shows the average calculation time for the model MLP2+(31) in handling instances with combinations of different values of OPs. The value Kij represents the calculation time for the model MLP2+(31) to handle instances with parameter j at level i. If K1j, K2j, and K3j are equal, parameter j has no effect on computation time. Rj denotes the range of Kij, that is, Rj=maxiKij-miniKij. OPs can be ranked according to their effects on the computing time, Rj.As shown in Table5, the project cycle, the number of employees, and the number of skills will lead to the increasing of problem scale. Compared with the other two parameters, the project cycle has more participation in constraints, and this may be the reason why the project cycle is more influential. Except for the project cycle, the turnover rate parameter pt is the second major factor. Its increasing will require more junior employees involved into an instance. The less computation time will be taken if each employee masters fewer average number of skills, because the fewer skills that employee masters, the fewer options needed to be considered. The parameters of CV and the tightness are the factors with less influence to calculation time.


## 4.1. Instances Generation

In the experiments, 27 instance sets are generated and each set contains 10 random instances. The experiment contains two types of parameters: constant parameters (CP) and orthogonal parameters (OP). They are shown in Tables1 and 2, respectively.Table 1
Constant parameters.
Parameter
Parameter definition
Value
Q
s
t
Project quality standard
98.7%
τ
w
s
u
b
First-unit production time (h/LOC)
0.065
τ
w
s
l
b
Steady-state unit production time (h/LOC)
0.015
λ
w
s
Learning rate of learning curve (efficiency)
0.000064
q
w
s
u
b
Steady-state production quality
1
q
w
s
l
b
First-unit production quality
0.96
α
w
s
Learning rate of learning curve (quality)
0.00117
c
w, w∈W1
Wage for junior employee (Yuan/h)
20
c
w, w∈W2
Wage for middle employee (Yuan/h)
40
c
w, w∈W3
Wage for senior employee (Yuan/h)
60
R
w
t
Limit of work time per period (h)
40
z
w
s
0, w∈W1, s∈Sw
Initial experience interval for junior employee (LOC)
[700, 1000]
z
w
s
0, w∈W2, s∈Sw
Initial experience interval for middle employee (LOC)
[5000, 10000]
z
w
s
0, w∈W3, s∈Sw
Initial experience interval for senior employee (LOC)
[100000, 300000]
z
w
s
0, w∈W, s∉Sw
Initial experience interval for amateur skill (LOC)
100Table 2
Orthogonal parameters.
Parameter
Definition
Level 1
Level 2
Level 3
W
The number of employees
6
9
12
S
The number of skills
3
4
5
T
Project cycle (weeks)
8
12
16
p
t
Turnover rate of employee
10%
20%
30%
S
w
-
Average number of skills each employee masters
[1,  1.4]
[1.6,  2]
[2.2,  2.6]
ϕ
Task tightness
0.85
0.9
0.95
V
Coefficient of variation
[0, 0.3]
[0.4, 0.7]
[0.8, 1.1]The CPs contain project quality standard, parameters of individual employee’s production and quality learning curves, limit of work time per period, wages, and initial experience interval for different educated employees. The values of CPs stay the same in all instances. The OPs contain scale parameters, turnover rates, average number of skills each employee masters, task tightness, and variation coefficient. The values of OPs differ in different instance sets. The data are provided according to the investigation to a software company. In order to explain the project quality standard, the defect rate has to be firstly introduced. The defect rate can be measured by the number of coding errors per kilo-line of code (KLOC) in completed software, and the expected defect rate can be determined by customers. Hence, the project quality standard can be defined as one minus the expected defect rate. The project cycle has several periods and each period length is assumed as a week. Then, each employee is supposed to have 40 available hours in each period. Note that, three levels for each OP are designed, as shown in Table2. The definitions of the task tightness and the coefficient of variation are described in Appendices A and B, respectively.Based on the turnover rate of employee, the proportion of junior employee, middle employee, and senior employee can be generated, shown in Table3.Table 3
Employee structure (%).
Turnover
Junior
Middle
Senior
10
10
17.1
72.9
20
20
28.8
51.2
30
30
35.7
34.3An orthogonal experiment design with the seven OPs and three levels for each parameter is generated according to Table2, shown in Appendix C. There are 27 sets of values assigned to OPs in the orthogonal design, and for each set, 10 instances are generated randomly.


## 4.2. Computational Results

The original MNLP model is firstly calculated using Lingo. However, most of the instances failed to reach optimal solutions within two hours. Then, MLP1 and MLP2 models are handled using CPLEX 12.61. When the maximum experience levelkmax equals 5, all the instances can obtain optimal solution within 1 hour. Then, Constraint (31) is incorporated into MLP1 and MLP2, and the updated models MLP1+(31) and MLP2+(31) succeeded to reduce the maximum computing time to less than 40 seconds.Table4 shows the computational results obtained by solving the models. Column 2 shows the average gaps between objective values and lower bounds of MNLP model calculated by Lingo within the time limitation of 7200 seconds. Columns 3–7 show the average computation time taken by different models. Column 8 shows the average gaps between the optimal solution obtained by MLP2+(31) and the lower bound obtained by MNLP within the time limitation of 7200 seconds.Table 4
Results for models.
Instance set
Gap-I
CPU (s)
Gap-II
MNLP
MLP1
MLP2
MLP1+(31)
MLP2+(31)
1
0
404
0.53
0.52
0.53
0.38
0.08%
2
0
634
0.54
0.53
0.46
0.37
0.10%
3
0
479
0.52
0.44
0.44
0.41
0.06%
4
1.76%
7200
13.83
7.80
2.80
2.54
1.62%
5
1.55%
7200
10.47
14.35
3.19
3.40
1.47%
6
2.03%
7200
44.37
31.81
7.80
6.50
1.89%
7
1.57%
7200
5.57
6.80
1.78
1.72
1.48%
8
3.45%
7200
191.85
331.13
32.95
38.90
2.91%
9
4.32%
7200
1997.34
3446.71
35.75
34.95
4.19%
10
4.23%
7200
14.08
11.82
2.78
2.82
3.85%
11
4.27%
7200
6.04
7.30
2.25
2.31
3.80%
12
4.96%
7200
46.70
45.74
15.09
14.35
3.29%
13
0.04%
7200
39.69
13.28
1.71
1.28
0.05%
14
#
7200
23.82
14.83
2.11
1.76
0.30%
15
0
1352
21.59
9.42
0.86
0.59
0.00%
16
1.93%
7200
1.76
1.35
1.31
1.06
1.87%
17
1.64%
7200
1.93
1.48
1.69
1.39
1.05%
18
1.48%
7200
1.60
1.38
1.40
1.23
1.41%
19
2.66%
7200
132.45
115.70
6.52
5.55
1.75%
20
1.07%
7200
141.75
243.43
12.26
12.15
0.97%
21
1.65%
7200
135.26
163.46
6.53
5.62
0.85%
22
4.57%
7200
4.02
3.58
2.04
1.86
4.20%
23
6.06%
7200
7.89
7.27
2.24
2.27
2.74%
24
3.27%
7200
2.30
2.08
1.56
1.48
3.16%
25
#
7200
21.15
2.13
1.93
1.72
0.06%
26
0.07%
5293
22.82
11.79
2.26
1.98
0.81%
27
#
7200
30.96
12.61
4.52
4.07
0.16%
Average
2.19%
6168.96
108.18
166.99
5.73
5.65
1.63%According to Table4, the calculation results are summarized as follows. (1) The piecewise linearization method can effectively improve the calculation performance of MNLP model. When using MNLP model, only 4 small-sized sets of instances can obtain optimal solutions within 7200 seconds. Using piecewise linearization method, in contrast, all of the instances can get optimal results within an average of 2-3 minutes. (2) After the incorporation of Constraint (31), the calculation performance of the updated MLP1 and MLP2 models is further improved; that is, the average computation time is decreased to 5-6 seconds. (3) The piecewise linearization method may effectively improve the accuracy of MNLP model in a limited time. Through the comparison between Column 2 and Column 8, it can be observed that the solutions obtained by MLP models are mainly closer to the lower bound than that obtained by MNLP model.On the basis of data in Table4, MLP2+(31) model has the best performance for the instances in this study. Then, the effect of OPs on computation time are analyzed based on the MLP2+(31) model’s experimental results, shown in Table 5.Table 5
Average computation time on different parameter levels.
K
i
j
W
S
T
p
t
S
w
-
ϕ
V
K
1
j
9.91
4.88
1.16
1.40
2.10
4.13
2.36
K
2
j
2.98
2.41
4.41
4.38
7.17
6.55
7.55
K
3
j
4.08
9.67
11.39
11.18
7.69
6.27
7.05
R
j
6.93
7.26
10.23
9.79
5.59
2.42
5.19Table5 shows the average calculation time for the model MLP2+(31) in handling instances with combinations of different values of OPs. The value Kij represents the calculation time for the model MLP2+(31) to handle instances with parameter j at level i. If K1j, K2j, and K3j are equal, parameter j has no effect on computation time. Rj denotes the range of Kij, that is, Rj=maxiKij-miniKij. OPs can be ranked according to their effects on the computing time, Rj.As shown in Table5, the project cycle, the number of employees, and the number of skills will lead to the increasing of problem scale. Compared with the other two parameters, the project cycle has more participation in constraints, and this may be the reason why the project cycle is more influential. Except for the project cycle, the turnover rate parameter pt is the second major factor. Its increasing will require more junior employees involved into an instance. The less computation time will be taken if each employee masters fewer average number of skills, because the fewer skills that employee masters, the fewer options needed to be considered. The parameters of CV and the tightness are the factors with less influence to calculation time.


## 5. Conclusions

Taking learning effect and project quality into consideration, a modified MLP model is put forward to describe MSWSP-LE&PQ. Firstly, a detailed description of learning effects and a MNLP model is provided by considering the project quality and individual learning curves of employees. Secondly, linearization approaches are introduced to transform the MNLP model into MLP1. After that, characteristics of senior employees are taken into account to reduce the number of variables and constraints. Then, MLP2 is put forward. Finally, in order to further improve the efficiency of optimizing processes and cut the feasible solution space, the upper bounds of the workload and the experience of employees with each skill in each period are defined. And consequently, the MLP models are improved through incorporating Constraint (31). The proposed models are testified through orthogonal experiments.According to the experiment results, the original MNLP model has limitations to solve practical problems, because it is hard to demonstrate that the obtained solution is global optimal. Especially for large-scale cases, even a feasible solution can hardly be found out in an acceptable time. To overcome these limitations, the proposed linearization approaches can guarantee the solution global optimal. After that, the modified MLP models have more accurate solutions and notably less computation time than the original MNLP model in which learning effects are described by continuous nonlinear curves.It can be concluded from the orthogonal experiments that junior employee scheduling appears mainly in long-term projects, when the project cycle is more than 3 months. There are two reasons that lead to this phenomenon. On one hand, the initial production quality of junior employee is probably lower than the project quality standard. It will take lots of time for junior employees to promote their production quality to meet the standard. On the other hand, due to the training cost (the work which is not qualified), the average unit cost of qualified work which is performed by a junior employee is mainly higher than that of the middle and senior employees. Based on the modified MLP model, the average unit cost of qualified work can be calculated by∑tcwωwst/∑tηwst. Hence, the junior employees’ average unit cost of qualified work will fall below the average in long-term project.This study also has limitations. To simplify the modelization, forgetting effect and relearning processes are not taken into account. The parameters in learning curves may change referring to specific situations. The skills of employees in this research are considered as mutually independent. However, there may be correlations between similar skills, and similar skills may partially share some experiences.Further research could extend the model to long-term scheduling. And in this case, employees’ wages may vary according to their experiences. After that, the senior employees may have extra requirements in reality, such as a senior employee may prefer to work in favorite tasks in appropriate periods with suitable mates. In addition, the model may extend to handle multiproject workforce scheduling problem, in which projects may have heterogeneous quality requirements.



---

*Source: 3728934-2016-02-16.xml*