作业车间调度(job shop scheduling).ppt

JobShopScheduling(JSP)车间作业调度问题简述
已知：有n个工件{J1，J2,…,Jn}在m台机器{M1,M2,…,Mm}上加工，每个工件以一定的次序在所有的机器上轮流加工，每个工件分成m个工序，而每个工序对应相应的加工机器。其中，工序的加工时间给定。
工件上的约束：每个工件上的工序只能在上一个工序执行结束之后，才能开始执行下一个工序。
机器上的约束：每个机器某一个时刻最多只能执行一个工件，而且执行过程是非抢占的。
目标：给出调度方案，使调度总结束时间最小。（Makespan）

典型性：JSP是最基本的调度问题，同时，和TSP问题一样，也是最经典的几个NP-hard问题之一。

复杂性：Garey在1976年第一次给出了此问题的复杂度分析，而后在1979年，Lenstra证明JSP是NP-hard问题并具有挑战性的难度。Fisher和Thompson在1963年提出的FT10*10算例在20多年之后才被找到最优解。目前最先进的算法很难求得较小规模问题的最优解。

实用性：应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等。
i-TSABbyNowickiandSmutnicki(2005)
JournalofScheduling
GESbyPardalosandShylo(2006)
ComputationalManagementScience
TSandTS/SAbyZhangetal.(2007,2008)
Computers&OperationsResearch
AlgFixbyPardalosetal.(2010)
ComputationalOptimizationandApplications
CP/LSbyBecketal.(2011)
InformsJournalonComputing
GES/TSbyNasiriandKianfar(2012)
Computers&IndustrialEngineering
BRKGAbyGoncalvesandResende(2013)
InternationalTransactionsinOperationalResearch
HEAbyChengetal.(2013)
AnnalsofOperationsResearch关键路径：从起点到终点的最长路径，其长度就是Makespan。
关键工序：在关键路径上的工序。关键块：由同一个机器上最大序列的连续关键工件组成。
邻域结构邻域动作N5邻域动作N6邻域动作N7邻域动作比较近似邻域评估策略近似邻域评估策略近似邻域评估策略近似邻域评估策略近似邻域评估策略禁忌对象P={S1,…,Sn}←Population_Initalization();

Tabu_Search(P);

PairSet←{(Si,Sj)丨Si∈P，Sj∈P，Si≠Sj};

Randomlyselectonesolutionpair{Si,Sj}fromPairSet;

Sp1←Path-Relinking{Si,Sj},Sp2←Path-Relinking{Sj,Si};

Tabu_Search(Sp1)，Tabu_Search(Sp2);

Updatethebestsolution,populationandthePairSet;

Repeatuntilasopcriterionismet.PathrelinkingPathrelinkingComputationResultsComputationResultsComputationResults