Preemptive Software Project Scheduling Considering Personality Traits

Abstract

The success of software projects is inseparable from the effective scheduling of multi-skilled human resources. In software development, employees’ personality traits often affect the performance of their work. Additionally, software developers are usually multi-tasking, which makes software development tasks preemptive. In view of this, we investigate the preemptive software project scheduling problem considering personality traits (PSPSP-PT), which aims at assigning employees with different skills and personality traits to suitable tasks and determining the start time of each task with the consideration of preemption, multi-skill, and precedence relations such that the total cost of the project is minimized. We formulate a mixed-integer linear programming model for the PSPSP-PT and design a dual priority rules-based heuristic (DPRH). Based on a benchmark dataset that is generated using a full factorial design, computational experiments are conducted to analyze the performance of our DPRH. Comparative analysis with existing algorithms reveals that our DPRH is competitive in terms of efficiency and effectiveness.

1. Introduction

As a strategic high-tech industry, the software industry is an important support for social informatization. In 2023, the global software market size reached $74.2 billion and is expected to reach $378.6 billion by 2033 [1]. However, due to the increasing complexity of software development business logic, the increasing cross-border and cross-regional collaboration of project teams, and the complexity and volatility of user needs, software development projects still face the challenge of low success rates [2], and a large number of software development projects are difficult to deliver on time and within budget. According to the research results of the Standish Group on 23,000 software development projects, 46% of the projects exceeded the budget or schedule, and only 26% of the projects could be delivered on time and within budget [3]. An important reason for the failure of many software development projects is the lack of effective scheduling [4].

Software project scheduling aims to develop a baseline schedule that specifies when each employee should perform specific tasks while satisfying constraints such as precedence relationships and human resource skill requirements. In other words, software project scheduling lies in determining who undertakes what tasks throughout the lifespan of a software project. This schedule seeks to achieve optimal matching between employees with certain skills and tasks requiring those skills, thereby minimizing performance measures such as project makespan and cost. This is a crucial matter in the practice of software engineering, as the total budget and human resources involved need to be managed in an optimal way to ensure a successful project outcome.

The software project scheduling problem (SPSP) has been extensively studied. As an early representative study, Alba and Chicano (2007) [5] applied the genetic algorithm to optimize task scheduling and staff employee assignment, with subsequent research building upon this foundation [6,7,8]. Li and Womer (2009) proposed a hybrid benders decomposition algorithm that combines integer linear programming and constraint programming to model and solve the SPSP [9].

Software development is a typical intelligence-intensive process. Whether multi-skilled employees can be effectively assigned is an important factor affecting the scheduling effect of software projects. Based on the model proposed by Alba and Chicano (2007) [5], Wang and Zheng (2018) [10], Rodríguez et al. (2011) [11], and Akbar et al. (2024) [12] considered varying skill levels among employees, proposing multi-objective fruit fly optimization algorithms, multi-objective simulation optimization algorithms, and greedy and parallel scheduling algorithms, respectively. García and Gómez (2014) further set differentiated salaries for different employees according to their skill levels so that “experts” and “novices” enjoy salary levels that match their skill levels [13]. Li et al. (2023) explored the software project scheduling problem with variable activity durations in which the task duration depends on the assigned employees and their skill levels [14]. Janiak and Rudek (2009) [15], Kuo and Yang (2011) [16], Wang and Wang (2013) [17], Niu et al. (2014) [18], Lin (2014) [19], and Korytkowski and Malachowski (2019) [20] considered the learning effects during software project scheduling, i.e., the phenomenon that employees’ familiarity with skills gradually increases with the length of use. Additionally, due to the complexity and volatility of user needs in software development projects, employees may need to acquire new skills not previously mastered. Shen et al. (2024) developed a dynamic model incorporating mechanisms for new skill acquisition and designed a predictive–reactive scheduling method based on a multi-population coevolutionary algorithm to solve this problem [4]. Guo et al. (2019) comprehensively considered the learning and forgetting effects, dynamically evaluated the skill level of employees, and used a multi-objective fireworks algorithm to solve the problem to minimize project cost and duration [21]. Shen et al. (2018) introduced a novel perspective on learning effects, suggesting that learning outcomes are influenced by employees’ motivation and learning ability. They also included employee satisfaction with the personnel assignment as one of the objectives and proposed a multi-objective, two-archive memetic algorithm based on a Q-learning algorithm for solving this problem [22]. Nigar et al. (2022) accounted for the improvement in employees’ learning abilities over time along with the evolution of their experience and reassigned tasks in a dynamic environment. To solve this problem, they employed various heuristic algorithms [23].

The above studies focus mostly on individual skills and do not take into account the synergistic utility between team members. Kosztyán et al. (2022) examined not only individual skill efficiency but also pairwise synergy effects among employees, analyzing the impact of synergy on project cost [24]. Building on this, Kosztyán et al. (2024) further studied the effect of autonomous team role selection and model and analyzed team roles and their synergy through a matrix-based project planning method [25]. Zhang et al. (2023) argued that interpersonal relationships within a team can affect the performance of software development projects. Consequently, they investigated the software project scheduling problem considering team dynamics, introducing communication cost as a factor and quantifying its relationship with changes in interpersonal interactions and improvements in skill proficiency. To solve this problem, they proposed an improved bi-population discrete evolutionary algorithm [26]. Chend et al. (2019) targeted the dynamic complexity of team collaboration and considered the employees’ leave and return during the software development process as well as the specific constraints on rework tasks caused by different programming habits among employees, thereby enhancing the robustness of the scheduling scheme [27].

Although scholars have conducted extensive research on software project scheduling from many perspectives of human resources, few studies have incorporated employee personality factors into the scheduling process of software projects, which undoubtedly affects the effectiveness of scheduling software projects that are significantly intelligence intensive. Personality reflects people’s behavior patterns, thinking patterns, and emotional reactions, which affect employees’ work performance [28]. Dhani and Sharma (2018) showed that personality traits have a significant impact on the work performance of IT employees and can serve as predictors of work performance [29]. Furthermore, the risks associated with employee performance are a critical component of project risk. Enhancing employee performance is an effective strategy for reducing project risks and improving project success rates [30,31]. Jones et al. (2023) noted that many software development teams have abandoned the use of planning poker for workload estimation during the development of minimum viable products [32]. This is due to the method’s failure to account for the heterogeneity of team members, making it difficult to achieve the expected effect [33]. It is worth noting that some scholars have considered personality traits in areas other than project scheduling. For example, Hamid et al. (2019) took the decision-making styles of surgical team members (as personality traits) into consideration to improve the efficiency of cooperation among surgical team members [34].

