《求解流水车间调度问题的差分进化算法设计》8700字（论文）

求解流水车间调度问题的差分进化算法设计目录TOC\o"1-2"\h\u264641绪论 281041.1课题来源与背景 2154351.2本文主要研究内容与意义 3189092差分进化算法 468862.1差分进化算法的含义 435852.2差分进化算法的流程 5183662.3差分进化算法的意义 6205532.4本章小结 621933零等待流水车间 6205963.1引言 6131293.2NWFSP基本概念和模型 7300153.3优化指标和计算 8251303.4本章小结 9277674求解调度问题的差分进化算法设计 9240884.1引言 932124.2求解NWFSP问题的算法 1062374.3算法具体部分的设计 1130284.4本章小结 1259805仿真实验与结果分析 127435.1引言 1256475.2算例介绍 1368295.3算例仿真 14215715.4本章小结 1731016总结与展望 17179056.1总结 1717266.2展望 17摘要：随着我国制造业经济的迅速发展，各部门对制造业的要求也逐渐变高，制造业企业只有在生产加工方式，部门管理等方面进行改革创新，才能面对当今供不应求的局面。解决调度问题就是改革制造业的突破口，调度问题主要研究的就是如何合理的分配资源。本文主要讲解了零等待流水车间的调度问题，以最大完成时间和总流程时间作为优化指标来研究，使读者更容易理解，文章整体结构更加清晰。此外本文还将用到差分进化算法来解决零等待流水车间的调度问题，通过介绍差分进化算法的原理和流程，结合优化指标，求取最优解。我们希望能够在实现算法的基础之上针对大规模、各种类型的算例进行优化设计，并对文中所选算例进行仿真实验，针对仿真数据及结果做出进一步详尽的分析，有效的验证差分进化算法在零等待作业车间调度中的作用与意义。关键词：差分进化算法；零等待；总流程时间1绪论1.1课题来源与背景目前各项企业在迅速发展变化的市场中依旧能够保持竞争地位的关键环节是车间调度，原油工业则是一开始就提出流水车间的调度问题，在化工原料方面加工、食品安全加工、混凝土类制品的生产以及制药工程加工等行业中都有着诸多的应用，可以说是非常方便了。所以说发现更快更好的调度技术以及使用方法有着至关重要的作用。在调度的研究过程中难度毋庸置疑是相当大的，因为整个工程所涉及到的问题都是需要考虑的问题，它不仅受着来自诸多方面的约束，并且每一个环节的变动都会影响调度的结果。因此，在当今这个时代，制造业的发展犹如雨后春笋，技术也不例外，和制造业并相发展，人们开始越来越重视调度问题的研究和解决，不仅如此，企业如果想要提高工作效率，尤为重要的一点就是调度的优化。随着科技与现代技术不断地如日中天与提升，更多的工厂与企业开始关注并重视流水车间调度问题，其中占据重要地位的不得不说零等待流水车间。下面来我们将大致的介绍一下零等待流水车间的主要流程，当工件在完成整个流水线上，每当它完成了一个加工步骤，那么下一个步骤要随即进行，在这一整个过程中工件根本没有停歇的机会，尤其是在非这样不行的时候，第一台工作的车间机器，它的工作必需延迟开始，以此来满足本文所述的零等待的要求。若是机器的数量为两个及以上，对与流水车间问题而言，那么它属于强NP-hard问题。由此可见，能够接受的计算时间范围内，零等待流车间调度问题中有且只有小规模的流水车间才能获得目标最优解。当我们在研究零等待流水车间问题的时候，不难发现，它不仅可以有效的缩短了加工过程所必不可少的时间，而且大幅度减少了上一个步骤与下一个步骤之间的等待时间，并且很大程度上的的提高了工作效率。由此可见，研究和进一步拓展零等待流水车间的调度问题对企业乃至个人都有着相当大的影响和意义，同样的对于此问题的进一步研究也引来了更多科研人员的广泛关注与重视。大部分的研究开发人员都会选择把最大完成时间(makespan,)作为优化指标来研究调度问题。我们不妨学习一下，同样的做法，分别把最大完工时间和总时间当做最终结果所需优化的指标。在研究零等待流水车间的总流程问题时，我们将会通过差分进化算法（DE）来将车间调度进一步优化，并且提供出能够提高工作效率的加工按序，大幅提高企业与工厂的工作效率，使企业的利润达到最大化，我相信这些研讨对企业和现代化社会的发展都具有重要且深远的意义。1.2本文主要研究内容与意义本文主要将会是通过差分进化算法（DE）来认识并解决零等待流水车间总流程时间调度问题，大家可能还不了解该算法的定义，我们可以把它与同样可以解决调度问题的其余算法相比，差分进化算法（DE）是一种效率极高，所涉局域极广的算法，在解决零等待流水车间总流程时间调度问题中同样能够发挥它高效的特点。本文所紧要讲述零等待流水车间总流程时间调度问题、差分进化算法（DE）的流程和步骤，以及通过差分进化算法（DE）解决NWFSP问题的算法设计和各算例的算法仿真。上面已经提到过，我们打算将最大完成时间和总流经时间作为指标来研究本文中所涉及到的调度问题。在这里，需要注意几个点：（1）零等待流水车间是探索本文的前提（2）必须通过差分进化算法（DE）进一步开展车间调度的优化（3）尽可能地把最大完成时间和总流程时间降至最低（4）提高企业以及工厂的生产效率，为企业谋取最大利润。各章节的主要内容如下：第一章：绪论。能够让读者更快更好的搞清楚本课题的来源以及背景，描述了本文主要讲述的内容以及该论文所表达的意义，更好的为下文做铺垫。第二章：差分进化算法。详尽地介绍了该算法的含义，内容，流程等，并且细致地描绘了如何运用此算法来解决车间调度类的问题。分别详略得当的讲解了车间调度和流水车间调度的概念，并且着重强调了零等待流水车间的有关内容，包括概念、模型和优化指标等等。第三章：零等待流水车间。精细地向读者阐述了零等待的内含以及流水车间调度的概念，并着重介绍了零等待流水车间的概念含义以及我们所规定的优化指标的一系列计算。第四章：求解调度问题的差分进化算法设计。本章节通过进一步对算法的介绍和过度，引用相关的例子，使读者能够自己动脑，去更好的理解本文所讲的主要方法。第五章：仿真实验与结果分析。对于上文中所提到的诸多相关算例，我们选取其中一部分进行了仿真实验，我们通过图表的形式让读者更直观的体会和理解。第六章：总结与展望。作者对本文所写的内容陈情并总结，表达作者对此类问题的想法、建议与期望。本论文通过探究差分进化算法（DE）来进一步解决零等待流水车间总流程时间调度问题。通过理论上的详尽细致的描绘和分析，通过观察与计算获得解决此问题的算法，并且使用计算机上的软件进行仿真实验，也可以选择把流水车间的实例运用差分进化算法（DE）进行仿真，得到最终的结果。差分进化算法在车间流水线上的应用有着深远影响与意义，因此企业可以通过此方法降低工件生产过程中的等待时间，大幅提高企业的工作效率，从而使企业在当今竞争力不断增强的社会中取得一席之地。2差分进化算法2.1差分进化算法的含义差分进化算法（DifferentialEvolutionAlgorithm,DE）是一种效率极高，涉及领域非常广的算法，种群整体的启发式搜索算法是它的基础，这个种群里的每个个体都会有一个与之对应的解向量。在进化流程这一方面，差分进化算法与遗传算法也可以说有着非常多的相似点了，两者就像兄弟一样，他们各自都包含这变异，杂交以及选择这三个基本操作，那么关键来了，两者之间最大的区别就是：对于操作的具体方法而言，两者只能说是大不相同了。如果你想要的更加明确的逼近效果，那么你就一定要选择差分进化算法了。差分进化算法（DifferentialEvolutionAlgorithm,DE）是由科学家雷纳斯托恩和肯尼恩普莱斯在1995年的时候最先提出的，人们把他的功能大部分定义在了求解实数优化的问题上，在很大程度上，我们也可以说他是一种演化算法，它的优点非常之多，由于结构清晰易懂，流程很简单，人们想要完成它很容易。不仅如此，差分进化算法的收敛速度极快，并且具有非常强的鲁棒特性，所以它能够在电磁领域，数字滤波器的构造以及模式识别系统等方面具有非常广泛的应用。早在1996年，当年的第一届国际演化计算（ICEO）竞赛，比赛大致是在日本的名古屋进行的，那次比赛就已发现并证明：差分进化算法是世界上速度最快的算法。差分进化算法（DifferentialEvolutionAlgorithm,DE）一般情况下都是通过使用浮点矢量来进行编码，从而生成种群个体，在进行该算法来取得最优解的过程中，第一步，我们首先要做的是要从父代个体中选择两个不同的个体进行向量作差，从而就能够得到差分矢量；第二步，选择另外一个个体（不可同于第一步）与该差分矢量进行求和，从而能够生成实验个体；第三步，将父代个体与第二步中所得的实验个体进行交叉操作；第四步也是最后一步，在父代个体与子代个体之间进行选择操作，把符合要求的个体保存到下一个群体中。2.2差分进化算法的流程图1差分进化算法流程图差分进化算法（DE）的主要操作都是通过突变和选择这两个过程来实现的，这其中突变过程又包含了突变和选择交叉两部分，这两部分的操作多数情况下被用于开发工程和拓展系统，选择过程主要是用于精确地选择出能够被进一步利用的信息进行接下来的操作。2.3差分进化算法的意义差分进化算法中数据很多，引用起来也十分复杂，所以相比与基于传统微积分的方法，差分进化算法有着更多的优点，比如说差分进化算法的效率非常之高，并且局域广阔，它不但具有着自我组织和适应的特点，还可以自我学习。差分进化算法整体而言，操作起来十分简洁方便，通俗易懂，对于测试各种的临床实验问题表现也是尤为突出，目前已成为现代进化算法的研究热点。2.4本章小结本章描述了差分进化算法的含义，基本属性，特点以及运算方式，运算流程，最后讲述了差分进化算法在实验及企业工厂中都具有非常重要的地位。近几年来，差分进化算法已成为现代进化算法的研究热点。3零等待流水车间3.1引言对于解决零等待流水车间调度问题（NWFSP），至关重要就是“零等待”这个条件，那么问题来了，什么叫“零等待”？“零等待”是指工件在生产流水线上，上一个步骤与下一个步骤之间没有停顿，而在普通流水车间调度问题上则是缺少了“零等待”这个约束条件，这也是两者最大的不同之处。本章主要目的就在于解释清楚零等待流水车间调度（NWFSP）的基本概念，以及向读者们介绍它的数学模型和优化指标。对于零等待流水车间调度问题（NWFSP）的优化指标，上文提过不止一次，我们接下来将主要描述最大完工时间（）和总流经时间的计算。本章节将通过对以上两个参数作为指标来研究零等待流水车间调度问题（NWFSP），目的就在于使用该算法大幅度提高企业工厂的工作效率，竭尽所能的减少产品完成所需要的时间，在近现代化工业生产中起到至关重要的作用。3.2NWFSP基本概念和模型经过研究流水车间或者参考文献书籍，网络查阅等等，我们不难发现，零等待流水车间的调度问题其实就可以描述为一个简单地问题：有x个工件和y台机器，当这全部的工件分别在y台机器上工作时，关键的一步在于x个工件在各自的机器上的加工顺序要保证一致。某一个时刻是，每个工件只能在一台机器加工，与此同时一台机器在这一时刻也只能加工这一个工件；在这个过程中我们需要注意，我们还有一个约束条件——“零等待”，也就意味着一个工件在相邻的两台机器之间工作时没有片刻停顿的时间，必须连续加工。工件在每个机器上的加工时间已知。所研究的问题是如何安排各工件的生产序列，我们所想要取得的是最小的优化指标。我们第一步要做的就是给模型中所能出现的变量定义值：x表示了产品的总数值；y表示了机器的总数值； 表示了该机器上的工作时间；表示了最大完成时间；表示了总流程时间；表示了该工件的完成时间。我们研究零等待流水车间调度的问题时，大多数情况下会选择使用混合整数规划模型和有向图模型来解决。由于时间有限，我们接下来会主要阐述混合整数规划模型的方法，零等待流水车间的模型由下图所示：首先，规定决策量 接下来一一列举这其中的约束条件： （1） （2） （3） （4） （5） （6） （7）3.3优化指标和计算对于任何问题的研究，我们都要制指定一个参考物，也就是本节所讲述的优化指标，我们对于零等待流水车间总流程时间调度问题的研究当中，将会把最大完成时间（）和总流经时间作为优化指标，并且详尽描述最大完成时间和流经总时间是如何计算的。（1）最大完成时间的计算方法零等待作为此加工过程的约束条件，两个相邻的工件与工件之间存在一个开工时间差，将两工件记为i-1和i，开工时间差记为,则开工时间差的计算式很容易可以获得：（8）设常数π时刻，由此可得：QUOTEi=1n-1Ei，图2调度甘特图（2）总流程时间的计算方式通过了之前的计算，我们大致计算出了上文所提到的开工时间差。我们可以根据这些推论求得总流经时间的计算公式：（10）3.4本章小结针对这个课题，我们研究到这里，应该已经对它有了充分的理解，本章又详尽的描述了零等待流水车间的含义，基本概念，模型，优化指标以及计算方法，同时，也对优化指标进行了详细的阐述，便于读者理解，提供了相关的计算式，方便读者对此类问题进行更深入的研究。4求解调度问题的差分进化算法设计4.1引言通过对于相关问题的查阅，已经对内容进行了总结和收集，本章节我想通过用各种实际算例来验证差分进化算法（DE），要想通过实例来证明，我们就必须借助一些外力，对此我们打算使用c++语言来进行编程的编写，进一步实现算法设计。第二章中具体介绍了差分进化算法的含义，基本属性，特点以及运算方式和流程，我们将会在这个前提下，把差分进化算法进一步描述，用具体事例来进行证明，通过对算法的设计使读者更好的了解，并将算法的设计步骤及应用进行到具体的程序当中。4.2求解NWFSP问题的算法对于解决零等待流水车间总流程时间调度问题，我们上文一提到所规定的两个优化指标——最大完工时间()和总流经时间（），在这个基础之上在进行研究更加的得心用手。在这里我们要清楚，“如何用目标函数编码来实现这两个参数的优化目标”是我们首要思考的问题，而且在算法的过程当中，判断排列之间你是否可以相互取代也应该通过比较最大完成时间和总流经时间来实现的。当然，我们的宗旨是要用差分进化算法（DE）来解决全文所遇到的问题。通过使用差分进化算法解决零等待流水车间问题操作步骤如下所述：步骤1：最先进入种群初始化状态，获取Y个z维实数解向量。步骤2：计算出种群中每个个体的适应值，并一一进行判断，判断每个个体是否满足终止条件，若满足则输出最优结果，若不满足则进行以下操作。步骤3：将步骤2中不满足终止条件的个体进行变异操作，这个过程通俗来说就是把两个向量的向量差乘上变异算子，再与第三个向量相加得到新的变异向量。步骤4：为了增加干扰向量的多样性，我们选择引入交叉操作。这个过程中不可避免引入新变量CR，又名交叉算子。如果随机产生的数值小于CR或者与之相等,那么就将变异后的种群放入下面的操作当中，如果不是就将原来的种群放入接下来的操作当中。步骤5：选择操作很重要，它直接决定了种群中的向量是否能成为下一代的一员，这里需要注意的是试验向量只与一个个体进行比较，而不是所有个体。选择出的结果将再次进行是否满足终止条件的判断。图3流程图4.3算法具体部分的设计（1）初始化阶段对于整个过程最开始的阶段，初始排列是不可少的，我们可以通过差分进化算法（DE）来产生。接下来使用for循环计算出所有工件的加工时间，将他们用sumtime整理出来，使得数据清晰，结果明确，让人一眼便知结果。再次使用排列功能，以从大到小的排列次序将工件和加工时间依次排列清晰。把依次排好的排列放进一个new函数中，求取最终结果，从而得到初始排列。最终获得最优排列。（2）差分进化算法阶段经过了初始化阶段，我们需要通过差分进化算法解决零等待流水车间总流程时间的问题，下面将展示差分进化算法的步骤：{ 经过初始化阶段对变量进行优化，得到初始值，首先通过for循环计算出所有工件的加工时间，保证所有工件加工完毕，用冒泡序列对其进行处理，就可以得到初始调度向量。for((j=0;j<product-1;j++){for(k=2;k<=machine;k++){for(h=2;h<=k;h++){比较temp与temp3值的大小关系可得=0，再次进行for循环}}得到该运算过程中的最大完成时间}将所得结果重复上述for循环可得cmax+=d.at(j)*(product-2-j)获得总流程时间}4.4本章小结 本章当中算法设计这部分是很难理解的一个难点，它非常考验逻辑思维的转换能力。在这里我们也把前两章的内容也进行了充分地联合，希望便于读者的理解，对于算法设计的整体思想，以及算法设计的步骤，流程，我们可以去网络上查看周刊，进一步理解。本章的最后我们对分析的结果进行了简单地解释。5仿真实验与结果分析5.1引言上文中已经提到过具体事例，那么第五章将会把这几个典型的算例一一进行测试。我们所使用的仿真系统——内存为8G，Win10的操作系统，所用到的仿真软件——VisualC++6.0。经过对多组数据结果的分析和探究，求出最优解，然后通过matlab画出甘特图，方便我们更清楚的得出结论。5.2算例介绍零等待流水车间总流程时间调度问题可以说成另外一个问题，因为所有的算例都是围绕一个问题展开的，经过研究发现此类调度问题一般情况下都是用“x个工件要在y台机器上加工”来描述的，当然我们也可以这样理解——每个工件都有y道工序进行加工。这里需要特别注意每个工件要在不同的机器上进行加工，我们现在所研究的问题，其主要目标就是确定每台机器上面工件的加工次序和开工时间，我们只有求解出此数值才能实现最终目标——获得最优实数解。当我们探究零等待流水车间这类问题时，我们必不可少的一个步骤——仿真实验，那我们拿什么来做仿真实验呢？这里就会引出本节重中之重的内容——仿真算例的介绍。仿真算例大家都不会陌生，最为经典的la问题和abz问题应该也在很多文献上看到过，对此我们就不多做介绍。经过大量的实验研究，以及翻阅书籍和文献，我们可以从中得知，这些算例得出了一些参考和值。实际生活中的算例都包含着大量的数据，每一个算例就相当于一个小数据库，如果一一来计算，不管是时间上，还是统计性能问题上，都是很难实现的，所以在第五章中我将会选取其中的3组数据进行运算处理，分别为la10、abz5、la25，这两组算例中的工件在设备上的处理时间如表1、表2、表3所示。其中表示第i个工件，表示第j台设备。表1算例la10的加工时间G1G2G3G4G5H158449866H28997967784H37788813989H45721311573H54840497071H63482801233H7917555179H86247733511H96475509094H106720171271H115293682966H12705893777H1327826310103H148756362648H157632361512表2算例abz5的加工时间G1G2G3G4G527357747696H38668866766H491646210155H56988819993H64798646781H75888999796H89765835272H99488828667H105098816857表3算例la25的加工时间G1G2G3G4G5H11676173977H23983865989H36681454917H44486972260H55673764338H68071325274H79765782292H88986646168H94477124531H10632485333H112050771118H128573726076H131588143740H143291348388H1598702839925.3算例仿真上述三组数据abz5、la10、la25是我们从数据库中选取出来的，机器数和工件数都比较少，容易计算和绘制甘特图。我们将对这三组算例分别进行以总流程时间为指标的仿真实验。首先对abz5进行仿真实验，由于该组数据中工件数较少，我们使用C++程序即可得出结果，最优解如表4所示。表4abz5算例仿真运行结果次数最优序列最优解1[74196281053]2170观察该组仿真结果，我们进行分析和比较，可以得到最优总流程时间为2170，相对应的最优工序为[74196281053]，我们将仿真所得到的的结果用甘特图的形式展示出来。图4abz5算例最优工序仿真甘特图然后我们对la10算例进行仿真实验和甘特图的绘制，所的结果如表4，图5所示。表4la10算例仿真运行结果次数最优序列最优解1[654139711015811122314]1290通过以上结果我们可以得出该算例的最优总流程时间为1290，最优序列为[654139711015811122314]，根据这些我们绘制出甘特图。图5la10算例最优工序仿真甘特图最后我们将la25算例进行仿真实验和甘特图的绘制