Optimal Branch and Bound Example Overview
This example demonstrates the Branch and Bound algorithm applied to job scheduling to find optimal preemptive schedules with lower and upper bounds on lateness. Starting with initial lower and upper bounds, nodes are explored to find the best schedules for different job sequences.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Initial lower bound J r p d 1 0 4 8 2 1 2 12 3 3 6 11 4 5 5 10 Use 1 machine preemptive schedule as lower bound Job 2 has a lateness of 5, this is a lower bound on Lmax J1 J3 J4 J3 J2 10 5 4 17 15
Initial upper bound J r p d 1 0 4 8 2 1 2 12 3 3 6 11 4 5 5 10 Find some schedule. Lmax is 7. J3 J4 J1 J2 12 6 4 17
Branch on First job Lower bound 5 Upper bound 7 *,*,*,* 4,*,*,* 1,*,*,* 3,*,*,* 2,*,*,* Pick one node to explore. Let s choose the one with 2 first
Optimal Preemptive Schedule with job 2 first J r p d 1 0 4 8 2 1 2 12 3 3 6 11 4 5 5 10 Best preemptive schedule with J2 first has Lmax of 7. The schedule is also non-preemptive, so we have upper and lower Bounds of 7 J3 J4 J1 J2 3 12 1 7 18
Explored node 2 Lower bound 5 Upper bound 7 *,*,*,* 4,*,*,* 1,*,*,* 3,*,*,* 2,*,*,* Lower bound 7 Upper bound 7 No need to explore this node further Pick another node to explore. Let s choose the one with 4 next
Optimal Preemptive Schedule with job 4 first J r p d 1 0 4 8 2 1 2 12 3 3 6 11 4 5 5 10 Best preemptive schedule with J4 first has Lmax of 9. The schedule is also non-preemptive, so we have upper and lower Bounds of 9. The lower bound of 9 means that we should PRUNE J1 J4 J3 J2 5 10 14 20 22
Explored node 4 Lower bound 5 Upper bound 7 *,*,*,* 4,*,*,* 1,*,*,* 3,*,*,* 2,*,*,* Lower bound 9 Upper bound 9 Lower bound 7 Upper bound 7 Pick one node to explore. Let s choose the one with 1 next We already know that the lower bound is 5 and is preemptive.
Exploring node 1 1,*,*,* 1,2,*,* 1,4,*,* 1,3,*,* .
Optimal Preemptive Schedule with job 1 and 2 first J r p d 1 0 4 8 2 1 2 12 3 3 6 11 4 5 5 10 Best preemptive schedule with J1, J2 first, has Lmax of 6 and Is non-preemptive J4 J3 J1 J2 4 6 11 17
Exploring node 1,2 1,*,*,* 1,2,*,* 1,4,*,* 1,3,*,* Lower bound 6 Upper bound 6 No need to explore further let s try node 1,3 next
Optimal Preemptive Schedule with job 1 and 3 first J r p d 1 0 4 8 2 1 2 12 3 3 6 11 4 5 5 10 Best preemptive schedule with J1, J3 first, has Lmax of 5 and Is non-preemptive J2 J4 J1 J3 4 10 15 17
Exploring node 1,3 1,*,*,* 1,2,*,* 1,4,*,* 1,3,*,* Lower bound 6 Upper bound 6 Lower bound 5 Upper bound 5 We have found a schedule that matches the global lower bound and are done!
summary Lower bound 5 Upper bound 7 *,*,*,* 4,*,*,* 1,*,*,* 3,*,*,* 2,*,*,* Lower bound 9 Upper bound 9 Lower bound 7 Upper bound 7 . 1,3,*,* 1,2,*,* 1,4,*,* Lower bound 5 Upper bound 5 Lower bound 6 Upper bound 6