Therefore, to close the gap that employee personality has not been considered in the field of software project scheduling, we consider the matching of employee personality traits with different types of tasks during the software project scheduling process, which will help improve employees’ work performance and thereby increase the success rate of software projects. At the same time, our study provides a valuable reference for software project managers to formulate scientific and effective employee assignment plans, optimize human resource allocation and team division, and promote collaboration based on factors such as employee personality traits and skill levels.

Additionally, due to external disruptions and management demands, tasks in software development may experience temporary interruptions, such as developers switching between different tasks. This implies that tasks in software project scheduling are preemptive. Existing studies have shown that considering preemption during scheduling can lead to better project makespan [35] and more balanced resource utilization [36]. However, in software project scheduling, few studies consider preemption.

Therefore, given the lack of consideration of task preemption and employee personality traits in software project scheduling, we propose and study the preemptive software project scheduling problem considering personality traits (PSPSP-PT). Our main contributions are as follows: (1) We formulate a mixed-integer linear programming model for the PSPSP-PT, which incorporates multiple factors, such as task preemption, employee personality traits, and uncertain workload, in the project scheduling process; (2) to efficiently solve the PSPSP-PT, we design a dual priority rules-based heuristic algorithm (DPRA) that can achieve effective scheduling through task selection and employee assignment; (3) we conduct computational experiments and compare the proposed algorithm with an estimation of distribution algorithm (EDA). The comparison results demonstrate the effectiveness and efficiency of our algorithm.

Our study provides software project managers with a flexible and effective scheduling tool that optimizes the allocation of human resources by comprehensively considering employee skills, personality traits, and task preemption. This will help improve project execution efficiency and reduce overall costs. The rest of this paper is structured as follows. We describe the PSPSP-PT in Section 2. In Section 3, we formulate a mixed-integer programming for the PSPSP-PT. In Section 4, we design a dual priority rules-based heuristic (DPRA). Section 5 evaluates the performance of the DPRA through computational experiments and compares it with the baseline algorithm. Finally, Section 6 concludes this paper and discusses future directions.

2. The Preemptive Software Project Scheduling Problem Considering Personality Traits

This section describes the PSPSP-PT and illustrates the problem with an example.

2.1. Problem Statement

The PSPSP-PT is described as follows.

Task A software project is represented by a directed graph $G=\left(N,A\right)$, where $N=\{\mathrm{0,1},\dots ,n+1\}$ is the set of nodes, representing the tasks in the project. The dummy tasks 0 and $N$ stand for the beginning and the end of the project, respectively. The arc set $A\subseteq N\times N$ is the set of precedence relationships. If $(i,j)\in A$, there is a precedence relationship between tasks $i$ and $j$, which means the start time of task $j$ should not be earlier than the finish time of task $i$. We call task $i$ the predecessor of task $j$, and task $j$ is the successor of task $i$. ${IP}_j$ and ${IS}_j$ represent the immediate predecessor and immediate successor task sets of task $j$, respectively. The duration $d_j$, the start time ${st}_j$, and the finish time ${ft}_j$ of each task $j$ are all integers. Note that the duration of dummy tasks is 0. The deadline of the project is $\overline{d}$.

Preemption During execution, each task $j$ can be preempted at any integer timepoint and can be preempted at most $d_j$ times. After task $j$ is preempted, it can continue to be executed at any subsequent timepoint. Consequently, each non-dummy task $j$ can be decomposed into $d_j$ unit-duration subtasks $j_q\in \{j_1,j_2,\dots ,j_{d_j}\}$. There exists a precedence relationship between adjacent subtasks ($j_q\prec j_{q+1},\forall q\in \{\mathrm{1,2},\dots ,d_j-1\}$). Each subtask $j_q$ must be executed exactly once.

Skills Each task requires at least one skill during execution. The set $S$ denotes the skills required in the project, and $S_{jq}\subseteq S$ represents the skills involved in subtask $j_q$. The main resources in a software project are multi-skilled employees, and the employee set is denoted as $E$. The subset $E_s\subseteq E$ contains employees equipped with skill $s\in S$. The workload of skill $s$ in subtask $j_q$ is denoted by $r_{jqs}$. If employee $e$ is assigned to subtask $j_q$, then $x_{jqse}$ represents the workload contributed by this employee using skill $s$ on subtask $j_q$. Dummy tasks do not consume any resources. For the same skill, different employees have different proficiency levels. The efficiency of employee $e$ in skill $s$ is denoted by ${\eta }_{es}$, with $1/{\eta }_{es}$ representing the time required for employee $e$ to complete a unit workload using skill $s$. If employee $e$ does not possess skill $s$, then ${\eta }_{es}=0$.

Work Intensity We let parameter $\rho$ denote the estimated upper bound of work intensity that all employees must endure per unit time, where $\rho \in \left(\mathrm{0,1}\right)$. A higher $\rho$ implies a greater workload for the employees. $\rho$ is calculated as follows:

$$\rho ={\displaystyle \frac{E\left(r_{jqs}\right)\times {\sum }_{j\in N}Num\left(S_j\right)}{{\sum }_{e\in E}{R}_e^{max}}}$$

(1)

where $R_e^{max}$ represents the maximum working time of employee $e$ per unit time; $E\left(r_{jqs}\right)$ represents the average workload demand of all tasks for the skills required, $E\left(r_{jqs}\right)$ = ${\displaystyle \frac{{\sum }_{j\in N}{\sum }_{s\in S_j}{r}_{jqs}}{{\sum }_{j\in N}Num\left(S_j\right)}}$; and $Num\left(S_j\right)$ represents the number of skill types required by task $j$.

Personality Traits From the perspective of how personality traits affect employee work efficiency, we comprehensively consider the impact of the degree of match between employee personality traits and the skills they use on their work efficiency. For instance, tasks such as user experience analysis are often performed more effectively by extroverted employees due to their inherent strengths in social interaction and communication.

