%0 Journal Article
%T A Local Search Method with Hybrid Neighborhood for the Job Shop Scheduling Problem<br>一种求解车间作业调度问题的混合邻域结构搜索算法
%A ZENG Li-Ping
%A HUANG Wen-Qi Theoretical Computer Science Institute
%A School of Computer Science
%A Technology
%A Huazhong University of Science
%A Technology
%A Wuhan
%A <br>曾立平
%A 黄文奇
%J 计算机科学
%D 2005
%I 
%X Job shop scheduling problem is well known to be a difficult, strongly NP-complete problem, the objective of this is minimizing the completion time of all the jobs, called the make span, subject to the constraints of this kind of problem. A local search method with hybrid neighborhood is presented for job shop scheduling problem. The key problems for local search method, such as neighborhood structure and off-trap strategy, the solutions are made to de- crease the makespan of the schedule. Our approach is tested on a total of 43 standard problem instances, 39 instances are found optimal solutions, including the notorious instances FT10. Our approach yields better solutions than a par- ticularly efficient algorithms discussed in the literature.
%K Job shop scheduling
%K Neighborhood
%K Local search
%K Off-trap strategy<br>车间作业调度问题
%K 邻域结构
%K 搜索算法
%K 混合
%K 求解
%K 优化组合
%K 约束条件
%K 加工周期
%K 解决方案
%K 测试实验
%K 国际标准
%K 行搜索
%K 最优解
%K 算例
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=7DDA617FC7FE7C26&yid=2DD7160C83D0ACED&vid=9971A5E270697F23&iid=94C357A881DFC066&sid=6425DAE0271BB751&eid=F1A8654ADB4E656E&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=11