Job Shop scheduling - Branch and bound

6 important questions on Job Shop scheduling - Branch and bound

When is a schedule active?

A schedule is active if no operation can be scheduled earlier without delaying another operation.  

What does the set of all active schedules contain?

An optimal schedule

What does this represent and give the formula

The time it would finish if the job is added to the schedule. Earliest possible completion time.
  • Higher grades + faster learning
  • Never study anything twice
  • 100% sure, 100% understanding
Discover Study Smart

What happens with disjunctions when applying branching?

Each node in the branch and bound tree is characterized by a set D' of fixed disjunctions.

How do you calculate a simple lower bound of node v with their fixed disjunction D' ?

Calculation of the critical path (longest route) to node v

How can you find a better lower bound?

  • Considering one machine i that needs to be scheduled;
  • All unscheduled operations on the other machines can be done in parallel, but unscheduled operation on machine I needs to be sequenced;
  • Solve optimally

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