Parallel-machine scheduling with controllable processing times

Abstract

We consider a problem of scheduling nindependent and simultaneously available jobs on munrelated parallel machines. The job processing times can be compressed through incurring an additional cost, which is a convex function of the amount of compression. Two problems are formulated as assignment problems, which can be solved inO (n³m + n²m log(nm))time. One is to minimize the total compression cost plus the total flow time. The other is to minimize the total compression cost plus the sum of earliness and tardiness costs.