Introduction

When a combinatorial problem is too hard to solve exactly, practitioners reach for metaheuristics — general strategies that trade the guarantee of optimality for the practical ability to find very good solutions quickly. Most metaheuristics come with tuning knobs, populations, or memory structures that require significant engineering. GRASP is the refreshing exception.

Greedy Randomized Adaptive Search Procedures were introduced by Feo and Resende in 1989 and formally published in 1995. The idea is almost embarrassingly simple: build a candidate solution from scratch using a greedy-randomized rule, then improve it with local search, and repeat until a time or iteration budget runs out. Keep the best solution seen across all repetitions.

That two-step loop — construct, then improve — sounds too plain to be competitive. Yet GRASP consistently outperforms pure greedy heuristics, matches or beats many more elaborate metaheuristics on a wide range of scheduling and set-cover problems, and requires almost no problem-specific tuning. Its secret is the construction phase: rather than always making the single best greedy choice, GRASP assembles a restricted candidate list (RCL) of the top-α\alpha% of available moves and picks one at random. That tiny dose of randomness produces diversity across iterations without the overhead of maintaining a population.

GRASP belongs to the broader family of approximation and heuristic methods that attack NP-hard optimization problems. It has been applied successfully to hundreds of problem classes, from vehicle routing and job scheduling to network design and bioinformatics.

GRASP vs. Greedy

Below is a job-scheduling problem: assign 8 jobs to 3 machines to minimize the makespan (the finish time of the last machine). Greedy always assigns each job to the currently least-loaded machine — it never looks back. GRASP does the same thing, but during construction it randomly picks from the best 40 % of available jobs rather than always the very best one, then applies a local-search swap pass to polish the result.

<p class="hint">Assign 8 jobs (durations shown) to 3 machines to minimize the <b>makespan</b> — the time the last machine finishes. Greedy (LPT rule) always picks the least-loaded machine. GRASP adds randomness during construction and polishes with local search.</p>
<div class="controls">
  <button id="btn-greedy" type="button">Run Greedy</button>
  <button id="btn-grasp" type="button">Run GRASP (×20)</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="results" class="results hidden">
  <div class="result-row">
    <span class="label greedy-label">Greedy makespan</span>
    <span id="greedy-span" class="val">—</span>
  </div>
  <div class="result-row">
    <span class="label grasp-label">GRASP best makespan</span>
    <span id="grasp-span" class="val">—</span>
  </div>
  <div class="result-row gap-row">
    <span class="label">Improvement</span>
    <span id="gap-span" class="val gap">—</span>
  </div>
