Instructions: Show your work $...$ no work will result in no credit.

Place a circle or box around your final answer. Submit at start of next class.

Consider the $1|r_j|$ problem instance presented below

$\backslash$table$[[$Job$,$j$,1,2,3,4,5],[$Processing time,$p_j,4,5,7,3,6],[,$Release date,$r_j,6,8,0,9],[$Due date,$d_j,12,20,14,13,9],[,,,,,,]]$

$[7$ points$]$ Suppose that $$ is the maximum job tardiness. For the earliest due date $($EDD$)$ first dispatching rule, what is the value of $?$ Provide a Gantt Chart of the schedule and the value of $.$

Tmax

$2.[7$ points$]$ Suppose that $$ is the sum of job completion times. For the shortest processing time $($SPT$)$ first dispatching rule, what is the value of $?$ Provide a Gantt Chart of the schedule and the value of $.$

$3.[6$ points$]$ Demonstrate that the SPT solution in $[2]$ above is not optimal by finding a solution with a lower value of $.$ Provide a Gantt Chart of your schedule and the value of $.$