Distributed simulated annealing algorithms for job shop scheduling

摘要

Job shop scheduling belongs to the class of NP-hard problems. There are a number of algorithms in literature for finding near optimal solution for the job shop scheduling problem. Many of these algorithms exploit the problem specific information and hence are less general. However, the simulated annealing algorithm for job shop scheduling is general and 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 problems. One possible approach to reduce the execution time of the algorithm is to develop distributed algorithms for simulated annealing. In the paper, the authors discuss approaches to developing distributed algorithms for simulated annealing for solving the job shop scheduling problem. Three different algorithms have been developed. These are the temperature modifier, the locking edges and the modified locking edges algorithms. These algorithms have been implemented on the distributed task sharing system (DTSS) running on a network of 18 Sun workstations. The observed performance showed that each of these algorithms performs well depending on the problem size.