MULTI-PATH TABU SEARCH METHOD FOR JOB SHOP SCHEDULING PROBLEM
Job shop scheduling problems (JSP) are known as NP-hard problems, which have been studied by a significant number of researchers for decades. Tabu Search, as one of the heuristic algorithms, has been widely researched and applied for scheduling problem. In this paper, a tabu search based job shop scheduling system with a new method called multi-path exploring is proposed. The multi-path exploring method employs more than one search path at one time to make the search can exploring larger decision space to reach the optimality. And when the selected path cannot provide improvement since a predetermined time, the search can exclude the current search path and select other path to explore to avoid the misguiding by local optimality. The tabu list is used to guide the search to explored regions. The length of it decides the efficiency of search, but actually it is impossible to set an appropriate length to the tabu list. To against this problem, we also proposed another method called tabu-recall to deal with it in this paper. The final experimental test shows the proposed scheduling system can provide a fast responsive and good object values.
Multi-path ezploring Tabu Search Job shop scheduling
Zheng Yao Shigeru Fujimura
Graduate School of Information, Production and Systems, Waseda University 2-7 Hibikino, Wakamatsu-ku, Kitakyushu, Fukuoka, 808-0135, Japan
国际会议
上海
英文
1-6
2009-08-02（万方平台首次上网日期，不代表论文的发表时间）