作　　者： ; ;

机构地区： 华中科技大学计算机科学与技术学院计算机科学理论研究所

出　　处： 《计算机学报》 2005年第5期809-816,共8页

摘　　要： 该文提出了一种新的求解工件车间调度(jobshopscheduling)问题的邻域搜索算法.问题的目标是在满足约束条件的前提下使得调度的makespan尽可能地小.定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向.计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法.其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解.这些实例是当前文献中报导的所有规模为10工件10机器的实例. A new local search algorithm for solving the minimum make span problem of job shop scheduling is presented. The objective of this kind of job shop scheduling problem is minimizing the completion time of all the jobs, called the makespan, subject to the constraints that: (1) the sequence of machines for each job is prescribed, and (2) each machine can process at most one job at a time. Job shop scheduling is well known to be a strongly NP-complete problem. Research experience shows that it is among the hardest combinatorial optimization problems. A new dispatching rule bases on greedy strategy is proposed to generate initial solution. A new concept of neighborhood structure is proposed. The neighborhood structure is based on some kind of greedy strategy other than disjunctive graph, which is common in the literature. Some lemmas and theorems base on the neighborhood structure are given and proved. The algorithm is a hybrid one since single machine sequencing is embedded into local search framework to take advantage of the differences between the two neighborhood structures. Six jumping strategies are proposed to jump from local optimal solution and guide the search in promising directions. The algorithm is tested on 58 benchmark instances and yields better solutions than two other particularly efficient algorithms discussed in the literature.

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

领　　域： [自动化与计算机技术] [自动化与计算机技术]