Constructive heuristics - Greedy approach

10 important questions on Constructive heuristics - Greedy approach

Explain shortly the goal of the greedy approach

A fast strategy to find a feasible solution that is mostly not optimal.

What are [2] things needed when executing the greedy approach?

  • Building blocks
  • dispatching rules

Explain the overall strategy of the greedy approach

Incremental approach selecting one building block at the time. Building blocks are selected based on a priority function that yields the greatest improvement in which no backtracking is allowed.
  • Higher grades + faster learning
  • Never study anything twice
  • 100% sure, 100% understanding
Discover Study Smart

Selecting building blocks for the greedy approach is done in 2 steps, explain the 2 steps

  • Variable selection | Which variable is added;
  • Value selection | Which value assign to the variable;

What is [2] different naming for dispatching rules?

  • Priority rules
  • Scheduling rules

What is the function of dispatching rules?

Determines the variable selection based on some priority measure.

What is an optimal dispatching rule used for sequencing (machines)?

The smiths rule
Weighted shortest processing time first dispatching rule

Explain the smith rule and give the formula

Sort the jobs in decreasing order, decreasing priority.

What kind of problem is the parallel machine problem?

  • Combinatorial optimization problem;
  • NP-hard problem;

What is a dispatching rule for the parallel machine problem?

List scheduling problem
Objective to minimize the completion time.

The question on the page originate from the summary of the following study material:

  • A unique study and practice tool
  • Never study anything twice again
  • Get the grades you hope for
  • 100% sure, 100% understanding
Remember faster, study better. Scientifically proven.
Trustpilot Logo