Background & Literature Review
RCPSP, MSRCPSP, prior methods, research gap, and contributions.
IEEE Access · Volume 12 · 2024
Weighted Multi-Skill
Project Scheduling
A Greedy and Parallel Scheduling approach
Authors: Saeed Akbar, Muhammad Zubair, Rizwan Khan, Ubaid Ul Akbar, Rahmat Ullah and Zhonglong Zheng
Presented by
Ghazal Zolfi Moselo
Student ID:
401104146
·
MohammadMahdi Montazeri Hedesh
Student ID:
401104479
Course Instructor
Prof. Mohsen VarmazyarPresentation roadmap
From the Scheduling Problem to Experimental Evidence
Problem Formulation
Task sets, precedence graph, skill matrices, decision variable, objective, and constraints.
Proposed GPS Algorithm
Greedy best-fit allocation, parallel task groups, five sub-algorithms, and resource reallocation.
Simulation & Numerical Results
Seven experiments, GPS–PSS comparison, resource wastage, and sensitivity analysis.
Conclusion & Critical Assessment
Main findings, evidence scope, limitations, author-stated future work, and takeaways.
Problem evolution
From Resource-Constrained Scheduling to Weighted Multi-Skill Resources
The paper models precedence-constrained software tasks performed by heterogeneous, multi-skilled human resources.
Resource Constraints + Precedence
Schedule project activities under limited renewable resources and task-dependency constraints.
Skill Requirements Are Added
Tasks require specific skills, while each human resource may master one or more skills.
Proficiency is weighted
Each resource–skill pair receives a proficiency weight in the interval \([0,1]\).
Related work and gap
Existing Approaches Address Key Dimensions, but Two Practical Gaps Remain
MILP and Exact Optimization Models
Model multiple objectives, uncertainty, cost, risk, and quality, but become computationally expensive for large instances.
Priority and schedule-generation rules
Generate feasible schedules quickly, but may use simplified employee abilities, incomplete precedence modeling, or limited dynamic adaptation.
GA, PSO, VNS and related search
Explore complex search spaces effectively, but several studies still assume homogeneous proficiency, single-resource assignments, or simplified skill transitions.
UncertaintyProject costMulti-project schedulingEmployee additionSkill switchingSoft skillsMultitaskingDynamic availabilityCollaboration
Gap 01Heterogeneous proficiency across resource–skill pairs is often overlooked.
Gap 02Resources released by earlier-finishing tasks may remain underutilized.
Literature review · exact and heuristic studies
Exact and Heuristic Studies Expand the Context
| Study | Method | Objective / modeled features | Stated limitation |
|---|---|---|---|
| Mirnezami et al. [17] | Multi-objective MILP | Makespan, resource cost, risk; preemption and uncertainty | High computational complexity |
| Fuzzy MILP [36] | MILP + fuzzy programming | Duration, cost, quality; overlap and rework | High computational complexity |
| Cui et al. [21] | VNS heuristic | Multi-project, multi-mode, multi-skill R&D allocation | Constant ability coefficient |
| Nigar et al. [19] | Dynamic heuristic | New employee addition; budget, time, concurrent projects | Omits slack and requirement cancellation |
| Haroune et al. [20] | Goal programming + greedy/local/tabu | Shared multi-skill employees; task-load constraints | No project/task precedence |
Literature review · metaheuristic studies
Metaheuristics Add Flexibility and Assumptions
| Study | Method | Objective / modeled features | Stated limitation |
|---|---|---|---|
| Chen et al. [33] | HH-FGP | Stochastic multi-project scheduling with non-identical machines | Paper presents a different stochastic setting |
| Ma et al. [29] | Tabu search | Robust schedule with multi-skilled resources and skill changes | Skill-switching cost omitted |
| Snauwaert et al. [9] | Factor study | Skill proficiency, workforce size, multi-skilled resources | Deterministic; no stochastic dimension |
| Wang et al. [23] | GA-PR / dynamic optimization | Uncertain availability; reallocation from idle resources | Homogeneous resources |
| Li et al. [24] | MODJaya | Makespan and cost; efficient multi-objective search | Single-resource task assignments |
Research objective and contribution
Minimizing Makespan Through Smarter Resource Allocation
Greedy best fit
Select the available resource with the highest proficiency in each required skill.
Parallel task groups
Group precedence-compatible tasks into subsets that can execute concurrently when sufficient resources are available.
Surplus allocation
Assign surplus resources to the latest-finishing task and its latest-finishing skill.
Freed-resource reuse
When the earliest-finishing task completes, release and reassign its resources to the remaining tasks in the same parallel group.
Central claimWeighted skill matching and resource reuse reduce project makespan.
Problem setup
Project Tasks Are Modeled Through a Directed Precedence Graph
Tasks in the same subset have no precedence relation and may execute concurrently if sufficient resources are available.
Task set:
\(T=\{t_0,t_1,\ldots,t_n,t_{n+1}\}\).
Directed acyclic graph of task precedence relations.
Dummy start and dummy end tasks.
Total effort and task duration used by the scheduling model.
Parallel-subset structure
\[|T|=|T_1|+|T_2|+\cdots+|T_q|=n,\qquad T_i\cap T_j=\varnothing\quad(i\ne j).\]
Notation · sets and task state
Core Symbols Used by the Formulation and Algorithms
Notation · resources and timing
Assignment, Proficiency and Event-Time Symbols
Model inputs and decision variable
Two Matrices Represent Task Requirements and Heterogeneous Resource Proficiency
TS
Task–Skill Matrix
\[TS=\begin{bmatrix}t_1s_1&t_1s_2&\cdots&t_1s_m\\t_2s_1&t_2s_2&\cdots&t_2s_m\\\vdots&\vdots&\ddots&\vdots\\t_ns_1&t_ns_2&\cdots&t_ns_m\end{bmatrix}\]
\(t_i s_j\in\{0,1\}\)
A value of \(1\) means task \(t_i\) requires skill \(s_j\).
connected through\(w_{r_k s_l t_i}\)binary resource–skill–task assignment
RS
Resource–Skill Matrix
\[RS=\begin{bmatrix}r_1s_1&r_1s_2&\cdots&r_1s_m\\r_2s_1&r_2s_2&\cdots&r_2s_m\\\vdots&\vdots&\ddots&\vdots\\r_ks_1&r_ks_2&\cdots&r_ks_m\end{bmatrix}\]
\(r_k s_j\in[0,1]\)
The value expresses the proficiency of resource \(r_k\) in skill \(s_j\).
\[w_{r_k s_l t_i}=\begin{cases}1,&\text{if }r_k\text{ with }s_l\text{ is assigned to }t_i,\\0,&\text{otherwise.}\end{cases}\]
Feasibility condition: \(r_k\in R,\;t_i\in T,\;s_l\in S_{t_i}\cap S^{r_k}\).
Mathematical Formulation · Objective and Constraints (2)–(4)
Minimize the Project Completion Time
The start time of the dummy end task represents the project makespan.
\[B_{t_j}\ge B_{t_i}+d_{t_i},\qquad t_i,t_j\in T\land(t_i,t_j)\in E\]
A successor starts only after its predecessor finishes.
\[\sum_{r_k\in R_{s_l}}w_{r_k s_l t_i}=R_{t_i s_l},\qquad t_i\in T,\ s_l\in S_{t_i}\]
The number of assigned resources equals the resource requirement for each task–skill pair.
\[\sum_{s_l\in S^{r_k}\cap S_{t_i}}w_{r_k s_l t_i}\le 1,\qquad r_k\in R,\ t_i\in T\]
For a given task, one resource contributes through at most one skill.
Mathematical Formulation · Constraints (5)–(9)
Feasibility, Non-Negativity, Compatibility and Finish Time
\[\sum_{s_l=1}^{|S|} t_i s_l>0,\qquad \forall t_i\in T\land s_l\in S_{t_i}\]
Every project task requires at least one skill.
\[\sum_{r_k=1}^{|R|} t_i r_k>0\]
Intended meaning: at least one resource performs each project task.
\[B_{t_i}\ge0,\qquad d_{t_i}\ge0,\qquad \forall t_i\in T\]
Start times and durations are non-negative.
\[R_{t_i s_l}\subseteq\bigcup_{t_i r_k>0}S_{t_i},\qquad \forall t_i\in T\cap s_l\in S_{t_i}\]
Resources allocated to task \(t_i\) must possess the skills required to perform that task.
Notation and reporting check
Three Notation and Reporting Ambiguities Are Handled Explicitly
\(d_{t_i}\): Treated as Task Duration
The formulation initially calls \(d_{t_i}\) a deadline, while Table 1, Equations (2), (7), and (9), and the algorithm discussion use it as task duration. This presentation follows the latter interpretation.
Equation (4): Formula Scope vs. Prose
Equation (4) limits each resource to at most one skill for a given task. The broader “one task at a time” statement appears in the prose but is not explicitly represented by this equation alone.
Figure Numbers Follow the Actual Captions
The results prose refers to Figures 7 and 8 for Experiments 6 and 7. The corresponding plots are Figure 8 for task duration and Figure 9 for resource demand. This presentation uses the caption-based numbering.
GPS framework
Five Algorithms Form One Coordinated GPS Framework
Assign Resources
Select the highest-proficiency available resources
Assign Extra Resources
Allocate surplus resources to the current bottleneck
Schedule Task Subset
Schedule one group until all its tasks are completed
Create Parallel Task Groups
Form precedence-safe groups of executable tasks
GPS Main Procedure
Coordinate parallel groups and accumulate makespan
Best-fit choiceHighest proficiency in the required skill
Release eventEarliest-finishing task completes and releases resources
Surplus targetLatest-finishing task and its latest-finishing skill
Algorithm 1 · Top-Level Orchestrator
GPS Generates Parallel Task Groups, Schedules Each Group, and Accumulates Makespan
- Generate the array of parallel executable task groups.
- Skip groups containing the dummy start or end task.
- Sort tasks by finishing time, earliest first.
- Schedule the selected group and add its completion time to the makespan.
Input \(T,S,R,E\)Output \(\mathrm{project\_makespan}\)
Algorithm 2 · Create Parallel Tasks Groups
Repeatedly Group Tasks with No Unresolved Predecessors
- Scan all tasks remaining in \(T\).
- Select tasks that are not the right endpoint of any remaining precedence edge.
- Add all selected tasks to the current parallel group.
- Remove the selected tasks and their outgoing edges, then repeat.
Input \(T,E\)Output \(T_{\parallel}[\,]\)
Algorithm 3 · Schedule Tasks Subset
The Scheduler Advances from One Earliest-Completion Event to the Next
- Assign resources to tasks that are unscheduled or do not satisfy the required time condition.
- Call Algorithm 5 to allocate any remaining resources to scheduled tasks.
- Identify the earliest-finishing task, mark it complete, and release its resources.
- Update completed effort and elapsed time for the remaining running tasks.
Input \(T_{\parallel},R_{\mathrm{avail}}\)Output \(C_{T_{\parallel}}\)
Algorithm 4 · Assign Resources
For Each Required Skill, Repeatedly Assign the Highest-Proficiency Available Resource
- Process every skill required by task \(t_i\).
- Select the available resource with the highest proficiency in the current skill.
- Assign the resource and recompute the skill-specific finishing time.
- Continue until \(F_{t_i s_l}\le d_{t_i}\); if no matching resource exists, release the task’s assigned resources and return false.
Input \(t_i,R_{\mathrm{avail}}\)Output \(\mathrm{Boolean}\): true if successful
Algorithm 5 · AssignExtraResources
Assign Surplus Resources to the Latest-Finishing Task and Skill
- Remove tasks that received no initial resource assignment.
- Select the latest-finishing task among the scheduled tasks.
- Identify the latest-finishing skill of the selected task.
- Assign a compatible available resource to that skill and repeat.
Input \(T_{\parallel},R_{\mathrm{avail}}\)OutputExtra-resource assignment
Notation noteLine 9 appears intended to use the latest-finishing task \(t_{lf}\) selected in line 8. Line 17 appears intended to remove that selected task from \(T_{\mathrm{temp}}\). These are apparent notation ambiguities, not definitive corrections.
Why GPS can reduce parallel-group completion time
Each Completion Event Triggers Resource Reallocation
Initial allocation
Task ATask BTask C
Task A finishes first and releases its assigned resources.
Reallocate→
After resource release
Task A ✓ CompletedTask B — ContinuesTask C + Released Resource
Released resources accelerate the latest-finishing task.
Earliest-finishing task completes→Resources are released→Task progress is updated→Latest-finishing task is accelerated
Simulation setup
Seven Experiments, 50 Project Instances Each
Randomized Benchmark
All six parameters are randomly sampled within the ranges reported in Table 2.
One-Factor-at-a-Time Sensitivity
One parameter varies while the other five remain fixed.
Number of TasksRequired SkillsAvailable ResourcesPredecessors / SuccessorsTask DurationResources per Skill
Benchmark: PSS is selected for its relevance and established use in project scheduling.
Experiment 1 · Random Projects
GPS Achieves a Lower Average Makespan and Reduces Resource Wastage
Interpretation: Lower free-resource levels indicate higher resource utilization. The paper also reports undefined “average completion gap” values of 9.80 days for GPS and 2.88 days for PSS; the direct mean difference is \(58.96-50.42=8.54\) days.
Sensitivity Results · Experiments 2 and 3
More Tasks Increase Both Makespans; More Required Skills Narrow the GPS Advantage
Sensitivity Results · Experiments 4 and 5
More Available Resources Benefit GPS; Graph Complexity Narrows the GPS–PSS Gap
Sensitivity Results · Experiments 6 and 7
Wider Task Durations Strengthen GPS; Higher Resource Demand Narrows Its Advantage
Synthesis of Experimental Evidence
GPS Gains Most When the Schedule Offers Reallocation Opportunities
Advantage Expands When…
- More resources are available.
- Fewer skills are required per task.
- Fewer resources are required per skill.
- Graph complexity is lower.
- Task-duration ranges are wider.
Available Flexibility
↓
GPS
Reallocation
↓
Lower Makespan
Advantage Narrows When…
- Fewer resources are available.
- More skills are required per task.
- More resources are required per skill.
- Graph complexity is higher.
- Task durations are more similar.
Critical Assessment
Promising Simulation Results, but Validation Remains Limited
Problem–Method Alignment
Weighted best fit and event-driven resource reuse directly target the two gaps identified by the authors.
Systematic Sensitivity Analysis
Six sensitivity experiments explain the conditions under which the advantage expands or contracts.
Simulation-Based Validation Only
No industrial case study or real-world project dataset is reported.
Limited Benchmark Breadth
GPS is primarily compared with PSS, so superiority over broader exact, heuristic, and metaheuristic baselines is not established.
Model Simplifications
The evaluated model excludes uncertainty, dynamic skill changes, preemption, and several operational constraints. No formal computational-complexity analysis is provided.
Notation and Reporting Ambiguities
Several definitions, formulas, algorithm lines, and figure references require careful interpretation, as noted earlier.
Conclusion
Use Proficiency. Preserve Parallelism. Reuse Capacity
GPS combines greedy best-fit allocation with parallel scheduling and repeatedly reallocates surplus or newly released resources to reduce project makespan.
Heterogeneous skill weights represent differences in resource proficiency instead of treating qualified resources as interchangeable.
The main operational gain comes from reallocating resources released as parallel tasks finish at different times.
Across all reported sensitivity settings, GPS achieves a lower makespan than PSS.
Author-Stated Future WorkExtend resource allocation with additional factors and constraints, and further improve the GPS method.
G09Group G09 · Project Control
Questions & Discussion
Ghazal Zolfi Moselo·MohammadMahdi Montazeri Hedesh
DOI 10.1109/ACCESS.2024.3350440 Open paper ↗