DISTRIBUTED SIMULATED ANNEALING ALGORITHMS FOR JOB-SHOP SCHEDULING

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.