Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times

• Processing time dependent on starting time is modeled.
• Scheduling with non-simultaneous machine available times is studied.
• Heuristic algorithms and their worst-case error bounds are given for the problem.

In this note, we deal with the parallel-machine scheduling of deteriorating jobs where the actual processing of a job is a simple linear function of the job’s starting time. The jobs are available at time zero but the machines may not be available simultaneously at time zero. For the problem to minimize the logarithm of makespan, we present heuristic algorithms and analyze their worst-case error bounds.