Consider the following scheduling problem. There are m machines, each of which can process jobs, one job at a time. The problem is to assign jobs to machines (each job needs to be assigned to exactly one machine) and order the jobs on machines so as to minimize a cost function. The machines run at different speeds, but jobs are identical in their processing needs. More formally, each machine i has a parameter li, and each job requires li time if assigned to machine i. There are n jobs. Jobs have identical processing needs but different levels of urgency. For each job j, we are given a cost function cj(t)that is the cost of completing job j at time t. We assume that the costs are nonnegative, and monotone in t. A schedule consists of an assignment of jobs to machines, and on each machine the schedule gives the order in which the jobs are done. The job assigned to machine i as the first job will complete at time li, the second job at time 21i and so on. For a schedule S, let tS(j) denote the completion time of job j in this schedule. The cost of the schedule is (S) = Σjcj(t(s)).

Required:
Give a polynomial-time algorithm to find a schedule of minimum cost.