Abstract:

We consider several uniform parallel-machine scheduling problems in
which the processing time of a job is a linear increasing function of its starting time.
The objectives are to minimize the total completion time of all jobs and the total
load on all machines. We show that the problems are polynomially solvable when
the increasing rates are identical for all jobs; we propose a fully polynomial-time
approximation scheme for the standard linear deteriorating function, where the objective
function is to minimize the total load on all machines. We also consider the
problem in which the processing time of a job is a simple linear increasing function
of its starting time and each job has a delivery time. The objective is to find a schedule
which minimizes the time by which all jobs are delivered, and we propose a fully
polynomial-time approximation scheme to solve this problem.