دانلود رایگان مقاله الگوریتم تبرید شبیه‌سازی شده با فرونشانی برای حل مساله زمانبندی جاب شاپ

ABSTRACT

 Various heuristic based methods are available in literature for optimally solving job shop scheduling problems (JSSP). In this research work a novel approach is proposed which hybridizes fast simulated annealing (FSA) with quenching. The proposed algorithm uses FSA for global search and quenching for localized search in neighborhood of current solution, while tabu list is used to restrict search from revisiting previously explored solutions. FSA is started with a relatively higher temperature and as search progresses temperature is gradually reduced to a value close to zero. The overall best solution (BS) is maintained throughout execution of the algorithm. If no improvement is observed in BS for certain number of iterations then quenching cycle is invoked. During quenching cycle current temperature is reduced to nearly freezing point and iterations are increased by many folds, as a result of this change search becomes nearly greedy. The strength of the proposed algorithm is that even in quenching mode escape from local optima is possible due to use of Cauchy probability distribution and non-zero temperature. At the completion of quenching cycle previous values of search parameters are restored and FSA takes over, which moves search into another region of solution space. Effectiveness of proposed algorithm is established by solving 88 well known benchmark problems taken form published work. The proposed algorithm was able to solve 45 problems optimally to their respective best known values in reasonable time. The proposed algorithm has been compared with 18 other published works. The experimental results show that the proposed algorithm is efficient in finding solution to JSSP.

6. Conclusions and future work

In this paper, a new novel hybrid approach is proposed which combines fast simulated annealing with quenching. In this approach FSA is used for both to perform global search and a way to escape local optima. Quenching is used to perform local search in near vicinity of current solution. The novelty of this approach is two folds one is hybridization of FSA and quenching and the other is its ability to escape local optima even in quenching mode. This approach was tested on 88 well known problems, taken from four groups of benchmark instances. The efficacy of proposed algorithm has been verified by comparing it with other published works of various authors. Proposed algorithm was able to solve all 45 problems optimally in reasonable time, which demonstrate the effectiveness of the proposed method. For future work, we propose to use some other objective function such as tardiness, lateness and due dates etc. instead of make span.