《制造执行系统实施与应用》 课件 3.2生产优化调度技术

制造执行系统(MES)实施与应用3.2生产优化调度技术【学习目标】1.理解生产调度的定义2.了解生产调度问题的不同类型和分类方法3.理解作业车间调度问题（JSP）4.掌握生产调度问题的基本数学模型5.了解不同的生产优化调度技术，以及它们在解决生产调度问题中的应用【重点和难点】重点：1.生产调度问题的数学模型，理解作业车间调度问题（JSP）的整数规划模型、线性规划模型和析取图模型2.人工智能算法的应用，学习如何将人工智能算法，尤其是遗传算法和禁忌搜索算法，应用于生产调度问题的求解3.2生产优化调度技术难点：1.调度问题的复杂性，生产调度问题通常涉及多个目标和约束条件，理解并处理这种复杂性是学习中的一个难点。【职业素养】1.具有持续改进的意识，能够根据生产实际情况，不断调整和优化生产调度策略2.能够运用创造性和批判性思维，面对生产过程中的调度问题，提出有效的解决方案3.培养在生产活动中实现可持续发展的意识，在调度优化中考虑环境影响和社会责任3.2生产优化调度技术最优化算法最优求解方法主要是通过对作业车间调度问题建立一个整数规划模型，采用基于枚举思想的分支定界法或线性规划法等来解决调度最优化或近优化问题。分枝定界法分枝定界法通过动态树结构搜索可行解空间，树的分支代表需搜索的解，路径表示工序顺序。算法从根节点开始，通过启发式方法获得上界，然后根据上界进行分支定界，舍弃超过上界的分支以缩小搜索空间。该方法对初始上界敏感，且主要适用于小规模调度问题，对实际问题敏感性限制了其应用。研究重点在于改进分枝和定界策略，以提高排除规则的效率。3.2生产优化调度技术线性规划法线性规划法是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。它将调度优化目标和各种约束条件表示为线性等式或不等式，通过求解线性规划问题达到求解调度的目的。理论上，只要问题的最优解存在，就能找到最优解。但由于调度问题所涉及的约束关系数量过大，实际运用中受到“组合爆炸”问题的困扰，因而不能获得真正的实用拉格朗日松弛法拉格朗日松弛法用非负拉格朗日乘子将工艺约束和资源约束进行松弛，最后将惩罚函数引入目标函数中。分枝定界法的主要问题是整数约束，为了解决这个问题，产生了拉格朗日松弛法，它删除了整数约束而加入了相应的代价。但是，与分枝定界法相比，拉格朗日松弛法更加耗时。3.2生产优化调度技术(1)优先分派规则优先分派规则是最早的近似算法，它给所有的被加工工序分配优先权，然后选出优先权最高的加工工序最先排序，接下来按优先权次序依次进行排序。这种方法非常容易实施，并且计算负担较低。优先规则有很多种，Panwalkar等人在1977年归纳了100多个优先规则，其中最主要的有优先选择加工时间最短工序的SPT(shortestprocessingtime)规则、先来先服务FCFS(firstcomefirstserve)规则、优先选择剩余加工时间最长作业的MWR(mostworkremaining)规则、优先选择剩余加工时间最短作业的LWR(leastworkremaining)规则和随机挑选RANDOM(randomselection)规则。表3-1包含了实际中常用的一些分派规则构造方法近似求解方法3.2生产优化调度技术表3-1常用优先分派规则列表规则全称描述SPTshortestprocessingtime先选择最短加工时间的工序LPTlongestprocessingtime优先选择最长加工时间的工序FCFSMWRfirstcomefirstservemostworkremaining选择同一机床上零件队列中最先到达的工序优先选择剩余总加工时间最长的零件的工序LWRleastworkremaining优先选择剩余总加工时间最短的零件的工序WSPTWeightedshortestprocessingtime优先选择最短加工时间的工序（考虑权重）EDDearliestduedate优先选择具有最早交货期的零件MSminimumslack优先选择具有最少迟缓时间的工序MORmostoperationremaining优先选择剩余工序数最多的零件的工序LOReastoperationremaining优先选择剩余工序数最少的零件的工序SOTshortestoperationtime优先选择加工时间最短的工序LOTlongestoperationtime优先选择加工时间最长的工序RANDOMrandomselection随机选择加工工序移动瓶颈算法移动瓶颈算法工作的特点是子问题的识别、瓶颈选择、子问题的解、排序重新最优化。移动瓶颈对瓶颈机器排序，留下被忽视的未被排序的机器，固定已经排序的机器。当每次瓶颈机器排序后，每个先前被排定的有接受改进能力的机器，通过解决单一机器问题方法，再次被局部重新最优化。而单一机器问题的排序是用Carlier的方法通过迭代来解决的，这个方法可以快速给出一个精确的解。移动瓶颈方法的主要贡献是提供了一种用不断转换的单一机器排序来确定一个优化调度的方法。3.2生产优化调度技术