</div>
<div id="chart" class="chart"></div>
<p id="log" class="log"></p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .9rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.results { margin-bottom: .8rem; }
.results.hidden { display: none; }
.result-row { display: flex; align-items: center; gap: .6rem; margin: .25rem 0; font-size: .9rem; }
.label { min-width: 160px; color: #555; }
.val { font-weight: 700; font-size: 1rem; }
.gap { color: #0a7d33; }
.gap-row { margin-top: .3rem; }
.greedy-label::before { content: ""; display: inline-block; width: 10px; height: 10px; background: #adb1b8; border-radius: 2px; margin-right: 5px; }
.grasp-label::before { content: ""; display: inline-block; width: 10px; height: 10px; background: #1d3557; border-radius: 2px; margin-right: 5px; }
.chart { display: flex; flex-direction: column; gap: 6px; }
.machine-row { display: flex; align-items: center; gap: 6px; }
.machine-label { min-width: 24px; font-size: .78rem; color: #555; font-weight: 600; }
.bar-track { flex: 1; background: #eee; border-radius: 4px; height: 28px; position: relative; overflow: hidden; }
.bar-seg { position: absolute; top: 0; height: 100%; border-right: 2px solid #fff; display: flex; align-items: center; justify-content: center; font-size: .7rem; font-weight: 700; color: #fff; overflow: hidden; transition: all .35s; }
.bar-seg.greedy { background: #adb1b8; }
.bar-seg.grasp { background: #1d3557; }
.makespan-line { position: absolute; top: 0; height: 100%; border-right: 2.5px dashed #e63946; }
.log { font-size: .82rem; color: #555; margin-top: .6rem; min-height: 1.2em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Job scheduling: minimize makespan on 3 parallel machines.
// Greedy: assign each job (largest first, LPT rule) to least-loaded machine.
// GRASP: during construction pick randomly from the top-alpha fraction of
//        "best improvement" jobs; then swap-improve until no gain.
const JOBS = [7, 5, 5, 4, 4, 3, 3, 2]; // durations, pre-sorted desc; greedy=12, optimal=11
const M = 3;      // machines
const ALPHA = 0.4; // RCL fraction
const ITERS = 20;  // GRASP repetitions

function makespan(loads) { return Math.max(...loads); }

// Greedy: LPT — sort jobs descending, assign each to least-loaded machine
function runGreedy(jobs) {
  const sorted = [...jobs].sort((a, b) => b - a);
  const loads = Array(M).fill(0);
  const assign = Array(M).fill(null).map(() => []);
  for (const j of sorted) {
    const m = loads.indexOf(Math.min(...loads));
    loads[m] += j; assign[m].push(j);
  }
  return { loads, assign, ms: makespan(loads) };
}

// GRASP construction: RCL over jobs sorted by "how much they worsen makespan"
function graspConstruct(jobs) {
  const loads = Array(M).fill(0);
  const assign = Array(M).fill(null).map(() => []);
  const remaining = [...jobs];
  while (remaining.length) {
    // For each remaining job, best machine and cost = load after assignment
    const options = remaining.map(j => {
      const bestM = loads.indexOf(Math.min(...loads));
      return { j, bestM, cost: loads[bestM] + j };
    });
    options.sort((a, b) => a.cost - b.cost);
    const rcl = options.slice(0, Math.max(1, Math.ceil(options.length * ALPHA)));
    const pick = rcl[Math.floor(Math.random() * rcl.length)];
    loads[pick.bestM] += pick.j;
    assign[pick.bestM].push(pick.j);
    remaining.splice(remaining.indexOf(pick.j), 1);
  }
  return { loads, assign };
}

// Local search: try moving each job from its machine to another; accept if makespan falls
function localSearch(loads, assign) {
  loads = loads.slice(); assign = assign.map(a => [...a]);
  let improved = true;
  while (improved) {
    improved = false;
    for (let m1 = 0; m1 < M; m1++) {
      for (let idx = 0; idx < assign[m1].length; idx++) {
        const j = assign[m1][idx];
        for (let m2 = 0; m2 < M; m2++) {
          if (m2 === m1) continue;
          const newLoads = loads.slice();
          newLoads[m1] -= j; newLoads[m2] += j;
          if (makespan(newLoads) < makespan(loads)) {
            loads = newLoads;
            assign[m1] = assign[m1].filter((_, i) => i !== idx);
            assign[m2] = [...assign[m2], j];
            improved = true; break;
          }
        }
        if (improved) break;
      }
      if (improved) break;
    }
  }
  return { loads, assign, ms: makespan(loads) };
}

function runGrasp(jobs, iters) {
  let best = null;
  for (let i = 0; i < iters; i++) {
    const { loads, assign } = graspConstruct(jobs);
    const result = localSearch(loads, assign);
    if (!best || result.ms < best.ms) best = result;
  }
  return best;
}

// ── Rendering ──────────────────────────────────────────────────────────────
let greedyResult = null, graspResult = null;

function renderChart(gResult, spResult) {
  const chart = document.getElementById('chart');
  chart.innerHTML = '';
  const maxSpan = Math.max(gResult ? gResult.ms : 0, spResult ? spResult.ms : 0, 1);

  for (let m = 0; m < M; m++) {
    const row = document.createElement('div'); row.className = 'machine-row';
    const lbl = document.createElement('div'); lbl.className = 'machine-label'; lbl.textContent = 'M' + (m+1);
    row.appendChild(lbl);

    // greedy bar
    if (gResult) {
      const track = document.createElement('div'); track.className = 'bar-track';
      let offset = 0;
      for (const j of (gResult.assign[m] || [])) {
        const seg = document.createElement('div'); seg.className = 'bar-seg greedy';
        const w = (j / maxSpan) * 100;
        seg.style.left = (offset / maxSpan * 100) + '%'; seg.style.width = w + '%';
        seg.textContent = j; offset += j; track.appendChild(seg);
      }
      // makespan line for greedy machine at total load
      if (spResult) {
        const ml = document.createElement('div'); ml.className = 'makespan-line';
        ml.style.left = (gResult.ms / maxSpan * 100) + '%'; track.appendChild(ml);
      }
      row.appendChild(track);
    }

    // grasp bar
    if (spResult) {
      const track2 = document.createElement('div'); track2.className = 'bar-track';
      let offset2 = 0;
      for (const j of (spResult.assign[m] || [])) {
        const seg = document.createElement('div'); seg.className = 'bar-seg grasp';
        const w = (j / maxSpan) * 100;
        seg.style.left = (offset2 / maxSpan * 100) + '%'; seg.style.width = w + '%';
        seg.textContent = j; offset2 += j; track2.appendChild(seg);
      }
      row.appendChild(track2);
    }
    chart.appendChild(row);
  }
}

function updateResults() {
  const res = document.getElementById('results');
  const gs = document.getElementById('greedy-span');
  const sp = document.getElementById('grasp-span');
  const gap = document.getElementById('gap-span');
  if (!greedyResult && !graspResult) { res.classList.add('hidden'); return; }
  res.classList.remove('hidden');
  if (greedyResult) gs.textContent = greedyResult.ms;
  if (graspResult)  sp.textContent = graspResult.ms;
  if (greedyResult && graspResult) {
    const diff = greedyResult.ms - graspResult.ms;
    gap.textContent = diff > 0 ? fmt('−%diff% (GRASP better)', { diff: diff }) : diff === 0 ? 'Tied' : fmt('+%abs% (Greedy better)', { abs: Math.abs(diff) });
    gap.style.color = diff > 0 ? '#0a7d33' : diff === 0 ? '#555' : '#e63946';
  }
}

document.getElementById('btn-greedy').addEventListener('click', () => {
  greedyResult = runGreedy(JOBS);
  updateResults(); renderChart(greedyResult, graspResult);
  document.getElementById('log').textContent =
    fmt('Greedy (LPT): machine loads = [%loads%], makespan = %ms%.', { loads: greedyResult.loads.join(', '), ms: greedyResult.ms });
  console.assert(greedyResult.ms === 12, fmt('Greedy makespan should be 12, got %ms%', { ms: greedyResult.ms }));
});

document.getElementById('btn-grasp').addEventListener('click', () => {
  graspResult = runGrasp(JOBS, ITERS);
  updateResults(); renderChart(greedyResult, graspResult);
  document.getElementById('log').textContent =
    fmt('GRASP (×%ITERS%): best makespan = %ms% — loads = [%loads%].', { ITERS: ITERS, ms: graspResult.ms, loads: graspResult.loads.join(', ') });
});

document.getElementById('btn-reset').addEventListener('click', () => {
  greedyResult = null; graspResult = null;
  updateResults(); renderChart(null, null);
  document.getElementById('log').textContent = '';
});
Result
Console

Click Run Greedy to see the deterministic result. Click Run GRASP (×20) to run 20 independent GRASP iterations and keep the best. Notice how GRASP consistently finds a shorter or equal makespan — and that the best-of-20 gap over pure greedy grows the more you click.

The Real Complexity

GRASP is a heuristic, not an exact algorithm, so it carries no approximation ratio guarantee in general. What makes it interesting is the interaction between its two phases:

Construction phase. At each step, the algorithm evaluates all remaining elements by a greedy criterion (e.g., the job whose addition increases makespan the least). It places the top-α\alpha% in the Restricted Candidate List (RCL) and picks one uniformly at random. Setting α=0\alpha = 0 gives pure greedy; α=1\alpha = 1 gives a purely random construction. The key insight is that moderate α\alpha values (often 0.2–0.4 in practice) inject enough diversity to escape greedy's local traps without sacrificing too much construction quality.

Local search phase. After construction, GRASP runs a local improvement procedure — typically swapping two elements or moving one element to a different position — until no single move reduces cost. This is equivalent to finding a local optimum in the neighborhood structure. Because construction already produces a reasonable starting point, local search converges quickly.

Why it works. Each GRASP iteration produces an independent local optimum from a different starting point. The probability that the global optimum lies in the basin of attraction of at least one starting point grows with the number of iterations. Probabilistic analysis by Feo, Resende, and others shows that under mild conditions, the expected solution quality converges to the optimum as iterations →∞\to \infty.

No tuning, no memory. Unlike simulated annealing (which has a cooling schedule) or tabu search (which maintains a forbidden-moves list), GRASP has essentially one parameter: α\alpha. There is no population to manage, no pheromone matrix to update, no crossover operator to design. This simplicity makes GRASP an ideal baseline before investing in more complex methods.

The underlying scheduling and routing problems GRASP is applied to are typically NP-hard, so no polynomial-time exact algorithm is known unless P = NP.

Where It Matters

GRASP's generality has led to successful applications across an unusually wide range of domains:

  • Job and machine scheduling: minimizing makespan or total weighted completion time on parallel machines — problems where greedy alone misses interactions between jobs.
  • Vehicle routing: assigning delivery routes to vehicles to minimize total distance, a classic NP-hard problem with huge economic impact.
  • Network design: selecting edges to connect nodes under cost or reliability constraints, crucial for telecommunications and supply chains.
  • Set cover and facility location: choosing the smallest subset of facilities that covers all demand points.
  • Bioinformatics: sequence alignment, phylogenetic tree construction, and protein structure prediction all benefit from GRASP's ability to explore diverse local optima.
  • VLSI placement and routing: arranging transistors on a chip so that wire lengths are minimized.

Because GRASP is so easy to implement, it is often the first metaheuristic tried on a new problem. If it performs well, the search stops. If not, the GRASP solution serves as a benchmark for evaluating more complex methods. In competitive operations-research contexts, GRASP solutions seeded into hybrid algorithms — combining GRASP construction with exact branch-and-bound or genetic crossover — routinely reach state-of-the-art results.

Conclusion

GRASP is a masterclass in the power of simplicity. Its two-step loop — build greedily with a random twist, then improve locally — needs almost no tuning, applies to virtually any combinatorial problem, and consistently outperforms the deterministic greedy heuristics that practitioners reach for first.

The key insight is that diversity during construction is cheap and effective. A small random element in an otherwise greedy procedure is enough to explore a wide region of the solution space across iterations, while local search guarantees that each iteration ends at a high-quality local optimum rather than wherever the random walk happened to stop.

If you ever need to attack a scheduling, routing, or assignment problem and lack the time to engineer a specialized solver, GRASP is where to start. It will almost certainly beat pure greedy, and it might save you from needing anything more elaborate at all. The underlying problems remain NP-hard — GRASP does not change that — but it narrows the practical gap between what we can compute and what we wish we could.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/grasp/Content licensed under CC BY-NC 4.0.