K. Krishna et al., DISTRIBUTED SIMULATED ANNEALING ALGORITHMS FOR JOB-SHOP SCHEDULING, IEEE transactions on systems, man, and cybernetics, 25(7), 1995, pp. 1102-1109
Citations number
10
Categorie Soggetti
Controlo Theory & Cybernetics","Computer Science Cybernetics","Engineering, Eletrical & Electronic
Job shop scheduling belongs to the class of NP-hard problems, There ar
e a number of algorithms in literature for finding near optimal soluti
on for the job shop scheduling problem. Many of these algorithms explo
it the problem specific information and hence are less general. Howeve
r, simulated annealing algorithm for job shop scheduling is general an
d produces better results in comparison with other similar algorithms,
But one of the major drawbacks of the algorithm is that the execution
time is high, This makes the algorithm inapplicable to large scale pr
oblems, One possible approach to reduce the execution time of the algo
rithm is to develop distributed algorithms for simulated annealing, In
this paper, we discuss approaches to developing distributed algorithm
s for simulated annealing for solving the job shop scheduling problem.
Three different algorithms have been developed, These are the Tempera
ture Modifier, the Locking Edges and the Modified Locking Edges algori
thms, These algorithms have been implemented on the Distributed Task S
haring System (DTSS) running on a network of 18 sun workstations. The
observed performance showed that each of these algorithms performs wel
l depending on the problem size.