We introduce the matching coefficient ${\mu }_{es}\in \left[\mathrm{0,2}\right]$, which represents the degree of match between employee $e$’s personality traits and the task requiring skill $s$. When ${\mu }_{es}=1$, it indicates that employee $e$’s performance in personality traits just meets the requirements of skill $s$, with no effect on work efficiency. When ${\mu }_{es}>1$, employee e’s performance in personality traits exceeds the requirements of skill s, which has a positive impact on work efficiency. Conversely, when ${\mu }_{es}<1$, employee $e$’s performance in personality traits does not meet the requirements of skill $s$, resulting in reduced work efficiency. The matching coefficient ${\mu }_{es}$ is calculated based on the study by Santos et al. (2013) [37], incorporating personality traits into the calculation process. First, using the Big Five Personality Traits model, employees’ personality traits are measured on five dimensions, neuroticism (N), extraversion (E), openness to experience (O), agreeableness (A), and conscientiousness (C), with results denoted as $p_{ie}\in \left[\mathrm{0,10}\right]$, representing employee $e$’s score on dimension $i$. Then, ${\varpi }_{is}$ is introduced as the weight of dimension $i$’s impact on skill $s$, with its value obtained through expert scoring. The matching coefficient ${\mu }_{es}$ of employee $e$ using skill $s$ can be expressed as follows [37]:

$${\mu }_{es}={\sum }_{i=1}^5{\phi }_i{\varpi }_i{\gamma }_{ise}$$

(2)

where ${\gamma }_{ise}$ measures the degree of match between employee $e$ and skill $s$ on dimension $i$, ${\gamma }_{ise}=1+p_{is}^{\prime }-p_{ie}$. ${\gamma }_{ise}=1$ indicates that employee $e$’s score on dimension $i$ just meets the demand level of skill $s$, that is, $p_{is}^{\prime }=p_{ie}$; ${\gamma }_{ise}<1$ indicates that employee $e$ does not meet the demand level of skill $s$ on dimension $i$; ${\gamma }_{ise}>1$ indicates that employee $e$’s score exceeds the demand level of skill $s$ on dimension $i$. ${\phi }_i$ is a scaling factor, which is used to reduce the matching coefficient more when the attributes with higher weights do not match. It is calculated as follows [37]:

