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

Confederal Confidential,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Hong Liu 2013,*,Job Shop Scheduling(JSP),车间作业调度问题简述,1,Peng Bo,Phd candidate,J1,，,J2,Jn,在,m,台机器,M1,M2,Mm,上加工，每个工件以,一定的次序,在所有的机器上轮流加工，每个工件分成,m,个工序，而每个工序对应相应的加工机器其中，工序的,加工时间,给定。,工件上的约束：每个工件上的工序只能在上一个工序执行结束之后，才能开始执行下一个工序。,机器上的约束：每个机器某一个时刻最多只能执行一个工件，而且执行过程是非抢占的。,目标：给出调度方案，使调度总结束时间最小。（,Makespan,）,描述,工序,1,工序,2,工序,3,J1,:M1 M2 M3,J2,:M3 M1 M2,J3 :M2 M3 M1,典型性：,JSP,是最基本的调度问题，同时，和,TSP,问题一样，也是最经典的几个,NP-hard,问题之一。,复杂性：,Garey,在,1976,年第一次给出了此问题的复杂度分析，而后在,1979,年，,Lenstra,证明,JSP,是,NP-hard,问题并具有挑战性的难度。,Fisher,和,Thompson,在,1963,年提出的,FT10*10,算例在,20,多年之后才被找到最优解。目前最先进的算法很难求得较小规模问题的最优解。,实用性：应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等。,介绍,i-TSAB,by Nowicki and Smutnicki (2005),Journal of Scheduling,GES,by Pardalos and Shylo (2006),Computational Management Science,TS,and,TS/SA,by Zhang et al.(2007,2008),Computers&Operations Research,AlgFix,by Pardalos et al.(2010),Computational Optimization and Applications,CP/LS,by Beck et al.(2011),Informs Journal on Computing,GES/TS,by Nasiri and Kianfar(2012),Computers&Industrial Engineering,BRKGA,by Goncalves and Resende(2013),International Transactions in Operational Research,HEA,by Cheng et al.(2013),Annals of Operations Research,研究背景,关键路径：从起点到终点的最长路径，其长度就是,Makespan,。,关键工序：在关键路径上的工序。,概念定义,关键块：由同一个机器上,最大序列,的,连续,关键工件组成。,概念定义,邻域结构,邻域动作（,N1-N7,）都是基于关键路径的操作。,Matsuo,在,1988,提出，交换关键块内的工件不能减小,Makespan,。,现今最有效的，,Nowicki,和,Smutnicki,提出了,N5,；,Balas,和,Vazacopoulos,提出了,N6,领域结构，张超勇提出的,N7,。,邻域动作,N5,N5,邻域结构是,Nowicki,和,Smutnicki,在,1992,年提出并发表在,Management Science,上的。,仅交换块首和块尾两相邻工件以避免交换关键块内的工件。,优点：邻域结构小，速度快；缺点：过度限制无效移动，使领域连通能力和搜索效率受到削弱。,邻域动作,N6,N6,邻域结构是,Balas,和,Vazacopoulos,在,1988,年提出并发表在,Management Science,。,把内部工件移动到块首之前和块尾之后。一直沿用至今，仍是最有效的邻域结构之一。,邻域动作,N7,N7,邻域结构是张超勇在,2007,年提出并发表在,COR,上。,在,N6,的基础上增加了一种邻域动作即把关键块的首尾工件移动至关键块内部。一直沿用至今，仍是最有效的邻域结构之一。,邻域动作比较,N7,N6,N5,MC,max,1416,1420,1462,MEN,106163,70216,48973,CPU-time,298,205,121,MCmax:Average makespan.,MEN:The mean number of evaluated neighbors.,CPU-time:The total CPU time performed in all(72)instances.,近似邻域评估策略,定义：,Ri:,表示 从起始工序 到工序,i,的最长路径长度。,Qi:,表示从工序,i,到 终止工序的最长路径长度。,近似邻域评估策略,近似评价值：,近似邻域评估策略,R,u,v,的求法：,近似邻域评估策略,Q,u,v,的求法：,近似邻域评估策略,实验结果显示，近似方法花费的计算时间一般为精确方法的,10-20%,，并且问题规模越大，近似方法的执行效率也越高。一般直觉认为的精确方法在解的质量方面优于近似方法，但是实验结果没有证实这个观点。,禁忌对象,禁忌的部分解，而非动作。,P=S,1,S,n,Population_Initalization();,Tabu_Search(P);,PairSet,(S,i,S,j,),丨,S,i,P,，,S,j,P,，,S,i,S,j,;,Randomly select one solution pair S,i,S,j,from PairSet;,S,p1,Path-Relinking S,i,S,j,S,p2,Path-Relinking S,j,S,i,;,Tabu_Search(S,p1,),，,Tabu_Search(S,p2,),;,Update the best solution,population and the PairSet;,Repeat until a sop criterion is met.,The outline of TS/PR,Path relinking,Illustration of the path solution selection procedure as follows:,Path relinking,Path Construction in the example of two machines as follows:,Computation Results,TS/PR is able to reach the best lower bound for the SWV15,meaning that TS/PR solves it,which has remained unsolved for over 20 years.,Computation Results,The comparisons in terms of computing time for all the instances,Computation Results,谢谢观赏,