Let's solve the problem step by step using **branch-and-bound with jumptracking** to minimize the **sum of earliness (E) and tardiness (T)**. --- ### **Step 1: Problem Restatement** - There are **4 jobs**, each with a duration and due date. - We want to **sequence** the jobs on a single machine to **minimize total earliness plus tardiness**. - **Earliness (ei)** = max(0, due date - completion time) - **Tardiness (ti)** = max(0, completion time - due date) - For each job, only one of ei or ti can be positive. | Job | Duration | Due Date | |-----|----------|----------| | 1 | 12 | 22 | | 2 | 8 | 9 | | 3 | 9 | 39 | | 4 | 15 | 27 | --- ### **Step 2: Initial Lower Bound** #### **Calculate the earliest possible finish time for each job** - The lower bound for a node is the minimum possible sum of earliness and tardiness for the remaining jobs, assuming they are scheduled in the best possible way. - The best-case scenario is to schedule the jobs with the earliest due date first (EDD rule), which is optimal for minimizing maximum lateness, but not always for earliness + tardiness. #### **EDD Order** Due Dates: 9 (Job 2), 22 (Job 1), 27 (Job 4), 39 (Job 3) Let’s try EDD: **2, 1, 4, 3** #### **Calculate Completion Times** - Job 2: 8 (ends at 8) - Job 1: 8+12=20 (ends at 20) - Job 4: 20+15=35 (ends at 35) - Job 3: 35+9=44 (ends at 44) #### **Calculate Earliness and Tardiness** - Job 2: Done at 8, due at 9 → **e=1, t=0** - Job 1: Done at 20, due at 22 → **e=2, t=0** - Job 4: Done at 35, due at 27 → **e=0, t=8** - Job 3: Done at 44, due at 39 → **e=0, t=5** **Sum (E+T) = 1+2+8+5 = 16** --- ### **Step 3: B&B Tree Initialization** - Root node: all jobs unscheduled. - Explore each job as the first scheduled job, then branch further. #### **Level 1 (t=1): Pick first job** - Try all 4 jobs as first: ##### **Node [1, -,-,-]** - Time: 12 - Remaining: 2,3,4 ##### **Node [2, -,-,-]** - Time: 8 - Remaining: 1,3,4 ##### **Node [3, -,-,-]** - Time: 9 - Remaining: 1,2,4 ##### **Node [4, -,-,-]** - Time: 15 - Remaining: 1,2,3 --- ### **Step 4: Calculate Lower Bounds for Each Node** #### **Node [1, -,-,-]:** - Job 1 finishes at 12 (due 22): e=10, t=0 - Remaining: 2,3,4; time=12 - EDD for remaining: 2 (due 9), 4 (27), 3 (39) - Schedule: 2 (12+8=20), 4 (20+15=35), 3 (35+9=44) - Job 2: 20, due 9 → e=0, t=11 - Job 4: 35, due 27 → e=0, t=8 - Job 3: 44, due 39 → e=0, t=5 Total: e=10, t=24 **Bound: 34** --- #### **Node [2, -,-,-]:** - Job 2 finishes at 8 (due 9): e=1, t=0 - Remaining: 1,3,4; time=8 - EDD: 1 (22), 4 (27), 3 (39) - Schedule: 1 (8+12=20), 4 (20+15=35), 3 (35+9=44) - Job 1: 20, due 22 → e=2, t=0 - Job 4: 35, due 27 → e=0, t=8 - Job 3: 44, due 39 → e=0, t=5 Total: e=3, t=13 **Bound: 16** (matches EDD order above!) --- #### **Node [3, -,-,-]:** - Job 3 finishes at 9 (due 39): e=30, t=0 - Remaining: 1,2,4; time=9 - EDD: 2 (9), 1 (22), 4 (27) - Schedule: 2 (9+8=17), 1 (17+12=29), 4 (29+15=44) - Job 2: 17, due 9 → e=0, t=8 - Job 1: 29, due 22 → e=0, t=7 - Job 4: 44, due 27 → e=0, t=17 Total: e=30, t=32 **Bound: 62** --- #### **Node [4, -,-,-]:** - Job 4 finishes at 15 (due 27): e=12, t=0 - Remaining: 1,2,3; time=15 - EDD: 2 (9), 1 (22), 3 (39) - Schedule: 2 (15+8=23), 1 (23+12=35), 3 (35+9=44) - Job 2: 23, due 9 → e=0, t=14 - Job 1: 35, due 22 → e=0, t=13 - Job 3: 44, due 39 → e=0, t=5 Total: e=12, t=32 **Bound: 44** --- ### **Step 5: Branch Further from Best Node ([2, -,-,-])** - Current **best upper bound = 16** (EDD order) - We'll branch from [2, -,-,-] (lowest lower bound). #### **Level 2: [2, 1, -,-]** - Time: 8+12=20 - Remaining: 3,4 - Try [2,1,3,4]: - 3: 20+9=29; 4: 29+15=44 - Job 3: 29, due 39 → e=10, t=0 - Job 4: 44, due 27 → e=0, t=17 - Job 1: 20, due 22 → e=2, t=0 - Job 2: 8, due 9 → e=1, t=0 - Total: e=13, t=17 = **30** - Try [2,1,4,3]: - 4: 20+15=35; 3: 35+9=44 - Job 4: 35, due 27 → e=0, t=8 - Job 3: 44, due 39 → e=0, t=5 - Job 1: 20, due 22 → e=2, t=0 - Job 2: 8, due 9 → e=1, t=0 - Total: e=3, t=13 = **16** (matches EDD) #### **Level 2: [2,4, -,-]** - Time: 8+15=23 - Remaining: 1,3 - Try [2,4,1,3]: - 1: 23+12=35; 3: 35+9=44 - Job 1: 35, due 22 → e=0, t=13 - Job 3: 44, due 39 → e=0, t=5 - Job 4: 23, due 27 → e=4, t=0 - Job 2: 8, due 9 → e=1, t=0 - Total: e=5, t=18 = **23** - Try [2,4,3,1]: - 3: 23+9=32; 1: 32+12=44 - Job 3: 32, due 39 → e=7, t=0 - Job 1: 44, due 22 → e=0, t=22 - Job 4: 23, due 27 → e=4, t=0 - Job 2: 8, due 9 → e=1, t=0 - Total: e=12, t=22 = **34** #### **Level 2: [2,3,-,-]** - Time: 8+9=17 - Remaining: 1,4 - Try [2,3,1,4]: - 1: 17+12=29; 4: 29+15=44 - Job 1: 29, due 22 → e=0, t=7 - Job 4: 44, due 27 → e=0, t=17 - Job 3: 17, due 39 → e=22, t=0 - Job 2: 8, due 9 → e=1, t=0 - Total: e=23, t=24 = **47** - Try [2,3,4,1]: - 4: 17+15=32; 1: 32+12=44 - Job 4: 32, due 27 → e=0, t=5 - Job 1: 44, due 22 → e=0, t=22 - Job 3: 17, due 39 → e=22, t=0 - Job 2: 8, due 9 → e=1, t=0 - Total: e=23, t=27 = **50** --- ### **Summary Table of Candidate Solutions (E+T):** | Order | E+T | |-------------|-----| | 2,1,3,4 | 30 | | 2,1,4,3 | 16 | | 2,4,1,3 | 23 | | 2,4,3,1 | 34 | | 2,3,1,4 | 47 | | 2,3,4,1 | 50 | ### **Other branches ([1, -,-,-], [3,-,-,-], [4,-,-,-]) have higher bounds and can be pruned.** --- ### **Step 6: Final Answer** The **optimal sequence** is **[2, 1, 4, 3]**, with a **minimum sum of earliness and tardiness = 16**. --- ### **Summary Table with Details** | Job | Completion | Due Date | Earliness | Tardiness | |-----|------------|----------|-----------|-----------| | 2 | 8 | 9 | 1 | 0 | | 1 | 20 | 22 | 2 | 0 | | 4 | 35 | 27 | 0 | 8 | | 3 | 44 | 39 | 0 | 5 | |**Sum**| | | **3** | **13** | --- ## **Final Answer** > **The optimal sequence is [2, 1, 4, 3], with a minimum sum of earliness and tardiness of 16.** > > **Branch-and-bound tree:** Start from [2,-,-,-], then [2,1,-,-], [2,1,4,-], [2,1,4,3] (best solution found), other branches have higher lower bounds and are pruned (jumptracking applied). --- **If you need the full B&B tree illustration or further details, let me know!**