启发式方法(1)局部搜索局部搜索包括模拟退火、禁忌搜索、混沌搜索、多起点局部搜索等。①模拟退火。模拟退火算法是一种受物理退火过程启发的随机优化技术，用于解决NP复杂性问题。它通过模拟物质冷却过程中的随机运动来避免陷入局部最优解，具有全局搜索能力。算法的核心在于控制“温度”下降的过程，以平衡探索和利用。模拟退火已广泛应用于生产调度、机器学习等领域，能有效解决传统方法难以处理的优化问题。②禁忌搜索。禁忌搜索(TabuSearch，TS)是一种现代启发式算法，由美国科罗拉多大学教授FredGlover在1986年左右提出的，是一个用来跳脱局部最优解的搜索方法。它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。3.2生产优化调度技术

(2)人工智能AI利用知识表达技术把人的知识包括进去，同时使用各种搜索技术求得一个令人满意的调度问题解。它把调度过程描述成一个在满足约束的解空间中搜索的过程。人工智能包括神经网络(neuralnetwork)、遗传算法(geneticalgorithm)、粒子群优化(particleswarmoptimization)、蚁群算法(antcolonyalgorithms)、禁忌搜索(tabuSearch)和模糊逻辑(fuzzylogic)等。1、神经网络。神经网络是一种模仿人脑结构和功能的计算模型，用于解决调度问题。尽管它们能并行处理信息，但因调度问题变量和约束众多，导致计算量大，容易陷入局部最优解。神经网络通过学习输入特征（如零件种类、加工时间等）和输出（如调度规则和评价指标）来预测调度方案。然而，由于涉及变量众多，这些方法计算效率低，且可能产生不可行的调度方案，限制了其在实际调度问题中的应用。

启发式方法3.2生产优化调度技术

(2)人工智能2、蚁群算法。蚁群算法是Dorigo等人在1996年提出的一种模拟进化算法，通过模拟自然界中真实的蚂蚁搜索食物源的行为来求解组合优化问题，并取得了一定的效果。蚁群算法的主要缺点是收敛速度慢。实践证明，信息素初始阶段的积累是影响蚁群算法收敛速度的关键因素之一。3、模糊逻辑。模糊逻辑理论一般用在混合调度方法中。它主要用来解决车间调度问题中不确定的加工时间、约束和辅助时间。这些不确定性可以用模糊数据表示。

