Context
RCPSP, MSRCPSP, research gap and contribution.
IEEE Access · Volume 12 · 2024
Weighted Multi-Skill
Project Scheduling
A Greedy and Parallel Scheduling approach for reducing project makespan through proficiency-aware assignment, parallel task groups, and active reuse of free resources.
Presented by
Ghazal Zolfi Moselo
·
MohammadMahdi Montazeri Hedesh
Course Instructor
Prof. Mohsen VarmazyarPresentation roadmap
From the scheduling problem to the evidence.
Model
Task graph, weighted skills, notation, objective and constraints.
Method
Five coordinated algorithms in the GPS scheduling loop.
Evidence
Seven simulation experiments against the PSS benchmark.
Assessment
Interpretation, limitations, future work and takeaways.
Problem evolution
From scarce resources to weighted human capability.
The paper studies software projects in which activities are linked by precedence, people possess several skills, and proficiency differs by person and skill.
Resources + precedence
Schedule activities under renewable resource limits and dependency constraints.
Skills enter the model
Every task requires skills; every human resource masters one or more skills.
Proficiency is weighted
Skill proficiency is heterogeneous and represented by values in the interval \([0,1]\).
Related work and gap
Existing approaches solve parts of the problem, but leave two practical gaps.
MILP and mathematical programming
Can model multiple objectives and constraints, but become computationally demanding as problem size grows.
Priority and schedule-generation rules
Produce solutions quickly, but do not guarantee optimality and often simplify resource capability.
GA, PSO, VNS and related search
Explore large search spaces, yet many studies assume homogeneous proficiency or limited collaboration.
UncertaintyProject costMulti-project schedulingEmployee additionSkill switchingSoft skillsMultitaskingDynamic availabilityCollaboration
Gap 01Heterogeneous proficiency is often overlooked.
Gap 02Resources freed by unequal task durations may remain underused.
Research objective and contribution
Minimize makespan by making resource availability more intelligent.
Greedy best fit
Select the available resource with the highest matching skill proficiency.
Parallel task groups
Partition the precedence graph into dependency-safe subsets that can execute concurrently.
Surplus allocation
Assign spare resources to the latest-finishing scheduled task to reduce its finish time.
Freed-resource reuse
When the earliest task finishes, redirect its resources to remaining tasks in the same group.
Central claimBetter proficiency matching + less idle capacity = shorter project duration.
Problem setup
The project is a task precedence graph with dummy start and end nodes.
Tasks inside the same parallel subset have no precedence relation with one another.
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
Two matrices connect task demand to heterogeneous capability.
TS
Task–Skill Matrix
\[TS=\begin{bmatrix}1&0&1\\0&1&1\\1&0&0\end{bmatrix}\]
\(t_i s_j\in\{0,1\}\)
A value of \(1\) means task \(t_i\) requires skill \(s_j\).
matched through\(w_{r_k s_l t_i}\)binary assignment decision
RS
Resource–Skill Matrix
\[RS=\begin{bmatrix}0.9&0.2&0.7\\0.4&1.0&0.6\\0.8&0.5&0.3\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}\]
Illustrative feasible match: if \(t_1\) requires \(s_1\) and \(w_{r_2s_1}=0.9\), then \(w_{r_2s_1t_1}=1\) records the assignment.
Mathematical formulation · objective and constraints (2)–(4)
Finish the dummy end task as early as possible.
The start time of the dummy end node represents project completion.
\[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 assignment satisfies the required headcount 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\]
At least one resource performs every project task; the published qualifier is typographically ambiguous.
\[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}\]
Published notation is ambiguous; the prose intends assigned resources to possess skills required by the task.
\[F_{t_i}=B_{t_i}+d_{t_i},\qquad \forall t_i\in T\]
Finish time equals start time plus duration.
Notation verification
Three paper-level inconsistencies are explicitly controlled in this presentation.
\(d_{t_i}\): duration, not deadline
The problem-formulation paragraph calls \(d_{t_i}\) a deadline, but Table 1, Equations (2), (7), (9), and the algorithm discussion use it as task duration. The slides use “duration.”
Constraint wording is separated from formula scope
Constraint (4) directly limits one skill contribution per resource for a given task. The broader “one task at a time” claim appears in prose and is not overstated as a standalone mathematical guarantee.
Figure references are corrected by captions
The results prose points to Figures 7 and 8 for Experiments 6 and 7. Their actual captions are Figure 8 (duration) and Figure 9 (resource demand), which this presentation follows.
GPS framework
Five algorithms form one event-driven scheduling loop.
GPS
Orchestrate groups
Create groups
Extract independent tasks
Schedule subset
Advance by completion events
Assign resources
Choose maximum proficiency
Assign surplus
Accelerate latest finisher
Best-fit choiceHighest matching proficiency
Release eventEarliest-finishing task completes
Surplus targetLatest-finishing scheduled task
Algorithm 1 · Top-level orchestrator
GPS builds parallel groups, schedules each group, and accumulates makespan.
- Create the array of dependency-safe task groups.
- Ignore groups containing dummy start or end tasks.
- Sort tasks in a group by finishing time.
- Call the subset scheduler and add its elapsed time.
Input \(T,S,R,E\)Output \(\mathrm{project\_makespan}\)
Algorithm 2 · CreateParallelTasksGroups
Repeatedly extract vertices with no remaining predecessor.
- Scan the remaining task set.
- Select vertices that are not the right vertex of any remaining edge.
- Place them in the current parallel subset.
- Remove selected vertices and outgoing edges; repeat.
Input \(T,E\)Output \(T_{\parallel}[\,]\)
Algorithm 3 · ScheduleTasksSubset
The scheduler advances from one earliest-finish event to the next.
- Attempt an initial feasible assignment for unscheduled tasks.
- Use Algorithm 5 to place surplus capacity.
- Find the earliest-finishing task and release its resources.
- Update remaining effort and elapsed time for running tasks.
Input \(T_{\parallel},R_{\mathrm{avail}}\)Output \(C_{T_{\parallel}}\)
Algorithm 4 · AssignResources
For each required skill, greedily choose the available resource with maximum proficiency.
- Visit every skill required by the task.
- Find the highest-weight available matching resource.
- Update task-skill finishing time after each assignment.
- Stop when the task can finish within \(d_{t_i}\); roll back if no match exists.
Input \(t_i,R_{\mathrm{avail}}\)Output \(\mathrm{Boolean}\)
Algorithm 5 · AssignExtraResources
Use spare capacity where it can reduce the group completion time most.
- Remove tasks that received no initial assignment.
- Select the latest-finishing scheduled task.
- Select that task’s latest-finishing skill.
- Assign any free resource possessing that skill; repeat.
Input \(T_{\parallel},R_{\mathrm{avail}}\)Output surplus assignments
Notation noteLines 9 and 17 appear to reuse the latest-finishing task selected in line 8. This is presented as an apparent ambiguity, not as a correction to the paper.
Why GPS can shorten a parallel group
Completion events continuously reshape resource allocation.
Initial allocation
Task ATask BTask C
A finishes first; its assigned resources become available.
Reallocate→
After resource release
Task A ✓Task B + RTask C + R
Freed and surplus resources are redirected to reduce the latest finish.
Earliest task completes→Resources released→Remaining effort updated→Latest finish reduced
Simulation setup
Seven experiments, 50 generated projects per experiment.
Random benchmark
All six factors are sampled within the reported ranges.
One-factor sensitivity
One factor varies while the other five remain fixed.
TasksSkillsResourcesGraph complexityDurationDemand per skill
Benchmark: Parallel Scheduling Scheme (PSS), selected by the authors for its relevance and established use.
Experiment 1 · Random projects
GPS reports a lower average makespan and fewer idle resources.
The paper separately reports “average completion gap” values of 9.80 days for GPS and 2.88 days for PSS without defining them as the direct difference. The headline comparison therefore uses \(58.96-50.42=8.54\) days.
Sensitivity results · Experiments 2 and 3
Task count preserves the pattern; higher skill demand narrows the advantage.
Sensitivity results · Experiments 4 and 5
More resources help GPS; denser precedence reduces parallel opportunity.
Sensitivity results · Experiments 6 and 7
Unequal durations create reuse opportunities; higher mandatory demand removes them.
Synthesis of experimental evidence
GPS is strongest when the schedule contains exploitable flexibility.
Advantage expands when…
- More resources are available.
- Each task requires fewer skills.
- Resource demand per task-skill is lower.
- Graph complexity leaves more parallel tasks.
- Task durations vary enough to release resources early.
Available flexibility→GPSreallocation→Lower makespan
Advantage narrows when…
- Skills consume most of the resource pool.
- Mandatory headcount leaves little surplus.
- Dense precedence relations suppress concurrency.
- Few resources become free before the group completes.
Critical assessment
Promising simulation evidence, with a bounded validation scope.
Mechanism matches the problem
Weighted best fit and event-driven resource reuse directly target the two gaps identified by the authors.
Factor-by-factor analysis
Six sensitivity experiments explain the conditions under which the advantage expands or contracts.
Simulation only
No industrial case study or real project dataset is reported.
Primary comparison is PSS
The study does not establish superiority against a broad set of contemporary exact and metaheuristic methods.
Model simplifications
Costs, uncertainty, skill evolution, switching, preemption and broader allocation constraints are outside the evaluated model. The paper also does not provide a formal computational-complexity analysis.
Notation and reporting ambiguity
Several formulas and result references need careful interpretation, as documented earlier in this presentation.
Conclusion
Use proficiency. Preserve parallelism. Reuse capacity.
GPS combines a greedy best-fit rule with parallel scheduling and repeatedly reassigns surplus or newly freed resources to reduce the latest finish time.
Heterogeneous skill weights produce more realistic resource selection than interchangeable-capacity assumptions.
The principal operational gain comes from keeping resources productive while parallel tasks finish at different times.
Across the reported simulations, GPS achieves a lower makespan than PSS in almost all tested settings.
Author-stated future workAdd more factors and constraints to resource allocation, 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 ↗