| Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem |
| |
| 作者姓名： | 黄文奇 曾立平 |
| |
| 作者单位： | SchoolofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan430074,China |
| |
| 基金项目： | TheNationalGrandFundamentalResearch973ProgramofChina (No .G19980 30 6 0 0 ) |
| |
| 摘 要： | A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson ( ie. , FT6 and FT20) is made. The experiment results show the better optimal performance of the proposed algorithm.
|
| 关 键 词： | 作业安排调度 局部搜索 混合邻域 滤波电路 截止策略 |
Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem |
| |
| Huang WenqiZeng Liping School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan ,China.Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem[J].Journal of Southwest Jiaotong University,2004,12(2):95-100. |
| |
| Authors: | Huang WenqiZeng Liping School of Computer Science and Technology Huazhong University of Science and Technology Wuhan China |
| |
| Institution: | School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China |
| |
| Abstract: | A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson (ie., FT6 and FT20)is made. The experiment results show the better optimal performance of the proposed algorithm. |
| |
| Keywords: | Job shop scheduling Local search Hybrid neighborhood Off-trap strategy |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
