Consider the following 1 | r | E(C-1) problem instance. j 3 rj 7 P 6...

   

Transcribed Image Text:

Consider the following 1 | r | E(C-1) problem instance. j 3 rj 7 P 6 1 0 9 2 1 7 4 10 3 552 15 Note that a feasible solution to this problem cannot include preemption, but an appropriate schedule with preemption can be used to provide a lower bound for each subproblem encountered. You will be using this problem data to demonstrate your knowledge of branch-and-bound (B&B) procedures in parts a and b. To compute the lower bound for a subproblem, use the Shortest Remaining Processing Time (SRPT) rule to schedule any jobs that are not fixed by the partial schedule. The SRPT rules ensures that at every point in time, the job being processed is the job with the smallest remaining processing time among the set of available jobs. A job j is available at time t if its release date r, satisfies rst and some amount of job j's processing time still remains to be completed. Note that the SRPT rule permits preemption. For example, in the provided data, job 1 is the only job that is available at time 0. Thus, at time 0, job 1 should be processed. At time 1, job 2 becomes available. At this point in time (time 1), we will have processed job 1 for 1 time unit. Thus, job 1 has 8 units of processing remaining. However, job 2 only requires 7 units of processing time. Thus, job 2 should preempt job 1 and start running at time 1. Comments: A partial solution (e.g., 21****) denotes the order of job completions for jobs that are to be processed without preemption. Jobs not specified in the partial solution must be processed in SRPT order and preemption of these jobs is permitted. For example, the partial solution 21**** specifies that job 2 will be the first job to be completed and job 1 will be second job to be completed. However, if feasible with regard to release dates, some job not in the partial solution (say job 4) may be processed prior to the release date of job 2, and then be preempted by job 2. Further, some other job (say job 5) may be the job selected to be processed at the completion of job 2 and then be preempted at the start of job 1. Please state any additional assumptions that you employ in your branch-and-bound procedure. As the branching rule, always branch on the subproblem having the smallest lower bound. If there is a tie, branch on the subproblem that is at the deepest level of the branch-and-bound tree. a. Compute the solution for the root node, i.e., Ø. Explain what information this solution provides. (3) b. Compute the solutions for the level 1 partial schedules, i.e., 1*****, ***** 6*****. Given these solutions, where would you branch next? c. Consider the partially completed B&B tree shown below. Given the current status, state your next step and justify your decision. "LB denotes a lower bound *UB denotes an upper bound LB = 10 1*** 2*** LB = 10 LB = 10 LB = 10 3*** UB=10 4*** d. Consider the partially completed B&B tree shown below. Given the current status, state your next step and justify your decision. (5) *LB denotes a lower bound *UB denotes an upper bound LB = 10 1*** 2*** Ø LB = 11 LB 10 LB = 12 3*** UB= 12 4*** Consider the following 1 | r | E(C-1) problem instance. j 3 rj 7 P 6 1 0 9 2 1 7 4 10 3 552 15 Note that a feasible solution to this problem cannot include preemption, but an appropriate schedule with preemption can be used to provide a lower bound for each subproblem encountered. You will be using this problem data to demonstrate your knowledge of branch-and-bound (B&B) procedures in parts a and b. To compute the lower bound for a subproblem, use the Shortest Remaining Processing Time (SRPT) rule to schedule any jobs that are not fixed by the partial schedule. The SRPT rules ensures that at every point in time, the job being processed is the job with the smallest remaining processing time among the set of available jobs. A job j is available at time t if its release date r, satisfies rst and some amount of job j's processing time still remains to be completed. Note that the SRPT rule permits preemption. For example, in the provided data, job 1 is the only job that is available at time 0. Thus, at time 0, job 1 should be processed. At time 1, job 2 becomes available. At this point in time (time 1), we will have processed job 1 for 1 time unit. Thus, job 1 has 8 units of processing remaining. However, job 2 only requires 7 units of processing time. Thus, job 2 should preempt job 1 and start running at time 1. Comments: A partial solution (e.g., 21****) denotes the order of job completions for jobs that are to be processed without preemption. Jobs not specified in the partial solution must be processed in SRPT order and preemption of these jobs is permitted. For example, the partial solution 21**** specifies that job 2 will be the first job to be completed and job 1 will be second job to be completed. However, if feasible with regard to release dates, some job not in the partial solution (say job 4) may be processed prior to the release date of job 2, and then be preempted by job 2. Further, some other job (say job 5) may be the job selected to be processed at the completion of job 2 and then be preempted at the start of job 1. Please state any additional assumptions that you employ in your branch-and-bound procedure. As the branching rule, always branch on the subproblem having the smallest lower bound. If there is a tie, branch on the subproblem that is at the deepest level of the branch-and-bound tree. a. Compute the solution for the root node, i.e., Ø. Explain what information this solution provides. (3) b. Compute the solutions for the level 1 partial schedules, i.e., 1*****, ***** 6*****. Given these solutions, where would you branch next? c. Consider the partially completed B&B tree shown below. Given the current status, state your next step and justify your decision. "LB denotes a lower bound *UB denotes an upper bound LB = 10 1*** 2*** LB = 10 LB = 10 LB = 10 3*** UB=10 4*** d. Consider the partially completed B&B tree shown below. Given the current status, state your next step and justify your decision. (5) *LB denotes a lower bound *UB denotes an upper bound LB = 10 1*** 2*** Ø LB = 11 LB 10 LB = 12 3*** UB= 12 4***

Answer rating: 100% (QA)

The images you provided contain the description of a scheduling problem and partial branchandbound BB decision trees for solving this problem with job ... View the full answer