启发式方法3.2生产优化调度技术步骤1初始化产生个可行解，为种群规模。步骤2计算个体适应度值，评价个体适应度。步骤3判断是否达到终止条件，若满足，则输出搜索解，否则转步骤4。步骤4按选择策略选择下一代种群规模。步骤5按交叉概率执行交叉操作。步骤5按变异概率执行变异操作。步骤6产生新一代种群，返回步骤2。遗传算法3.2生产优化调度技术遗传算法通过模拟自然进化过程来寻找所求问题的答案，区别于传统的搜索方法，具有以下特点：(1)遗传算法是对问题的编码“染色体”进行进化操作，对搜索问题的限制极少，这使得遗传算法不受函数约束条件，如连续性、可导性等的限制。(2)遗传算法同时对解空间内的一群解进行搜索，并且具有隐含并行搜索特性，因而能有效地防止收敛到局部最优解，并可能获得全局最优解。(3)遗传算法使用个体目标函数的适应度值信息和遗传操作按概率在解空间进行搜索，因而与随机或穷举搜索方法不同，是一种有目标、有方向的启发式搜索方法。遗传算法3.2生产优化调度技术车间调度问题描述在作业车间中有一批待加工工件，这批待加工工件中有个不同的工件，每个工件均包含多道工序，需要在台机器上加工。加工这批工件需要同时满足以下几点约束条件：(1)所有工件的工序之间都有顺序约束，同一工件的各工序间有先后顺序，需按照工序顺序进行加工；(2)不同工件的加工工序之间没有顺序约束；(3)每道工序只能在一台机器上加工；(4)各工件工序的加工时间由对应的加工机器确定；(5)在同一时刻车间中的同一机器只能加工一道工序；(6)一道工序同一时刻只能在一台机器上加工，且不能中途中断；(7)不同工件之间优先级是相同的；(8)不考虑机器故障等随机性因素。遗传算法求解JSP实例3.2生产优化调度技术本节求解目标为已知每台机器上工序的加工顺序和每个工序的开工时间，使得最大完工时间最小，目标函数和约束条件中的公示所示。本节提出一种改进后的遗传算法来解决作业车间调度问题。改进后的遗传算法在初始化时能够适当扩大种群，在迭代过程中运用更易区分染色体的适应度函数计算染色体的适应度值，并且运用能够自适应改变交叉和变异概率的算子调整概率值。实验结果表明改进后的遗传算法更适用于作业车间调度。遗传算法求解JSP实例车间调度问题描述3.2生产优化调度技术遗传算法设计染色体编码遗传算法的基因编码方式有很多种，如浮点数编码、二进制编码、整数编码、符号编码、矩阵编码等。基因编码在算法中起着至关重要的作用，编码的方式直接影响遗传算法的运行速度以及能否找到全局最优解。这里采用基于工序的实数编码来表示染色体，一个编码后的染色体代表一个车间调度问题的调度方案。对于个不同工件在台机器上加工的作业车间调度问题，采用基于工序的编码方式编码后，每条染色体均含有个基因，染色体的基因顺序对应所有工件工序的加工顺序，即一条染色体代表一个车间调度问题的调度方案。遗传算法求解JSP实例3.2生产优化调度技术遗传算法设计染色体编码对于n个不同工件在m台机器上加工的作业车间调度问题，采用基于工序的编码方式编码后，每条染色体均含有n×m个基因，染色体的基因顺序对应所有工件工序的加工顺序，即一条染色体代表一个车间调度问题的调度方案。每条染色体的基因表示如下：每个工件号在染色体中只能出现m次；从染色体的第一个基因位到最后一个基因位依次遍历，若同一工件号出现第k次则表示为此工件的第k道工序,如染色体[332121]，其中第一个3代表3号工件的第一道工序，第二个3代表3号工件的第二道工序，以此类推。遗传算法求解JSP实例3.2生产优化调度技术种群初始化先给定种群的初始值p；然后根据作业车间一道工序只在一台机器上加工的特点，生成一个有个n×m基因的染色体；最后调用randperm函数处理生成的染色体，使其循环p次，得到一个初始种群数处理生成的染色体，使其循环p次，得到一个初始种群。遗传算法求解JSP实例遗传算法设计3.2生产优化调度技术染色体适应度值优化目标是最小化最大完成时间，因此最大完成时间越小的染色体越优良。染色体的适应度值是用来区分染色体间的优劣程度，染色体越优良适应度值越大，被选中的概率越大，染色体越差适应度值越低，被选中的概率越低。假设现有4个工件，其加工完成时间分别为[20,21,22,23]，取最大完成时间倒数方法得到的适应度值分别为[0.05,0.0476,0.0454,0.0425]，算法得到的适应度值分别为[1,0.6308,0.2923,0]。从这两组适应度值可看出，这样设定适应度值可以让最大完成时间小的染色体被多次选择，最大完成时间最大的染色体被少选择或者不被选择，拉开了染色体间差距,保障了对优良染色体的选择。适应度函数如式(3-4)所示,最大完工时间的倒数如式(3-5)所示:遗传算法设计遗传算法求解JSP实例3.2生产优化调度技术染色体适应度值(3-4)(3-5)式(3-4)、式(3-5)中,i为初始种群中的任意一条染色体，Max表示的最大值，Min表示h(i)的最小值。在确定好各染色体的适应度值后在采用轮盘赌的方法选择初始种群中的染色体。遗传算法设计遗传算法求解JSP实例3.2生产优化调度技术交叉与变异交叉操作可以增加种群的多样性，提高算法的搜索能力，有利于产生优秀的染色体，即有利于产生优秀的作业车间调度方案。鉴于优先工序交叉法POX(PrecedenceOperationCrossover)能够很好地继承父代优良特征并且子代总是可行的这一特点，这里选择POX进行交叉操作，具体步骤如下所述：遗传算法求解JSP实例遗传算法设计3.2生产优化调度技术步骤1.按顺序依次选择种群中的一条染色体作为父代1即Parent1，随机选择种群中的一条染色体作为父代2即Parent2；步骤2.将工件集{1,2,3,…,n}随机划分为两个非空子集j1,j2；步骤3.将Parent1和Parent2中包含j1={2}工件号分别按其在染色体中的位置复制到子代1即Children1和子代2即Children2中，将Parent1和Parent2中包含j1={2}工件号分别按其在染色体中的顺序复制到Children2和Children1中；Children1和Children2这两条染色体即为交叉后的染色体。如Parent1={3,2,2,3,1,1},Parent2={1,1,3,2,2,3}，对工件集{1,2,3}随机划分生成j1={2}，j2={3,1}，经过POX交叉后得到Children1={1,2,2,1,3,3}，Children2={3,3,1,2,2,1}。遗传算法求解JSP实例遗传算法设计交叉与变异3.2生产优化调度技术遗传算法求解JSP实例遗传算法设计交叉与变异变异操作是小概率发生的，它能够对染色体产生较小的扰动来增加种群的多样性，从而产生更能满足目标函数要求的调度方案。交叉后的染色体在进行小概率的变异操作,可得到新的染色体,保持种群多样性。为了保证新得到的染色体编码是可调度的,避免将不可行调度转换成可行调度，减少代码运行时间，，采用互换法(ReciprocalExchangeMutation,REM)进行变异操作。对一个染色体随机选择两个基因号，将两个基因号上对应的工件号进行互换，循环i次后可得到变异后的染色体。3.2生产优化调度技术交叉和变异概率影响着交叉操作和变异操作的发生，当交叉和变异概率大于由rand函数在(0,1)之间随机产生的值时，染色体发生交叉变异。标准遗传算法的交叉和变异概率通常都是固定不变的值，一般根据前人经验给定或者根据实验结果给定，当给定的值较小时会使搜索范围变小，不利于寻找更优解；而当给定值较大时则可能导致已有的优良染色体在交叉和变异操作后变差；在实验中容易出现早熟问题，即未成熟收敛。这里确定交叉和变异概率值时采用文献提出的自适应改变交叉和变异概率的方法,该算法能够在种群进化初期提高进化能力,降低陷入局部最优的风险,避免早熟问题的出现,解决了参数难以确定的问题.自适应交叉概率函数如式(3-6)所示,自适应变异概率函数如式(3-7)所示:遗传算法求解JSP实例遗传算法设计交叉与变异概率3.2生产优化调度技术式(3-6)、式(3-7)中，

