求解工件车间调度问题的一种新的邻域搜索算法

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

A New Local Search Algorithm for Job Shop Scheduling Problem

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.