Ag. Mamalis et I. Malagardis, DETERMINATION OF DUE-DATES IN JOB-SHOP SCHEDULING BY SIMULATED ANNEALING, Computer-integrated manufacturing systems, 9(2), 1996, pp. 65-72
Citations number
20
Categorie Soggetti
Operatione Research & Management Science","Computer Science Interdisciplinary Applications","Engineering, Manufacturing","Operatione Research & Management Science
The scheduling of n jobs to m machines in a job shop is considered. A
predefined due date, a release time and the minimization of the maxima
l job's lateness is the objective assigned to each job. A search space
consisting of triads (job, operation, machine) is formulated, and an
iterrative improvement approach, the simulated annealing method, is th
en used to obtain feasible and global optimal solution. The simulated
annealing method is applied to two alternative energy functions to mod
el the maximum lateness. For calculation of the first energy function
at each step, complete schedules are created and the lateness of each
job is derived by abstracting the job's completion time from the corre
sponding due date. The second energy function is calculated on the bas
is of partial estimates often used by pairwise interchange techniques.
The convergence of the algorithm in relation to the initial temperatu
re, temperature iterrations and temperature cycles has been verified i
n various case studies. Specific characteristics of the scheduling, su
ch as its dimensionality and the deviation of the total processing tim
e from the due dates, were considered. Common characteristics derived
were subsequently used for the definition of an efficient annealing sc
hedule. Copyright (C) 1996 Published by Elsevier Science Ltd