Industrial Management, School of Engineering, University of Seville, Camino de los Descubrimientos, s/n, 41092 Seville, Spain
Academic Editors: J. G. Barbosa and D. Oron
Copyright © 2014 Victor Fernandez-Viagas and Jose M. Framinan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
This paper addresses a decision problem related to simultaneously scheduling the tasks in a project and assigning the staff to these tasks, taking into account that a task can be performed only by employees with certain skills, and that the length of each task depends on the number of employees assigned. This type of problems usually appears in service companies, where both tasks scheduling and staff assignment are closely related. An integer programming model for the problem is proposed, together with some extensions to cope with different situations. Additionally, the advantages of the controllable processing times approach are compared with the fixed processing times. Due to the complexity of the integrated model, a simple GRASP algorithm is implemented in order to obtain good, approximate solutions in short computation times.
The lead time required to carry out a project—project makespan—has turned to be one of the main sources of competitive advantage for companies (see, e.g., [1, 2]). Since, in many cases, the processing times of the tasks that compose a project depend on the resources allocated to the task (see, e.g., ), it is clear that the project lead time depends both on the scheduling of the tasks and on the allocation of staff to these tasks. Regarding task scheduling, it encompasses the sequence to be followed by each task over time, and it is usually regarded as an important aspect of the industrial organization  and production . On the other hand, staff assignment is essential in a project  and it can be defined as the allocation of company workers to different tasks. Traditionally, staff assignment is included within the manpower planning as one of its steps. Thus, several authors [7–10] have considered the following structure: planning; scheduling; allocation. In staff assignment, worker’s satisfaction tends to be maximized whereas makespan and production costs are often minimized in task scheduling. To execute a task, it is essential that a particular employee is available at that time; otherwise the realization of such task should be postponed until the employee becomes available and, consequently, staff assignment directly influences task schedule. Due to the importance of the scheduling and the assignment in a project environment and since both are very related, it is critical to address both problems in an integrated manner. Furthermore, the majority of scheduling problems in the literature consider fixed processing times  and most of the rest assume that processing times depend linearly on the amount of resources assigned . As lead times strongly depend on the processing times of the task, and since the processing time of a task depends on the number of employees assigned to this task, in this paper we explicitly take into account this relationship.
In this paper, an integration of project scheduling and staff assignment (PSSA) problem with controllable processing times (CPT) is presented using renewable resources and nonpreemptive tasks. Minimization of the makespan has been chosen as the objective function since delays can lead to an increase in costs and even to the loss of customers. This problem can be placed within the project management process. According to Demeulemeester and Herroelen , the project life cycle is as follows.(i)Concept Phase. There is a need of a customer to perform a project. This need is transmitted to the company.(ii)Definition Phase. First, the goal of the project is defined. Next, the work content is defined and, finally, a project strategy is elaborated to achieve the goal.(iii)Planning Phase. The project is divided into tasks. Then, their processing times are estimated and both the resources requirements and the precedence relationships between tasks are identified.(iv)Scheduling Phase. Both task scheduling and the amount of resources in each period of time are defined in this phase(v)Control Phase. In this phase it is controlled that the project is implemented following the aspects defined in the planning and scheduling phases.(vi)Termination Phase. This phase corresponds to the delivery of the results of the project.
Note that between the scheduling phase (where the amount of resources is known) and the control phase there must be an assignment of resources to the tasks if the resources are not identical. For these cases, an additional phase is therefore needed. This phase—named “resources assignment phase”—must be placed between the scheduling phase and the control phase. Alternatively, integration between the scheduling and the resources assignment phases can be done. The latter is the adopted approach in this paper, which is organized as follows: a state of the art and a description of the problem are shown in Section 2. An extended explanation of the CPT is also presented, while the problem statement and a formulation of the integer linear programming model are shown in Section 3. Additionally this integer linear programming model is compared with a multimode formulation. In Section 4, we define a simple GRASP heuristic algorithm for the problem. Section 5 contains computational experiments based on a test bed. Besides, a comparison between the model with and without CPT is shown there. Lastly, conclusions are described in Section 6.
2. Literature Review
The model presented in this paper includes two decision problems: task scheduling and staff assignment. Task scheduling is traditionally denoted in the literature as project scheduling problem (PSP). Furthermore, if limitations regarding the number of resources per activity are assumed, it is named resource-constraint project scheduling problem (RCPSP). This problem has been extensively studied in the literature, and recent reviews can be found in Węglarz et al.  and Hartmann and Briskorn . Staff assignment is a type of assignment decision problem that has also been extensively addressed . Nevertheless, the integration between project scheduling and staff assignment has not been so comprehensively studied, and hence there is still no consensus about the name of this joint problem (see in Table 1 different names that have been used to denote the problem). In our work, we consider the name “project scheduling and staff assignment” as denomination for the problem.
Table 1: Names for the integrated problem.
Our problem is related to several contributions in the literature, which are summarized in Table 2. Bassett  presents a model of project scheduling and staff assignment considering time windows for the completion times of the tasks. Vairaktarakis  adds precedence relationships to the integrated problem. However, no time units are used in the linear programming model (the order of the tasks defines the schedule of the project). Time units are included in a similar problem by Bellenguez and Néron  and Bellenguez-Morineau and Néron  where some lower bounds are calculated in the former reference, while in the latter the authors implement a branch and bound algorithm. External and internal resources constraints are considered by Kolisch and Heimerl . Wu and Sun  present the integrated problem proposing a nonlinear model, which is solved by a genetic algorithm. Although learning effect (i.e., the longer an employee works on a task, the greater his/her efficiency is) is considered in the model, neither precedence relationships nor skill constraints are used in their model. Gutjahr et al.  consider portfolio selection and skills in the integrated problem with learning effect but with precedence relationship which are included by Gutjahr et al. . Precedence relationships are also included by Corominas et al.  in an integrated problem, similar to the problem of Wu and Sun , also with learning effect. Drezet and Billaut  propose a linear programming model for a project scheduling and staff assignment problem. However, they do not consider learning effects in the model and include move constraints (i.e., the number of assignment movements of the employees from one nonfinished task to another is bounded). Moreover, the number of employees assigned to each task at each period of time is set between a minimum and a maximum depending on the level of skills of the workers. However, the processing times of the tasks are assumed to be fixed and not depending on the number of employees assigned. Since no solutions can be found for medium-sized instances of the problem, a tabu search algorithm was implemented using a greedy algorithm as initial solution.
Table 2: Summary of related papers.
A common feature in all the aforementioned works is that none of them include variable processing times. Regarding CPT, Hachicha et al.  propose a staff assignment model considering multiskilled employees, preference of the employees for some tasks, and skill-based processing times (i.e., the processing times of the tasks depend on the skills of the employee). Nevertheless, they are preprocessed before solving the model, which means that the processing times do not change during the planning horizon. More specifically, processing times are first calculated depending on the skills of each employee and then introduced in the model as data. Heimerl and Kolisch  analyze a staff assignment problem without scheduling considering learning effect on the employees, so the processing times are now variables of the problem as they depend on the experience of the staff. In order to solve this problem, a nonlinear model is implemented. Hachicha et al.  and Heimerl and Kolisch  use CPT in their models, although none of them solve the integrated problem (only the staff assignment problem). Variable processing times in a scheduling problem can be found in Alfares and Bailey . They use a linear programming model to schedule the task of a project and to assign the number of employees to each task; that is, the variables of the problem are the starting times of each task, the processing times, and the number of employees per period. Regarding the processing times, they are chosen to minimize the costs, but they do not depend on any variable. Moreover, staff assignment for each employee is not considered there.
CPT in an integrated PSSA problem are considered in Drexl , Dodin and Elimam  with the objective of costs minimization. However, in their models, the processing times depend on the skills of the employee assigned (and consequently are introduced in the model as data), but not on the amount of resources allocated; that is, processing times are defined by a matrix of two dimensions where the rows are the processing times of the tasks and the columns the employees. In Valls et al. , each task has to be performed by a single employee and its processing time increases or decreases depending on the efficiency of the employee. Nonpreemptive tasks with release times and due dates are taken into account, as well as precedence relations with time lags. No programming model is implemented, but a hybrid genetic algorithm is developed to solve the cost minimization problem. This contribution is the one most related to our problem, since the authors implement an integrated PSSA with CPT. However, in our paper, a linear programming model is considered to minimize the makespan of the project where the processing times of the tasks depend piecewise linearly on the number of employees assigned instead of the efficiency level of the employee and multiple assignments to each task are also allowed as well, while in Valls et al.  each task must be implemented by a single employee. To the best of our knowledge, the proposed model has not been analyzed before.
3. Model Proposal for the Integrated PSSA Problem
3.1. Problem Statement
This paper presents a PSSA problem in which a company is responsible for the implementation of a project consisting of tasks (with task ) with (known) precedence relations between tasks (i.e., some tasks should be finished before carrying out others). The order of execution of each task has to be decided to minimize the corresponding objective function. Each task must be performed by some workers from total of employees (employee ) with certain skills in each period of the planning horizon .
It is assumed that each task has a release time , so it must always start after this time. Furthermore, once a task starts, it runs continuously until its end (nonpreemptive approach). One employee can be assigned to a task if the employee possesses the required skills for the task. We assume that there is an optimal number of employees, , to be assigned to each task, although overcoverage and undercoverage of employees are allowed by the model. Under- and overcoverage would lead to different values of the efficiency of the employees and, consequently, to different processing times of the tasks.
3.2. Controllable Processing Times (CPT)
In this paper, we assume that processing times depend on the resources (or employees, as we would use both terms as equivalent in this paper) assigned. Such type of processing times has been studied in the literature as a function of the resources allocated and of the experience of the workers (level of skills). The relationship between time and amount of resources has been mainly analysed under two different approaches, namely, linear and convex (see the review by ). In the linear approach (see, e.g., ), a linear relationship between the processing times of a task and the resources allocated to this task is assumed. Denoting as the processing time of task and as the number of resources allocated to this task, this relationship can be expressed as , with and constants. However, this approach is not well suited to many realistic situations, since according to Belbin , there must be an optimal number of employees to be assigned to task in order to achieve maximum workers’ efficiency (point ). Therefore, it is easy to see that the linear approach is not flexible to this concept, at least for values to each side of the efficiency level since the efficiency point of worker must always be in an extreme of the line (see, e.g., Figure 2(a), where the efficiency point is placed for resources).
In the convex approach it is assumed that there is an inverse relationship between processing times and employees (see, e.g., ), where and (normally denoted workload of the task ) are constants:
For , the number of resources and the processing times are inversely proportional (e.g., doubling the employees would cut the processing time by half and vice versa; see the red line of Figure 1). The convex relationship is closer to real life than the linear and it has been used for many actual government and industrial projects , distributed communication network, time-sharing computing system, and chemical plant or commercial construction projects . Nevertheless, its nonlinearity would preclude modeling the problem using linear programming. Thus, in this paper a piecewise linear relationship to represent the relationship between processing times and amount of resources assigned to the task is proposed. The relationship is shown in (2), being the slope of each section for a task in the piecewise linear relationship and the number of employees fulfilled of that task in each section, where section has a length (). This piecewise linear relationship can be adjusted to the convex relationship (with ) as shown in the blue line of Figure 1. This relationship is over the convex relationship representing a safer configuration of processing times and amount of resources:
Figure 1: Piecewise linear relationship and convex relationship with . Subscripts are removed for simplicity in the figure.
Figure 2: Relation between processing times and number of employees (shaded area).
The superscript for processing times, , and for the amount of resources, , denotes that they correspond to point .
According to Lanigan , the convex relationships between the processing time of a task and the number of employees assigned do not entirely match the reality, and there shall be a penalty due to assigning different numbers of employees. On the one hand, if , then a penalty for communication exists. In contrast (see, e.g., [41, 42]), if then there is a penalty for lack of specialization . Hence, each feasible point different than the optimum must be placed over the convex curve; otherwise many optima would exist and there would be no penalties for under- and overcoverage. The feasible area formed by these points is represented by the light red area in Figure 2(a) (this feasible area is also taken into account by [44, 45]). Moreover, it shall be considered that the processing time of a task decreases when the number of employees increases; otherwise it would make no sense to assign more employees to the tasks. Thus, the feasible area can be reduced by considering that the processing time of a task cannot increase when the number of employees increases (Figure 2(b)). In this way, the feasible relationships between both aspects must be in this area. Therefore, we propose using a piecewise linear relationship with a maximum and minimum possible number of workers on each task. Depending on the maximum and minimum possible number of workers, the slopes of the lines must be different to avoid that both lines are under the convex curve (i.e., in the infeasible region) in any point. The directions of the slope of the piecewise relationships are placed in the feasible region and shown in Figure 2(c). By doing so, linear programming can be used to model and solve the problem. Furthermore, the piecewise relationship is on the safe side with respect to the convex relation, since the piecewise relationship is always over the convex relation.
To define the slopes of the lines, we propose introducing the parameters and . The higher these parameters are, the bigger the penalties for under- and overassignment of employees with respect to the optimal value, and consequently the closer the problem to the PSSA with fixed processing times (FPT). In the most extreme case, both problems are the same. The piecewise linear relation left and right of the optimum can be written as follows (see Figure 2(d)):
Analogously, let us now consider as the undercoverage of task and as the overcoverage of task , :
3.3. Formulation of the Model
3.3.1. Proposed Integer Linear Programming Model
In the previous section, we have presented a mechanism for formulating a realistic relationship between the processing times of the task and the number of employees assigned. Furthermore, this relationship can be embedded into a piecewise linear function; therefore a linear programming model can be formulated for the PSSA. In this section, a formal description of this model is given.
Data earliest starting time (release time) of task .
Campbell GM, Diaby M (2002) Development and evaluation of an assignment heuristic for allocating cross-trained workers. Eur J Oper Res 138:9–20CrossRefMATHGoogle Scholar
Campbell GM (1999) Cross-utilization of workers whose capabilities differ. Manage Sci 45:722–732 Bassett M (2000) Assigning projects to optimize the utilization of employees’ time and expertise. Comput Chemical Eng 24:1013–1021Google Scholar
Miller JL, Franz LS (1996) A binary-rounding heuristic for multi-period variable-task-duration assignment problems. Comput Oper Res 23(8):819–828CrossRefMATHGoogle Scholar
Urahama K (1994) Analog circuit for solving assignment problems. Trans IEEE on CAS-I 41(5):426–429Google Scholar
Xu HB, Wang HJ, Li CG (2002) A hybrid algorithm for the assignment problem. In: Proceedings 2002 International Conference on Machine Learning and Cybernetics, 2:881–884Google Scholar
Bassett M (2000) Assigning projects to optimize the utilization of employees’ time and expertise. Comput Chemical Eng 24:1013–1021CrossRefGoogle Scholar
Hendriks MHA, Voeten B, Kroep L (1999) Human resource allocation in a multi-project research and development environment. Int J Project Manage 17:181–188CrossRefGoogle Scholar
Hanakawa N, Morisaki S, Matsumoto K (1998) A learning curve based simulation model for software development. In: Proceedings of the 1998 (20th) International Conference on Software Engineering, 350–359Google Scholar
Wright TP (1936) Factors affecting the cost of airplanes. J Aeronautical Sci 3:122–128Google Scholar
Yelle LE (1979) The learning curves: historical review and comprehensive survey. Decis Sci 10(2):302–328Google Scholar
Smith DB, Larsson JL (1989) The impact of learning on cost: the case of heart transplantation. Hospital Health Service Administration 34(1):85–97Google Scholar
CPLEX (2002) User’s Manual, ILOG CPLEX 7.5CEnoteincomplete ref. infoGoogle Scholar
Gen M, Cheng R (2000) Genetic algorithms and engineering optimization. Wiley, New YorkGoogle Scholar
Goldberg DE (1989) Genetic algorithm in search optimization and machine learning. Addison Wesley, New YorkGoogle Scholar
Man KF, Tang KS, Kwong S (1999) Genetic algorithms. Springer, New YorkGoogle Scholar
Winston PH (1992) Artificial intelligence. Addison-Wesley, New YorkGoogle Scholar