$${\phi }_i=\left\{\begin{array}{c}{\phi }_{i-1}, if p_{ie}\ge p_{is}^{\prime }\hfill \\ {\phi }_{i-1}-{\varpi }_i/{\displaystyle \sum _{i=1}^5}{\varpi }_i, if p_{ie}<p_{is}^{\prime }\hfill \end{array}\right.$$

(3)

Subsequently, we consider the effect of personality matching on employee efficiency, resulting in the adjusted efficiency ${\eta }_{es}^{\prime }={{\mu }_{es}\times \eta }_{es}$.

Scheduling objective The task of the PSPSP-PT is to generate a schedule that indicates the start time of each task and assign multi-skilled employees with varying personality traits to appropriate tasks while satisfying constraints such as skill matching, precedence relationships, and the project deadline such that the total project cost is minimized. The total cost of the project consists of two items: (1) The total basic salary of employees ($\sum _{e\in E}{c}_e\times {st}_{n+1}$), where $c_e$ is the basic salary of employee $e$ per unit time, and ${st}_{n+1}$ is the start time of the dummy task $n+1$, which corresponds to the project makespan (regardless of whether employees are assigned tasks, they are entitled to receive their basic salary); (2) the total performance salary of an employee ($\sum _{e\in E}\sum _{j\in N}{\sum }_{q=1}^{d_j}\sum _{s\in S_e}({\displaystyle \frac{1}{{\eta }_{es}\times {\mu }_{es}}}\times x_{jqse}\times c^{\prime })$), where $c^{\prime }$ is the performance salary of employee $e$ per unit time, and ${\displaystyle \frac{1}{{\eta }_{es}\times {\mu }_{es}}}$ $\times x_{jqse}$ is the actual working duration of employee $e$ (employees will only receive performance pay if they participate in the tasks).

2.2. Example

This section shows an example that demonstrates our problem. We assume that a software system development project consists of three non-dummy tasks. The project network graph is shown in Figure 1, where solid circles indicate non-dummy tasks, dashed circles indicate dummy tasks, the numbers inside the circles are task indexes, and the numbers above the circles are task durations. The skills required in the project are programming ($s_1$), database design ($s_2$), and web design ($s_3$).

Table 1. The task attributes.

Task Index	Task Name	Duration	Workload Demand
			Programming $({\mathit{s}}_1$)	Database Design $({\mathit{s}}_2$)	Web Design $({\mathit{s}}_3$)
0	Dummy start task	0	0	0	0
1	Web design and implementation	3	0.7	0	1.2
2	Database design and implementation	1	1.5	1.6	0
3	System backend design and implementation	3	1.6	0	0
4	Dummy end task	0	0	0	0

shows the information about the skills required in each task, the workload required at each stage, and the duration. For example, task 3 requires one employee with programming skills, where the efficiency of programming skills is 1, to work 1.6 man-hours per day for a total of three days to complete. The project involves three employees, and their basic information (maximum working hours per day, performance salary, basic salary, skill efficiency, matching coefficient) is shown in

Table 2. The employee attributes.

Employee Index	Maximum Daily Working Time	Performance Salary	Basic Salary	Skill Efficiency ${\mathit{\eta }}_{\mathit{e}\mathit{s}}$			Matching Coefficient ${\mathit{\mu }}_{\mathit{e}\mathit{s}}$
				${\mathit{s}}_1$	${\mathit{s}}_2$	${\mathit{s}}_3$	${\mathit{s}}_1$	${\mathit{s}}_2$	${\mathit{s}}_3$
1	1.2	30	10	1.5	0	0.8	0.5	1	0.1
2	1	30	12	1.5	0.6	1	1.5	0.5	1.5
3	1.2	30	8	0	1.5	1.5	0	1	1.5

.

3. Mixed-Integer Linear Programming Model

In this section, we formulate a mixed-integer linear programming model for the PSPSP-PT. In addition to the decision variable $x_{jqse}$ mentioned above, we further introduce the decision $y_{tjq}\in \left\{\mathrm{0,1}\right\}$, which indicates whether the $q$th subtask of task $j$ ($j_q$) starts at instant $t$. Specifically, when the duration $d_j$ of task $j$ is zero, indicating it is a dummy task with no subtasks, the decision variables simplify to $y_{t0}$ and $y_{t(n+1)}$, with the subscript $q$ omitted. The value rules for $y_{tjq}$ are as follows:

$$y_{tjq}=\left\{\begin{array}{cc}1,& if the qth subtask of task j starts at time t\\ 0,& otherwise\end{array}\right.$$

(4)

Thus, the start time of subtask $j_q$ is given by ${st}_{j_q}={\sum }_{t=1}^{\overline{d}}(y_{tjq}\times t)$. For non-dummy tasks $j$, the start time ${st}_j={st}_{j1}$, and the end time ${ft}_j={st}_{j{d}_j}$. The project start time ${st}_0={\sum }_{t=1}^{\overline{d}}{y}_{t0}t=0$, and the project duration $T={st}_{n+1}={ft}_{n{d}_j}={\sum }_{t=1}^{\overline{d}}{y}_{t(n+1)}t=\underset{j\in N-\{n+1\}}{\max }{\sum }_{t=1}^{\overline{d}}{y}_{tj{d}_j}+1$. Based on the above description, the mixed-integer linear programming model for the PSPSP-PT is formulated as follows:

$$\mathrm{M}\mathrm{i}\mathrm{n} w^k\sum _{e\in E}\sum _{j\in N}\sum _{q=1}^{d_j}\sum _{s\in S_e}({\displaystyle \frac{1}{{\eta }_{es}\times {\mu }_{es}}}\times x_{jqse}\times c^{\prime })+w^b\sum _{e\in E}{c}_e\sum _{t=1}^{\overline{d}}{y}_{t(n+1)}t$$

(5)

$$\mathrm{S}.\mathrm{T}. \sum _{t=1}^{\overline{d}}{y}_{tjq}=1, \forall j\in N$$

(6)

$$\sum _{t=1}^{\overline{d}}{y}_{tj1}t\ge \sum _{t=1}^{\overline{d}}{y}_{ti{d}_i}t+1, \forall (i,j)\in A$$

(7)

$$\sum _{t=1}^{\overline{d}}{y}_{tj(q+1)}t\ge \sum _{t=1}^{\overline{d}}{y}_{tjq}t+1, \forall j\in N,q=1,\dots ,d_j-1$$

(8)

$$\sum _{e\in E_s}{x}_{jqse}\ge r_{jqs}{y}_{\tau jq}, \forall j\in N;q=1,\dots ,d_j;\tau =0,\dots ,\overline{d}-1;\forall s\in S_{jq}$$

(9)

$$\sum _{s\in S_e}{\displaystyle \frac{1}{{\eta }_{es}\times {\mu }_{es}}}\times x_{jqse}\le R_e^{max}, \forall j\in N;q=1,\dots ,d_j;\forall e\in E$$

(10)

$$y_{tjq}\in \left\{\mathrm{0,1}\right\}, \forall j\in N;q=1,\dots ,d_j;t=0,\dots ,\overline{d}-1$$

(11)

$$x_{jqse}\ge 0, \forall j\in N;q=1,\dots ,d_j;\forall s\in S;\forall e\in E_s$$

(12)

In the above model, the objective function (5) minimizes the total cost of the project, where $\sum _{e\in E}{c}_e\times {\sum }_{t=1}^{\overline{d}}{y}_{t(n+1)}t$ represents the sum of the basic salary for all employees with a weighting factor of $w^b$. $\sum _{e\in E}\sum _{j\in N}{\sum }_{q=1}^{d_j}\sum _{s\in S_e}({\displaystyle \frac{1}{{\eta }_{es}\times {\mu }_{es}}}\times x_{jqse}\times c^{\prime })$ represents the performance salary of employees with a weight coefficient $w^k$, considering that, in practice, the basic salary of employees is a fixed cost of the enterprise. In addition to undertaking project tasks, employees also have to undertake other work, such as the daily affairs of the enterprise. The basic salary cost of employees during the project period should be allocated to other affairs of the company, so $w^b=0.3$, and the performance salary as the performance reward for employees participating in the project is completely part of the human cost of the project, so $w^k=1$.

Constraint (6) ensures that each subtask $j_q$ has exactly one start time throughout the project. Constraint (7) describes the precedence relationship constraint between tasks, i.e., the start time ${\sum }_{t=1}^{\overline{d}}{y}_{tj1}t$ of the first subtask $j_1$ of the subsequent task $j$ should be no earlier than the finish time ${\sum }_{t=1}^{\overline{d}}{y}_{ti{d}_i}t+1$ of the last subtask $i_{d_i}$ of the preceding task $i$. Constraint (8) describes the precedence relationship constraint between subtasks in task $j$. Constraint (9) indicates that, for any instant $\tau =0,\dots ,\overline{d}-1$, if subtask $j_q$ starts at instant $\tau$($y_{\tau jq}=1$), then the workload demand $r_{jqs}$ of subtask $j_q$ for various skills $s$ ($s\in S_{jq}$) needs to be allocated. The allocation object is the employee $e$ with skill $s$, i.e., $e\in E_s$, and the allocated workload is $x_{jqse}$. Constraint (10) is a resource constraint. The time required for any employee $e$ to complete the assigned workload in any subtask $j_q$ cannot exceed the maximum working time of the employee per unit time $R_e^{max}$. Constraints (11) and (12) define the value range of decision variables $y_{tjq}$ and $x_{jqse}$.

Note that the impact of employee personality is considered in our model. Specifically, in our objective function (5), personality trait-related factor ${\mu }_{es}$ is considered. The same factor is also considered in constraint (10) when dealing with the resource constraint. It is also worth noting that the establishment of the mixed-integer linear programming model enables a clearer articulation of the decision variables, objectives, and constraints of the problem.

The PSPSP-PT in this paper is NP-hard. Specifically, consider a special case of the PSPSP-PT. First, let the duration of each task be 1. Second, assume that each employee possesses only one skill with identical skill efficiency and matching coefficients and that the maximum working time for each employee is the same, i.e., $\left|S_e\right|=1,{\eta }_{se}=1,{\mu }_{es}=1,R_e^{max}=1$. Then, let the basic salary per unit time of each employee be 1, and do not consider the employee’s performance salary, i.e., $c_e=1,c^{\prime }=0,w=0$. Under the above conditions, the PSPSP-PT becomes the classic resource-constrained project scheduling problem (RCPSP) with the objective of minimizing the project makespan. The RCPSP is NP-hard [38]. Consequently, as a generalization of the RCPSP, the PSPSP-PT is also NP-hard. Therefore, in order to efficiently solve large-scale instances, we will design a heuristic scheduling algorithm in the next section.

4. A Dual Priority Rules-Based Heuristic

By analyzing our problem and model, we find that the following two factors significantly affect the total cost of software projects: (1) project duration—the shorter the project duration, the smaller the total basic salary of employees; (2) employee efficiency. When assigning employees to meet the workload requirement for skill $s$ in subtask $j_q$ (i.e., $r_{jqs}$), prioritizing the employee with higher skill efficiency can help reduce the project duration, thereby minimizing the costs associated with performance salary.

Based on the above analysis, we design a dual priority rules-based heuristic scheduling algorithm (DPRH) to efficiently solve the PSPSP-PT. The algorithm addresses two key problems (i.e., task selection problem and employee assignment problem) that need to be solved in the PSPSP-PT and designs task selection priority rules and employee assignment priority rules, respectively, making full use of the above two factors to construct a schedule that can minimize the total cost of the project. In our DPRH, different priority rules related to task selection and employee assignment can be flexibly embedded.

The main process of our DPRH is as follows. First, the project network is converted into a unit-time project network (Section 4.1) to cope with the task preemption. Then, the following steps are repeated until all tasks are scheduled: (a) select the next task to be executed based on task selection priority rules (Section 4.2); (b) determine the start time of the selected task and assign employees to it based on employee assignment priority rules (Section 4.3).

4.1. Generation of Unit-Time Project Network

The purpose of generating a unit-time project network is to address the task preemption. The basic idea of converting the project network $G$ into the unit-time project network G^′ is to divide each task $j$ in $G$ into subtasks $j_q$ with a duration of one time unit. These subtasks are renumbered as nodes, and the precedence relationships between subtasks in the same task are added. These subtasks, the newly added priority relationships, and the original priority relationships in $G$ together constitute G^′. Specifically, each node in G^′, i.e., subtask $j_q$, is renumbered starting from 0 (0 denotes a dummy start task) to create a new task set $I$, and the number of the subtask $j_q$ in the set $I$ is $m=\sum _0^{j-1}{d}_j+q$. The precedence relationship $i\prec j$ in the project network $G$ is converted into the precedence relationship $n\prec m$ between the first subtask $j_1$ (with numbering $m=\sum _0^{j-1}{d}_j+1$) of the subsequent task $j$ and the last subtask $i_{d_i}$ (with numbering $n=\sum _0^{i-1}{d}_i+d_i$) of the predecessor task $i$. Additionally, precedence relationships between the subtasks of task $j$ are incorporated. Based on the above method, the example project network in Section 2.2 can be converted into the unit-time network shown in Figure 2. The duration of each subtask in Figure 2 is one unit, and the resource requirements of the subtask are the same as the original task.

Subsequent scheduling will be based on G^′. The advantage is that there is no need to consider the task preemption separately because each subtask already has a unit duration. If there is no time delay between all subtasks of a task, it means that the task has not been preempted; if there is a time delay between two or more subtasks, it means that the task has been preempted at least once.

After obtaining the unit-time network G^′, initialize the DPRH by setting the start time of the dummy start task ${st}_0=0$. Define the set of scheduled tasks $Skd=\left\{0\right\}$, and the set of schedulable tasks $D$ is an empty set. Initialize the resource availability matrix $RE{S}_{\overline{d}\times \left|E\right|}$, where each element $RE{S}_{\overline{d}\times \left|E\right|}$ represents the available work capacity of employee $e$ in period $t$.

4.2. Task Selection Based on Priority Rules

Our DPRH offers a variety of priority rules for task selection. With the objective of minimizing the total project cost as much as possible, six different priority rules are incorporated, with their definitions provided in

Table 3. Task selection priority rules.

Priority Rule	Symbol	Definition
Earliest start time first	$p_{AL3}$	$\mathrm{Max} {es}_{j_q}$
Latest finish time first	$p_{AL4}$	$\mathrm{Max} {ls}_{j_q}$
Maximum resource demand first	$p_{AL5}$	$\mathrm{Max} {\sum }_{q=0}^{d_j}{\sum }_{s\in S}{r}_{jqs}$
Critical path priority	$p_{AL6}$	Max frequency of $j$ on the critical path
Random rule	$p_{ALr}$	Randomly select one rule from the above priority rules

. During the execution of our DPRH, any of the priority rules can be applied.

4.3. Employee Assignment Based on Priority Rules

In the DPRH, we design an employee assignment algorithm based on priority rules (Algorithm 1). Given a task that requires employee assignment, the algorithm first determines the employee assignment order based on the priority rules and then determines the start time of the task as early as possible while satisfying various constraints.

Algorithm 1. Employee assignment algorithm
Input: task $j_q$, earliest start time ${es}_{j_q}$, latest start time ${ls}_{j_q}$, resource availability matrix $RES$, employee assignment priority rules $p_{RA}$
Output: start time ${st}_{jq}$, workload $x_{jqse}$ of employee $e$ using skill $s$ on subtask $j_q$, remaining resource availability matrix ${RES}^{\prime }$
1	Initiation: $lag=0$;${st}_{j_q}={es}_{j_q}$; calculate the earliest/latest start time ${es}_{j_q}/{ls}_{j_q}$ for $j_q$ based on the Critical Path Method
2	While ${st}_{j_q}+lag\le {ls}_{j_q}$
3	${st}_{j_q}={st}_{j_q}+lag$
4	${RES}^{\prime }=RES$
5	$isFeasible=True$
6	For s = 1 to |S|
7	Select skill $s$ from $S$ according to the skill scheduling order
8	$require=r_{jqs}$
9	If $require\ne 0$
10	For e = 1 to |$R_s$|
11	Select employee $e$ from $R_s$ according to the priority rule $p_{RA}$
12	If ${RES}^{\prime }\left[{st}_{jq}\right]\left[e\right]\ast {{\eta }^{\prime }}_{s{e}^{\ast }} \ge require$
13	${RES}^{\prime }\left[{st}_{jq}\right]\left[e\right]={RES}^{\prime }\left[{st}_{jq}\right]\left[e\right]-require/{{\eta }^{\prime }}_{s{e}^{\ast }}$
14	$x_{jqse}=x_{jqse}+require$
15	$require=0$
16	$break$
17	else
18	$x_{jqse}=x_{jqse}+{RES}^{\prime }\left[{st}_{jq}\right]\left[e\right]\ast {{\eta }^{\prime }}_{s{e}^{\ast }}$
19	$require=require-{RES}^{\prime }\left[{st}_{jq}\right]\left[e\right]\ast {{\eta }^{\prime }}_{s{e}^{\ast }}$
20	${RES}^{\prime }\left[{st}_{jq}\right]\left[e\right]=0$
21	End For
22	If ${RES}_{E_s}=0$ and $require\ne 0$
23	Taks $j_q$ cannot start at instant ${st}_{jq}$
24	$isFeasible=False$
25	$lag=lag+1$
26	$break$
27	End For
28	If $isFeasible$
29	Return the current start time ${st}_{jq}$ and the updated resource availability $RE{S}^{\prime }$
30	else
31	$continue$
32	End while

In Algorithm 1, given a task $j_q$, starting from its earliest start time (${st}_{j_q}={es}_{j_q}$), the requirements of task $j_q$ for various skills are met in descending order according to the skill scarcity ($\left|E_s\right|$). If, during the assignment process, it is discovered that resources are insufficient (i.e., when ${RES}_{E_s}=0$ and the skill requirement $r_{jqs}$ remains unmet), the time delay $lag$ is incremented (lines 22–26 of Algorithm 1, where the sum of $lag$ and ${es}_{j_q}$ determines the earliest feasible start time for task $j_q$) until a suitable start time is found that ensures all skill requirements within the duration of task $j_q$ are met. The algorithm ultimately outputs the start time of task $j_q$, the assigned employees, and the workload of these employees.

Table 4. Employee assignment priority rules.

Priority Rule	Symbol	Definition
Maximum adjusted skill efficiency priority rule	$p_{RA1}$	$\mathrm{Max} {\eta }_{se}\times {\mu }_{es}$
Maximum initial skill efficiency priority rule	$p_{RA2}$	$\mathrm{Max} {\eta }_{se}$
Maximum personality matching coefficient priority rule	$p_{RA3}$	$\mathrm{Max} {\mu }_{es}$
Random rule	$p_{RAr}$	Randomly select one rule from the above priority rules

shows the priority rules used for employee assignment in Algorithm 1. During the execution of Algorithm 1, any priority rule can be selected from Table 4. There are two approaches to reducing project cost during employee assignment: prioritizing employees with higher efficiency and those with better personality matching. For this purpose, we design the maximum initial skill efficiency priority rule ($p_{RA2}$) and the maximum personality matching coefficient priority rule ($p_{RA3}$). Combining the above two factors, i.e., considering the influence of personality traits on employee efficiency, we also design the hybrid priority rule: the maximum adjusted skill efficiency priority rule ($p_{RA1}$). In addition, the random priority rule $p_{RAr}$ randomly selects one of the three priority rules mentioned above. In the case of multiple employees with the same priority value, the employee with the smallest number will be selected.

Applying our DPRH to solve the example project in Section 2.2, the resulting schedule is shown in Figure 3. In Figure 3, the vertical axis is the employee index, and the horizontal axis is the time. Each rectangle in Figure 3 represents a subtask. Inside the rectangle, we give the subtask number of the task that the rectangle belongs to and the skills used in the task. Looking at Figure 3 horizontally, we can observe which tasks each employee is assigned to. As can be observed in Figure 3, the task web design and implementation (task 1) is preempted after its first subtask is completed, and its subsequent subtasks continue to be executed at instant 4. In this schedule, the total project cost is 402.

4.4. Computational Complexity Analysis

The worst-case running time complexity of our dual priority rules-based heuristic algorithm is analyzed as follows. The complexity of generating the unit-time project network is $O\left(\left|N\right|+\left|A\right|+n\right)$. The complexity of determining the task scheduling order based on priority rules is $O(\left|N^{\prime }\right|+\left|A^{\prime }\right|+n)$, where $\left|N^{\prime }\right|$ is the total number of subtasks in the unit-time project network and $\left|A^{\prime }\right|$ is the number of precedence relationships. The complexity of calculating the employee assignment priority is $O\left(\right|S|\times |E\left|\right(\mathit{log}\left|E\right|+1\left)\right)$. Therefore, Algorithm 1 is characterized by a complexity of $O(SL\times |S|\times |E\left|\right)$, where $SL$ is the maximum slack time across all subtasks.

Based on the above estimation, the complexity of our DPRH is acceptable and does not involve non-polynomial computational complexity.

5. Computational Experiments

This section analyzes the performance of our DPRH through computational experiments. Our algorithm has been implemented in Python 3.7. Computational experiments were conducted on an Intel i5 Core PC with 3.20 GHz CPU and Windows 7 64-bit. In the following subsections, we first introduce the benchmark dataset, comparison algorithm, and performance measures used in the computational experiments. We then evaluate the performance of our DPRH by comparing it with the EDA. Finally, we discuss the robustness of our DPRH based on a sensitivity analysis.

5.1. Benchmark Dataset

The construction of the benchmark dataset follows Heimerl and Kolisch (2010) [39], which conducts a full factorial experimental design based on five characteristic parameters, the number of tasks $n$, order strength (OS), work intensity $\rho$, the number of skills possessed by each employee |$S_e$|, and the personality matching coefficient ${\mu }_{es}$, to construct a benchmark dataset for computational experiments. Among them, OS $\in$(0,1) reflects the number of precedence relationships in the project network, and a larger OS indicates more priority relationships.

First, we use the project scheduling problem instance generator RanGen to generate project networks with different $n$ and OS [40]. Then, for each project network generated by RanGen, we determine its $\rho$, |$S_e$|, and ${\mu }_{es}$. As shown in

Table 5. Parameter settings for the benchmark dataset.

Parameter	Values
$n$	10, 20, 30, 60
$OS$	0.3, 0.7
$|S_e$|	2, 4
$\rho$	0.3, 0.7
${\mu }_{es}$	${TN}_{\mathrm{0.5,1.0}}\left(\mathrm{0.75,0.25}\right)$$,{TN}_{1.0,1.5}\left(\mathrm{1.25,0.25}\right)$

, for $\rho$, a value of 0.3 (0.7) corresponds to a low (high) workload for employees. A value of 2(4) for |$S_e|$ indicates fewer and more types of skills mastered by each employee. When ${\mu }_{es}$ follows the truncated normal distribution ${TN}_{\mathrm{0.5,1.0}}\left(\mathrm{0.75,0.25}\right)$ and ${TN}_{\mathrm{1.0,1.5}}\left(\mathrm{1.25,0.25}\right)$, it means that the degree of match between employee personality traits and their skills is low and high, respectively. We set some different values for the five factors (i.e., $n$, OS, $\rho$, |$S_e$|, and ${\mu }_{es}$) in Table 5 and generate five instances for each parameter combination. We thus obtain $4\times 2\times 2\times 2\times 2\times 5=320$ project instances in total.

Then, for each project instance described above, the total number of employees is set to $\left|R\right|=10$. The maximum working time of employee $e$ per unit time $R_e^{max}$ is selected randomly from the interval $\left[\mathrm{0.8,1.2}\right]$. The skill efficiency ${\eta }_{es}$ is drawn from the truncated normal distribution ${TN}_{\mathrm{0.5,1.5}}\left(\mathrm{1,0.25}\right)$. The basic salary per unit time $c_e$ is drawn from the truncated normal distribution ${TN}_{\mathrm{8.75,13.75}}\left(\mathrm{11.25,2.5}\right)$. Let the unit performance salary $c^{\prime }=30$ and the total number of skills involved in each project $\left|S\right|=6$. Each task requires, at most, four of these skills, which are randomly drawn from all skills. The demand for each skill $r_{jqs}$ for each task follows a normal distribution with a mean of $E\left(r_{jqs}\right)$ and a standard deviation of $\mathsf{\sigma }=0.1\times E\left(r_{jqs}\right)$, where $E\left(r_{jqs}\right)$ is derived and calculated based on Formula (1).

Table 6. Fixed parameter values in the benchmark dataset.

Parameter	Values
$\left|R\right|$	10
$\left|S\right|$	6
$|S_j|$	$\le$4
$R_e^{max}$	Randomly sampled from the interval [0.8, 1.2]
$c_e$	Sampled from the truncated normal distribution ${TN}_{\mathrm{8.75,13.75}}\left(\mathrm{11.25,2.5}\right)$
$c^{\prime }$	30

shows the values of fixed parameters in the benchmark dataset.

5.2. Baseline Algorithm and Performance Measure

We evaluate the performance of our DPRH through experiments by comparing it with a baseline algorithm. The estimation of distribution algorithm (EDA), which is a population evolutionary algorithm based on statistical learning theory, is selected as the baseline algorithm for comparison [41]. It has been widely applied in the multi-mode resource-constrained project scheduling problem (MRCPSP) and achieved better solution results [42].

The EDA algorithm in this paper is based on Wang and Fang (2012) [42]. In order to make the EDA able to solve the PSPSP-PT, we made the following modifications to the EDA: (1) Solution Encoding. The encoding of solutions consists of two main parts: AL represents the execution order of subtask $j_q$. $\Gamma$ represents the employee assignment scheme. For each skill $s\in S$, ${\gamma }_s\in \Gamma$, ${\gamma }_s=\left(RA,\mathrm{S}\mathrm{K}\right)$, where RA is the employee number sequence and $\mathrm{S}\mathrm{K}$ is the random key vector, describing the workload ratio assigned to the corresponding employee in $\mathrm{R}\mathrm{A}$. Thus, for any subtask $j_q$ requiring skill $s$, the employee assignment scheme is ${\gamma }_s=\left(RA,\mathrm{S}\mathrm{K}\right).$ (2) Probability matrix. The EDA contains two probability matrices, ${Prob}_{AL}\left(GEN\right)$ and ${Prob}_{TA}\left(GEN\right)$. ${Prob}_{AL}\left(GEN\right)$ is the same as Wang and Fang (2012) [36], ${Prob}_{TA}\left(GEN\right)$ is a matrix of |S|×|E|, and ${Prob}_{TA}\left(tGEN\right)[s,e]$ represents the probability that employee $e$ uses skill $s$ to perform the task at the GENth iteration. For ${Prob}_{TA}\left(GEN\right)$, each iteration is updated with the number of employees in the elite set who use skill $s$ to perform the task.

To evaluate the performance of the DPRH, we define the improvement ratio of the mean performance (Imp) as follows:

$$Imp={\displaystyle \frac{\sum _{i\in Set}\left[({obj}_i^{EDA}-{obj}_i)/{obj}_i^{EDA}\right]}{\left|Set\right|}}\times 100\%$$

(13)

where ${obj}_i$ represents the objective function value of the $i$th instance in the dataset obtained by the DPRH, ${obj}_i^{EDA}$ is the optimal objective function value of instance $i$ obtained by the comparison algorithm EDA, and $Imp$ represents the degree of improvement of the DPRH relative to the EDA. According to Formula (12), a higher $Imp$ value signifies a greater improvement of the DPRH over the EDA.

5.3. Experimental Result

(1)

Discussion on Priority Rules

For the DPRH, combining different task selection and employee assignment priority rules results in 20 distinct heuristic scheduling algorithms. We apply these 20 heuristic algorithms to solve the benchmark dataset in order to determine the best combination of priority rules.

Table 7. Objective function values of the DPRH under different priority rule combinations.

Task Selection Rule	Employee Assignment Priority Rule				Average	Rank
	${{\mathit{p}}^{\prime }}_{\mathit{R}\mathit{A}1}$	${{\mathit{p}}^{\prime }}_{\mathit{R}\mathit{A}2}$	${{\mathit{p}}^{\prime }}_{\mathit{R}\mathit{A}3}$	${{\mathit{p}}^{\prime }}_{\mathit{R}\mathit{A}\mathit{r}}$
$p_{ALr}$	2057.58	2104.97	2643.92	2260.49	2266.74	4
$p_{AL3}$	2057.39	2104.73	2643.86	2251.97	2264.49	2
$p_{AL4}$	2059.22	2106.51	2646.65	2255.72	2267.02	5
$p_{AL5}$	2057.48	2104.91	2643.37	2253.09	2264.71	3
$p_{AL6}$	2057.73	2104.67	2643.01	2252.33	2264.43	1
Average	2057.88	2105.16	2644.16	2254.72	2265.48	-
Rank	1	2	4	3	-	-

shows the objective function values of the schedule obtained by the DPRH under different combinations of priority rules.

As shown in Table 7, among the task selection priority rules, the critical path priority rule ($p_{AL6}$) performs best in terms of the mean objective function value, but its performance is not much different from that of other priority rules. The performance of the DPRH is more affected by the employee assignment priority rule, among which the maximum adjustment skill efficiency priority rule ($p_{RA1}$) is significantly better than other single priority rules and random priority rules. Therefore, in subsequent experiments, our DPRH uses $p_{AL6}$ as the task selection priority rule and $p_{RA1}$ as the employee assignment priority rule.

(2)

Comparative experiment results

The DPRH and EDA are used to solve the benchmark dataset, respectively. The parameters of the EDA are set as follows: the population size is 40, the elite probability is 10%, the learning speed is 0.2, and the algorithm termination condition is when 520 schedules are generated or when the calculation time reaches 1500 s. The comparative results of the algorithms are presented in

Table 8. Comparative results of our DPRH and the EDA.

$\mathit{n}$	${|\mathit{S}}_{\mathit{e}}|$	Imp	CPU Time (s)
			DPRH	EDA
10	2	14.07%	0.08	31.74
	4	19.99%	0.09	40.73
20	2	12.40%	0.69	367.04
	4	17.35%	0.66	380.68
30	2	11.46%	2.20	1101.22
	4	16.14%	1.86	1020.27
60	2	9.82%	16.18	1510.18
	4	15.85%	18.00	1510.15
Average		14.63%	4.97	723.44

.

As can be observed in Table 8, for all project instances, the DPRH outperforms the EDA in both solution quality and computational time, showing its significant advantages. In particular, as the number of tasks $n$ increases, the advantage of the DPRH in computation time becomes more and more significant, indicating that it is more competitive in solving large-scale instance problems. This is due to the DPRH employing predefined priority rules for task scheduling and staff assignment, which effectively reduces the search space. Unlike the EDA, which requires constructing complex probability models and numerous iterations, the DPRH’s direct approach reduces computational complexity and improves solution speed.

For instances with the same number of tasks, the greater the number of skills |$S_e$| possessed by each employee, the more obvious the improvement of the DPRH over the EDA, that is, the DPRH is less sensitive to the complexity of human resources (${|S}_e|$) and can flexibly adapt to different resource allocation situations. This is primarily because the DPRH is always based on a rule-driven mechanism regardless of changes in resource allocation. In contrast, the EDA requires the construction and updating of more complex probabilistic models when dealing with higher-dimensional resource attributes, which greatly impacts the computational quality.

5.4. Sensitivity Analysis

Based on the benchmark dataset, this section examines the impact of order strength (OS), employee work intensity ($\rho$), and personality matching coefficient (${\mu }_{es}$) on the performance of our DPRH. The results are shown in Figure 4. In Figure 4, the vertical axis is $Imp$, which is the degree of improvement of the DPRH relative to the EDA, and the horizontal axis represents work intensity $\rho$. In the left figure, the personality matching coefficient ${\mu }_{es}$ follows the truncated normal distribution ${TN}_{\mathrm{0.5,1.0}}\left(\mathrm{0.75,0.25}\right)$, which represents that, in these project examples, the degree of match between the employee personality traits and their mastered skills is generally low. Conversely, in the right figure, the personality matching coefficient ${\mu }_{es}$ follows the truncated normal distribution ${TN}_{1.0,1.5}\left(\mathrm{1.25,0.25}\right)$, which indicates that, in these project examples, the degree of match between the employee personality traits and their mastered skill is relatively ideal.

Figure 4 illustrates that, under different levels of the personality matching coefficient, when the order strength is given, the greater the workload, the better the solution effect of the DPRH. This indicates that our DPRH can more effectively handle projects with tight resources, particularly in scenarios where there are fewer employees and a greater task workload. Compared to the EDA, the improvement in the performance of the DPRH algorithm is more pronounced. This result further reveals that the DPRH is not sensitive to changes in workload parameters. Conversely, the order strength negatively impacts the performance of our DPRH, indicating that the DPRH is better suited for software project scheduling problems with fewer dependencies between tasks. In such cases, the algorithm can more effectively allocate resources and improve scheduling efficiency. Comparing the two sub-graphs on the left and right, our DPRH has a better improvement effect in the problem instances with a lower personality matching coefficient. This suggests that our DPRH is capable of effectively handling scenarios where the degree of match between the employee personality traits and their mastered skill is relatively ideal while also achieving satisfactory scheduling effects in situations with the degree of match being generally low.

6. Conclusions and Future Research

In this paper, we have studied the preemptive software project scheduling problem considering personality traits in which employees with varying skills and personality traits are scheduled facing constraints such as skills and precedence relationships such that the project cost is minimized. We formulate a mixed-integer programming model for the problem and design a dual priority rules-based heuristic algorithm. Based on computational experiments on a benchmark dataset containing 320 instances, the performance of our algorithm is analyzed and compared with the EDA. The results reveal that our algorithm outperforms the EDA in both solution quality and time. In terms of the mean objective function values of the obtained schedules, our algorithm is 14.63% higher than the EDA. In the meantime, the average calculation time of our algorithm (4.97 s) is much shorter than that (723.44 s) of the EDA. The sensitivity analysis further indicates that our algorithm is robust and can be effective, especially when there are few employees and large task workloads. In addition, our DPRH can achieve satisfactory scheduling results whether the employee skills are ideally matched with their personality traits or the matching degree is low.

Compared with existing studies that deal with planning a project [8], our study provides important references for software project managers in their practical work to create a more comprehensive plan. Our results indicate that, in software project management, project managers should pay attention to the understanding and evaluation of the personality traits of team members. By rationally scheduling team members with different skills and personality traits, the schedule and human resource allocation can be optimized, thereby reducing the overall cost of the project. In addition, project managers should effectively utilize the task preemption and arrange tasks in an interspersed manner to shorten the project duration.

The limitation of our study is that, although our algorithm can yield satisfactory solutions in a short time, it may not achieve optimal solutions in some cases. Future research will consider designing a branch-and-bound algorithm for the PSPSP-PT to obtain the optimal solution for small-scale instances. Additionally, our study assumes a deterministic environment and does not account for uncertainties, such as employee resignation and uncertain activity duration. Therefore, investigating the PSPSP-PT problem in uncertain environments represents a valuable area for further study.