文献类型：期刊文章

作　　者：王磊[1] 黄文奇[1]

机构地区：[1]华中科技大学计算机科学与技术学院计算机科学理论研究所,武汉430074

出　　处：《计算机学报》

基　　金：国家自然科学基金(10471051);国家"九七三"重点基础研究发展规划项目基金(2004CB318000)资助.~~

年　　份：2005

卷　　号：28

期　　号：5

起止页码：809-816

语　　种：中文

收录情况：BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：该文提出了一种新的求解工件车间调度(jobshopscheduling)问题的邻域搜索算法.问题的目标是在满足约束条件的前提下使得调度的makespan尽可能地小.定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向.计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法.其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解.这些实例是当前文献中报导的所有规模为10工件10机器的实例.

关 键 词：组合优化 NP难问题 工件车间调度  邻域搜索

分 类 号：TP18]