HKSM

A structured search technique that evaluates many scheduling choices while using bounds to discard options that cannot outperform the current best. It helps identify the optimal or best-available sequence or resource assignment under constraints when the option space is large.

Key Points

• Builds a search tree of decisions (e.g., sequence, resource assignment, crashing choices) and explores it systematically.
• Uses bounds (best-case estimates) to prune branches that cannot lead to a better schedule than the current best.
• Well-suited for complex, constrained scheduling problems where simple heuristics are unreliable.
• Can yield an optimal answer if allowed to run to completion, or a high-quality answer within a defined time limit.
• Relies on a clear objective (e.g., minimize finish date, lateness, or cost) and strict feasibility checks.
• Often implemented with solver tools or custom scripts integrated with the schedule model.

Purpose of Analysis

Support schedule control by selecting the best corrective or preventive action among many feasible alternatives. Typical goals include minimizing total duration, meeting a milestone date, or reducing late penalties while respecting precedence and resource limits.

• Compare resequencing options after slippage.
• Evaluate resource reassignments and leveling choices.
• Select cost-effective crashing or overtime combinations.
• Assess what-if scenarios to satisfy deadline or WIP constraints.

Method Steps

• Define objective and constraints: choose the metric to optimize (e.g., earliest project finish) and list all precedence, resource, calendar, and policy limits.
• Create an initial feasible solution, often using a heuristic (e.g., critical path with simple leveling) to set an initial best value (incumbent).
• Branch on a decision variable: next activity to schedule, resource assignment, mode/duration choice, or crashing option.
• Compute a bound for each partial solution using fast estimates such as critical-path lower bounds, resource feasibility checks, and minimal additional cost/duration.
• Prune any branch whose bound is worse than the incumbent; expand promising branches first (best-first) or use depth-first with backtracking.
• Update the incumbent whenever a better complete schedule is found.
• Stop when the tree is exhausted or a time/effort limit is reached; extract the best schedule and implementation actions.

Inputs Needed

• Activity list with durations, precedence, and constraints (FS/SS/FF/Lags).
• Resource availability, skills, calendars, and assignment limits.
• Crashing modes, overtime rules, and related costs if optimizing time-cost trade-offs.
• Milestones, deadlines, penalties, and key performance targets.
• Current schedule status, actuals, and variances versus baseline.
• Risk or uncertainty ranges if bounds incorporate conservative or optimistic estimates.
• Scheduling tool or solver capable of representing decisions and evaluating bounds.

Outputs Produced

• Recommended schedule revision with defined sequencing, assignments, and any crashing/overtime choices.
• Objective value for the selected plan (e.g., new finish date or penalty cost) and gap to theoretical bound.
• Shortlist of pruned alternatives with reasons, supporting transparent decision-making.
• Change requests for approved adjustments to dates, resources, or budgets.
• Updated schedule data, forecasts, and related performance metrics.

Interpretation Tips

• Quality of bounds drives efficiency; tighter bounds prune more branches and speed decisions.
• If time-boxed, treat the result as near-optimal and communicate residual risk or potential improvement.
• Validate that the model includes real-world constraints such as calendars, resource skills, and policy limits.
• Stress-test the chosen schedule with what-if checks to ensure robustness to minor delays.
• Align the optimization objective with stakeholder priorities; the “best” plan is objective-specific.

Example

A construction project slips two days due to weather. The team must meet a critical handover in three weeks with one crane and limited weekend overtime.

The scheduler models decisions for resequencing crane-dependent tasks and optional weekend work. Using branch and bound, the tool branches on task order and overtime choices, applies critical-path lower bounds, and prunes infeasible or dominated options. It identifies a plan that restores the handover date by shifting two noncritical lifts and adding one overtime shift, with minimal added cost.

Pitfalls

• Using weak or unrealistic bounds that lead to excessive computation and delayed decisions.
• Optimizing a narrow objective (e.g., duration) while ignoring side effects like cost or risk exposure.
• Modeling errors in calendars, resource limits, or precedence that produce infeasible “optimal” plans.
• Over-reliance on deterministic durations without sensitivity checks in volatile environments.
• Applying the technique to trivial problems where simpler heuristics would be faster and sufficient.

PMP Example Question

While evaluating multiple corrective actions to recover a slipped milestone, the team wants a systematic way to eliminate schedule options that cannot beat the current best plan based on optimistic bounds. Which technique should they use?

1. Monte Carlo simulation.
2. Branch and bound.
3. Rolling wave planning.
4. Kanban work-in-progress limits.

Correct Answer: B — Branch and bound.

Explanation: Branch and bound uses bounds to prune inferior alternatives while searching for the best schedule under constraints. The other options do not perform this type of optimality-based pruning.