Problems:
Suppose you have N jobs that have to be processed on a single machine. For i = 1, 2, . . . ,N, job i requires pi units of time on the machine, and has weight wi. The objective is to schedule these jobs so as to minimize the sum of the weighted completion time of all the jobs, where the completion time of job i is the time at which job i finishes.
Note that at most one job can run on the machine at any time. For example, let N = 3, p1= 1, p2 = 2, p3 = 3, and the weights are w1 = 2, w2 = 1, w3 = 0. If the jobs are scheduled in the order 231, then the completion time of job 2 is 2, completion time of job 3 is 5, and
the completion time of job 1 = 6. The value of the objective function for this schedule is 2 × 6 + 1 × 2, which is 14. (We consider schedules that are non-preemptive: any job started on the machine cannot be interrupted. In other words, if we decide to schedule job 2 as the first job, we have to let it run until time 2, which is when job 2 finishes.)
Define T = ∑Ni=1 Pj .
Clearly, it is enough to consider schedules in which all of the jobs are completed by time T. (In other words, there is no benefit to keeping the machine idle when there are jobs to be processed.) For i = 1, 2, . . . ,N, and t = 1, 2, . . . , T, let your decision variables be Xit, which is 1 if job i completes at time t, and 0 otherwise. Formulate the given scheduling problem as a linear (integer) programming problem involving these decision variables. (Hint: You need to incorporate the non-preemptive condition and the condition that at most one job can run on the machine at any time.)