2 PARALLEL MACHINE SEQUENCING PROBLEMS INVOLVING CONTROLLABLE JOB PROCESSING TIMES

In this note we consider a problem of scheduling n single-operation jobs on m non-identical machines where the sequencing of the jobs and their processing times are decision variables. It is assumed that the cost of performing a job is a linear function of its processing time. The scheduling cost to be minimized is: (A) the total processing cost plus total flow time, (B) the total processing cost plus total weighted earliness and weighted tardiness. We reduce each problem to a transportation problem that can be solved by a polynomial time algorithm.