Scheduling linearly deteriorating jobs on parallel machines: a simulated annealing approach
No Thumbnail Available
Date
2001
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
Citation
Hindi, K.S. and Mhlanga, S., 2001. Scheduling linearly deteriorating jobs on parallel machines: a simulated annealing approach. Production Planning & Control, 12(1), pp.76-80.