A Novel Large-Step Optimization Method for Job Shop Scheduling
Local search methods have characteristic of obtaining decent solution with short or acceptable time for job shop scheduling problems. They improve solution by search iteratively neighbors of initial solution. But they tend to get trapped in local optimal solutions, usually far away from the global optimal solution. Simulated annealing methods try to improve on this by accepting uphill moves depending on a decreasing probability controlled by the temperature parameter. But, at small temperatures, they also tend to get stuck in valleys of the cost function. In this paper, we proposed a large-Step optimization method. The large step of the large-step optimization methods allows one to leave these valleys even at small temperatures.Experiments on some job shop scheduling benchmark problems demonstrated the effectiveness and efficiency of the Large-Step Optimization Method
job shop scheduling local search methods large-step optimization method simulated annealing algorithm
YIN Hongli WANG Yongming HU Enliang ZHAO Chenggui
School of Computer Science and Information Technology Yunnan Normal University Kunming, Yunnan Provi Computer Science Department Qujing Normal University Qujing, Yunnan Province 655011, China School of mathematics Yunnan Normal University Kunming, Yunnan Province 650092, China Computer Science Department Yunnan University of finance and economics Kunming, Yunnan Province 6502
国际会议
武汉
英文
342-347
2007-07-25（万方平台首次上网日期，不代表论文的发表时间）