Scheduling jobs on parallel machines with sequence-dependent setup times

Scheduling jobs on parallel machines with sequence-dependent setup times

0.00 Avg rating0 Votes
Article ID: iaor19991752
Country: Netherlands
Volume: 100
Issue: 3
Start Page Number: 464
End Page Number: 474
Publication Date: Aug 1997
Journal: European Journal of Operational Research
Authors: ,
Abstract:

Consider a number of jobs to be processed on a number of identical machines in parallel. A job has a processing time, a weight and a due date. If a job is followed by another job, a setup time independent of the machine is incurred. A three phase heuristic is presented for minimizing the sum of the weighted tardinesses. In the first phase, as a pre-processing procedure, factors or statistics which characterize an instance are computed. The second phase consists of constructing a sequence by a dispatching rule which is controlled through parameters determined by the factors. In the third phase, as a post-processing procedure, a simulated annealing method is applied starting from a seed solution which is the result of the second phase. In the dispatching rule of the second phase there are two parameters of which the values are dependent on the particular problem instance at hand. Through extensive experiments rules are developed for determining the values of the two parameters which make the priority rule work effectively. The performance of the simulated annealing procedure in the third phase is evaluated for various values of the factors.

Reviews

Required fields are marked *. Your email address will not be published.