表示当前种群中所有染色体的最大适应度值；

表示当前种群中所有染色体的平均适应度值;

为两个交叉染色体中适应度值较大的值；表示选中的变异染色体的适应度值。算法中

，

，

，

的值在范围中选择即可。遗传算法求解JSP实例遗传算法设计交叉与变异概率3.2生产优化调度技术仿真实验程序运行的软件为Matlab_R2018a，用遗传算法分别对测试用例库中的FT06和LA01这两个用例进行实验。FT06是一个6×6的测试用例，即共有6个工件，每个工件都有6个加工工序，FT06的工件工序集J=[3,1,2,4,6,5；2,3,5,6,1,4；3,4,6,1,2,5；2,1,3,4,5,6；3,2,5,6,1,4；2,4,6,1,5,3]；加工FT06各个工序所需时间集T=[1,3,6,7,3,6；8,5,10,10,10,4；5,4,8,9,1,7；5,5,5,3,8,9；9,3,5,4,3,1；3,3,9,10,4,1]；LA01是一个10×5的测试用例，即共有10个工件,每个工件都有5个加工工序，LA01的工件工序集J=[2,1,5,4,3；1,4,5,3,2；4,5,2,3,1；2,1,5,3,4；1,4,3,2,5；2,3,5,1,4；4,5,2,3,1；3,1,2,4,5；4,2,5,1,3；5,4,3,2,1]；加工LA01各个工序所需时间集T=[21,53,95,55,34；21,52,16,26,71；39,98,42,31,12；77,55,79,66,77；83,34,64,19,37；54,43,79,92,62；69,77,87,87,93；38,60,41,24,83；17,49,25,44,98；77,79,43,75,96]。遗传算法求解JSP实例算法输出结果3.2生产优化调度技术遗传算法参数设置为：迭代次数为200，种群总大小为100，在初始化时将种群总大小扩大为原来的2倍，以增加染色体的多样性，算法中交叉和变异概率是自适应调节的，无需直接指定，k1=k2=0.9,k3=k4=0.1。用FT06基准案例验证时，遗传算法求得的最优解为55，20次实验中有12次求得55，所得解均值为56.2，当求得最优解为55时，最优迭代次数为10，平均迭代次数为38.05；用LA01基准案例验证时，遗传算法求得的最优解为666，20次实验中有14次求得最优解，最优解平均值为671.3，当求得最优解为666时，最优迭代次数为18，平均迭代次数为76.6。遗传算法求解JSP实例算法输出结果

