Problem 3 Consider the problem of scheduling a set of jobs so as to minimize the total weighted completion time. There are n jobs indexed by [n] := {1,2,3,...n}, and each job je (n] has a weight w; > 0 and processing time p, 2 0. The goal of the problem is to output an ordering of jobs so as to minimize the total weighted completion time of all jobs. See Figure 1 for an instance of the problem. ! 2 3 2 3 1 0 1 5 6 1 cos2x15x87x60 cont x2+7+20W Figure 1: An instance with two different schedules. The second schedule has a better weighted completion time than the first one, and it is the optimum schedule. 1 Prove that the schedule that processes the jobs ; in increasing order of is the optimum for the instance. For convenience, you can assume that for any two different jobs j and ;', we have toy 10