Scheduling deteriorating jobs on parallel machines is an NP-hard problem, for which heuristics would be the ®rst
solution option. Two variants of linearly deteriorating jobs are
considered. The ®rst is that with simple linear deterioration, i.e. where there is a deterioration rate only, which is meaningful
only if the jobs are assumed to be available at a positive time t0
. In the second variant, there is a basic processing time and a deterioration rate and all jobs are available at time t ˆ 0. In
both cases, we seek to minimize the makespan. Starting from simple heuristics, both steepest descent search
and simulated annealing are designed and implemented to
arrive at optimal or near-optimal solutions. Computational results for randomly generated problem
instances with diåerent job/machine combinations are pre sented.