仿真实验3.2生产优化调度技术用FT06和LA01验证遗传算法，生成的遗传代数图和甘特图分别如图3-4~图3-7所示。由图3-5可知每台机器上的工序顺序，以及加工完所有工件花费的最少加工时间55，由图3-4可知得到此调度方案只迭代了10次；由图3-7可知每台机器上的工序顺序，以及加工完所有工件花费的最少加工时间666，由图3-6可知得到此调度方案只迭代了18次。图3-4FT06遗传代数图图3-5FT06甘特图图3-6LA01遗传代数图图3-7LA01甘特图遗传算法求解JSP实例算法输出结果

仿真实验3.2生产优化调度技术仿真结果表明改进后的遗传算法比标准遗传算法收敛速度快，所得解更稳定，遗传参数较易确定。该遗传算法的收敛速度快，交叉和变异概率采用自适应交叉、变异函数确定，解决了参数难以确定的问题，证实了该遗传算法的有效性和可靠性。图3-4FT06遗传代数图图3-5FT06甘特图图3-6LA01遗传代数图图3-7LA01甘特图遗传算法求解JSP实例算法输出结果

仿真实验3.2生产优化调度技术遗传算法有着很强的并行性和全局寻优能力，但也有收敛速度慢、局部寻优能力较差等缺点，而禁忌搜索算法等一些启发式搜索算法则具有较强的局部搜索能力。结合不同算法的寻优思想对遗传算法进行改进，如在遗传框架内加入禁忌搜索操作可以提高算法的运行效率和求解质量。下面我们介绍基于遗传与禁忌搜索混合算法求解作业车间调度问题。遗传算法求解JSP实例3.2生产优化调度技术禁忌搜索算法已经被有效地用于求解多种车间调度问题。该算法的特点是采用禁忌表来避免个体陷入局部最优。如果某一个体被禁忌表所禁止，那么它就不能被选为新解进入下一代。禁忌搜索算法包含以下几种元素：邻域结构、移动属性、禁忌表、特赦准则和终止条件。本节所采用的邻域结构是N7邻域结构。移动属性指工序间的移动操作。禁忌表用来禁止重复的移动操作。特赦准则是指当新解的Makespan比当前最优解更小时，即使新解的移动操作被禁止，仍然接受。终止条件是指当新解的Makespan达到了下界或算法到达了给定的迭代次数，则算法终止。遗传算法求解JSP实例禁忌搜索算法设计3.2生产优化调度技术禁忌搜索算法的流程如下：步骤1

随机产生一个候选解

，并设置当前最优解

。步骤2

设置禁忌表

为。步骤3

基于N7邻域结构产生

的多个邻域解，并选择Makespan最小且没有被禁忌，或满足特赦准则的解为

。步骤4

如果

优于

，设置

；同时设置

。步骤5

更新禁忌表

。步骤6

判断是否达到终止条件，

若满足则输出最优解，结束算法；否则转步骤3。遗传算法求解JSP实例禁忌搜索算法设计3.2生产优化调度技术遗传与禁忌搜索混合算法将“适者生存”的进化准则融入多起点禁忌搜索算法中，由遗传算法和对初始化及进化过程中产生的个体进行优化的强化禁忌搜索算法组成。从总体上分析，遗传算法用于执行全局探索，而强化禁忌搜索算法用于对有希望的区域进行集中搜索（局部探索）。由于遗传算法和禁忌搜索算法具有互补的特性，混合算法能够超越这两种算法单独使用。遗传算法求解JSP实例混合算法的框架设计3.2生产优化调度技术求解JSP问题的遗传与禁忌搜索混合算法流程如下：步骤1

种群初始化并设代数

。步骤2

对种群适应度值进行评估。步骤3

判断是否满足终止条件？满足则跳转至步骤6；否则跳转至步骤4。步骤4

更新种群：首先使用遗传算子（选择、交叉和变异）更新种群；然后对种群中每个个体使用禁忌搜索操作提高解的质量。步骤5

设，并返回步骤2。