作业车间调度(job-shop-scheduling)

ConfederalConfidentialJobShopScheduling(JSP)车间作业调度问题简述1PengBoPhdcandidate已知：有n个工件{J1，J2,…,Jn}在m台机器{M1,M2,…,Mm}上加工，每个工件以一定的次序在所有的机器上轮流加工，每个工件分成m个工序，而每个工序对应相应的加工机器。其中，工序的加工时间给定。工件上的约束：每个工件上的工序只能在上一个工序执行结束之后，才能开始执行下一个工序。机器上的约束：每个机器某一个时刻最多只能执行一个工件，而且执行过程是非抢占的。目标：给出调度方案，使调度总结束时间最小。（Makespan）描述工序1工序2工序3J1:M1M2M3J2:M3M1M2J3:M2M3M1ConfederalConfidential典型性：JSP是最基本的调度问题，同时，和TSP问题一样，也是最经典的几个NP-hard问题之一。复杂性：Garey在1976年第一次给出了此问题的复杂度分析，而后在1979年，Lenstra证明JSP是NP-hard问题并具有挑战性的难度。Fisher和Thompson在1963年提出的FT10*10算例在20多年之后才被找到最优解。目前最先进的算法很难求得较小规模问题的最优解。实用性：应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等。介绍ConfederalConfidential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研究背景ConfederalConfidential关键路径：从起点到终点的最长路径，其长度就是Makespan。关键工序：在关键路径上的工序。概念定义ConfederalConfidential关键块：由同一个机器上最大序列的连续关键工件组成。概念定义ConfederalConfidential邻域结构邻域动作（N1-N7）都是基于关键路径的操作。Matsuo在1988提出，交换关键块内的工件不能减小Makespan。现今最有效的，Nowicki和Smutnicki提出了N5；Balas和Vazacopoulos提出了N6领域结构，张超勇提出的N7。ConfederalConfidential邻域动作N5N5邻域结构是Nowicki和Smutnicki在1992年提出并发表在ManagementScience上的。仅交换块首和块尾两相邻工件以避免交换关键块内的工件。优点：邻域结构小，速度快；缺点：过度限制无效移动，使领域连通能力和搜索效率受到削弱。ConfederalConfidential邻域动作N6N6邻域结构是Balas和Vazacopoulos在1988年提出并发表在ManagementScience。把内部工件移动到块首之前和块尾之后。一直沿用至今，仍是最有效的邻域结构之一。ConfederalConfidential邻域动作N7N7邻域结构是张超勇在2007年提出并发表在COR上。在N6的基础上增加了一种邻域动作即把关键块的首尾工件移动至关键块内部。一直沿用至今，仍是最有效的邻域结构之一。ConfederalConfidential邻域动作比较N7N6N5MCmax141614201462MEN1061637021648973CPU-time298205121MCmax:Averagemakespan.MEN:Themeannumberofevaluatedneighbors.CPU-time:ThetotalCPUtimeperformedinall(72)instances.ConfederalConfidential近似邻域评估策略定义：R[i]:表示从起始工序到工序i的最长路径长度。Q[i]:表示从工序i到终止工序的最长路径长度。｛｝ConfederalConfidential近似邻域评估策略｛｝近似评价值：ConfederalConfidential近似邻域评估策略Ru,v的求法：｛｝ConfederalConfidential近似邻域评估策略Qu,v的求法：｛｝ConfederalConfidential近似邻域评估策略实验结果显示，近似方法花费的计算时间一般为精确方法的10-20%，并且问题规模越大，近似方法的执行效率也越高。一般直觉认为的精确方法在解的质量方面优于近似方法，但是实验结果没有证实这个观点。｛｝ConfederalConfidential禁忌对象禁忌的部分解，而非动作。ConfederalConfidential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.TheoutlineofTS/PRConfederalConfidentialPathrelinkingIllustrationofthepathsolutionselectionprocedureasfollows:ConfederalConfidentialPathrelinkingPathConstructionintheexampleoftwomachinesasfollows:ConfederalConfidentialComputationResultsTS/PRisabletoreachthebestlowerboundfortheSWV15,meaningthatTS/PRsolvesit,whichhasremainedunsolvedforover20years.ConfederalConfidentialComputationResultsThecomparisonsintermsofcomputingtimeforalltheinstancesConfederalConfidentialComputationResultsConfederalConfidential谢谢观赏