《作业车间调度jobshopscheduling课件》由会员分享，可在线阅读，更多相关《作业车间调度jobshopscheduling课件（25页珍藏版）》请在金锄头文库上搜索。
1、JobShopScheduling(JSP)车间作业调度问题简述1Peng BoPeng BoPhd candidatehttp:/ 个工件个工件 J1，J2, , Jn 在在 m 台机器台机器 M1, M2, , Mm上加工，每个工件以上加工，每个工件以一定的次序一定的次序在所有的机器上轮流加在所有的机器上轮流加工，每个工件分成工，每个工件分成 m 个工序，而每个工序对应相应的加工机个工序，而每个工序对应相应的加工机器。其中，工序的器。其中，工序的加工时间加工时间给定。给定。工件上的约束：每个工件上的工序只能在上一个工序执行结束工件上的约束：每个工件上的工序只能在上一个工序执行结束之后，才能
2、开始执行下一个工序。之后，才能开始执行下一个工序。机器上的约束：每个机器某一个时刻最多只能执行一个工件，机器上的约束：每个机器某一个时刻最多只能执行一个工件，而且执行过程是非抢占的。而且执行过程是非抢占的。目标：给出调度方案，使调度总结束时间最小。目标：给出调度方案，使调度总结束时间最小。（Makespan）描述描述工序工序1 工序工序2 工序工序3J1 : M1 M2 M3J2 : M3 M1 M2J3 : M2 M3 M1典型性：典型性：JSP是最基本的调度问题，同时，和是最基本的调度问题，同时，和TSP问题一样，也问题一样，也是最经典的几个是最经典的几个NP-hard 问题之一。问题之一
3、。复杂性：复杂性：Garey在在1976年第一次给出了此问题的复杂度分析，年第一次给出了此问题的复杂度分析，而后在而后在1979年，年，Lenstra证明证明JSP是是NP-hard问题并具有挑战性问题并具有挑战性的难度。的难度。Fisher和和Thompson在在1963年提出的年提出的FT10*10算例在算例在20多年之后才被找到最优解。目前最先进的算法很难求得较小规多年之后才被找到最优解。目前最先进的算法很难求得较小规模问题的最优解。模问题的最优解。实用性：应用领域极其广泛，涉及航母调度，机场飞机调度，实用性：应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线
4、等。港口码头货船调度，汽车加工流水线等。介绍介绍i-TSAB by Nowicki and Smutnicki (2005) Journal of SchedulingGES by Pardalos and Shylo (2006) Computational Management ScienceTS and TS/SA by Zhang et al. (2007, 2008) Computers & Operations ResearchAlgFix by Pardalos et al. (2010) Computational Optimization and ApplicationsCP
5、/LS by Beck et al. (2011) Informs Journal on ComputingGES/TS by Nasiri and Kianfar (2012) Computers & Industrial EngineeringBRKGA by Goncalves and Resende (2013) International Transactions in Operational ResearchHEA by Cheng et al. (2013) Annals of Operations Research研究背景研究背景关键路径：从起点到终点的最长路径，其长度就是关键
6、路径：从起点到终点的最长路径，其长度就是Makespan。关键工序：在关键路径上的工序。关键工序：在关键路径上的工序。概念定义概念定义关键块：由同一个机器上关键块：由同一个机器上最大序列最大序列的的连续连续关键工件组成。关键工件组成。概念定义概念定义邻域结构邻域结构邻域动作（邻域动作（N1-N7）都是基于关键路径的操作。）都是基于关键路径的操作。Matsuo在在1988提出，交换关键块内的工件不能减小提出，交换关键块内的工件不能减小Makespan。现今最有效的，现今最有效的，Nowicki和和Smutnicki提出了提出了N5；Balas和和Vazacopoulos提出了提出了N6领域结构，
7、张超勇提出的领域结构，张超勇提出的N7。邻域动作邻域动作 N5N5N5邻域结构是邻域结构是Nowicki和和Smutnicki在在1992年提出并发表在年提出并发表在Management Science上的。上的。仅交换块首和块尾两相邻工件以避免交换关键块内的工件。仅交换块首和块尾两相邻工件以避免交换关键块内的工件。优点：邻域结构小，速度快；缺点：过度限制无效移动，使优点：邻域结构小，速度快；缺点：过度限制无效移动，使领域连通能力和搜索效率受到削弱。领域连通能力和搜索效率受到削弱。邻域动作邻域动作N6N6N6邻域结构是邻域结构是Balas和和Vazacopoulos在在1988年提出并发表在年
8、提出并发表在Management Science。把内部工件移动到块首之前和块尾之后。一直沿用至今，仍把内部工件移动到块首之前和块尾之后。一直沿用至今，仍是最有效的邻域结构之一。是最有效的邻域结构之一。邻域动作邻域动作N7N7N7邻域结构是张超勇在邻域结构是张超勇在2007年提出并发表在年提出并发表在COR上。上。在在N6的基础上增加了一种邻域动作即把关键块的首尾工件移的基础上增加了一种邻域动作即把关键块的首尾工件移动至关键块内部。一直沿用至今，仍是最有效的邻域结构之动至关键块内部。一直沿用至今，仍是最有效的邻域结构之一。一。邻域动作比较邻域动作比较N7N6N5MCmax14161420146
9、2MEN1061637021648973CPU-time298205121MCmax : Average makespan.MEN: The mean number of evaluated neighbors.CPU-time: The total CPU time performed in all (72) instances.近似邻域评估策略近似邻域评估策略定义：定义：Ri: 表示表示 从起始工序从起始工序 到工序到工序 i 的最长路径长度。的最长路径长度。Qi: 表示从工序表示从工序 i 到到 终止工序的最长路径长度。终止工序的最长路径长度。近似邻域评估策略近似邻域评估策略近似评价值：
10、近似评价值：近似邻域评估策略近似邻域评估策略Ru, v 的求法：的求法：近似邻域评估策略近似邻域评估策略Qu,v的求法：的求法：近似邻域评估策略近似邻域评估策略实验结果显示，近似方法花费的计算时间一般为精确方实验结果显示，近似方法花费的计算时间一般为精确方法的法的10-20%，并且问题规模越大，近似方法的执行效率，并且问题规模越大，近似方法的执行效率也越高。一般直觉认为的精确方法在解的质量方面优于也越高。一般直觉认为的精确方法在解的质量方面优于近似方法，但是实验结果没有证实这个观点。近似方法，但是实验结果没有证实这个观点。禁忌对象禁忌对象禁忌的部分解，而非动作。禁忌的部分解，而非动作。P =
11、S1 , , Sn Population_Initalization();Tabu_Search( P );PairSet ( Si , Sj ) 丨丨 Si P， Sj P，Si Sj ;Randomly select one solution pair Si , Sj from PairSet;Sp1 Path-Relinking Si , Sj , Sp2 Path-Relinking Sj , Si ; Tabu_Search(Sp1 )， Tabu_Search(Sp2 ) ;Update the best solution, population and the PairSet;R
12、epeat until a sop criterion is met.The outline of TS/PRThe outline of TS/PRPath relinkingPath relinkingIllustration of the path solution selection procedure as follows:Path relinkingPath relinkingPath Construction in the example of two machines as follows:Computation ResultsComputation ResultsTS/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 ResultsComputation ResultsThe comparisons in terms of computing time for all the instancesComputation ResultsComputation Results谢谢观赏谢谢观赏
