英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
基于混合粒子群算法的铸造生产调度优化
1、摘要
铸造车间调度是指生产过程中的热工序不能在两个连续的工序之间等待，可以被建模为无等待约束的流水车间调度问题。以减少总流程时间为目标，选择合适的作业序列进行调度是必不可少的，因此该问题可以看作是典型的NP-hard组合优化问题。针对铸造企业客户需求的不断变化和存在的约束条件，提出了粒子群优化与模拟退火相结合的方法来解决复杂的计划调度问题。提出了一种混合粒子群算法，该算法利用随机密钥表示规则来表示解，将粒子的连续位置信息值转化为离散的作业排列。提出的混合粒子群优化算法利用Nawaz-Enscore-Ham启发式算法有效地初始化种群，采用PSO机制引导的进化搜索和模拟退火机制的局部搜索，兼顾全局搜索和局部开发。提出的混合粒子群优化算法考虑铸造环境，试图弥补理论与实际的差距，这将有助于规划师根据客户的订单来决定作业的生产顺序，并开发高效的调度程序，以在相对较低的计算工作量下最小化总流程时间。根据铸件的工作特点，进行了大量的计算实验。铸造类型、模具尺寸和合金类型，其中工件尺寸（n）被视为10、12、20、50和100。在性能指标、平均相对偏差等方面，该方法优于模拟退火算法和粒子群算法。
介绍
在任何类型的生产环境中，作业的计划和调度是决定市场竞争地位的首要因素。本文以铸造厂为例，研究如何在指定的机器上，以最小化总流程时间为目标，找出有效的生产计划。铸造企业的生产过程是一个复杂的过程，各种物理化学变化同时发生[1]。因此，为了保证生产目标的完成，合理的生产计划和稳定的生产运行是铸造企业的重要组成部分。任何金属工业的铸造环境都有一个多阶段的过程，其中熔化的金属通过吹炼炉、加热炉和轧机的过程依次转化为产品[2]。很明显，这代表了流水车间的一个典型模型，其中每一个作业都由每台机器按固定顺序处理。此外，铸造车间是一个没有等待约束的流动车间，在这种生产类型中，过程中的热加工不能在两个连续操作之间等待。。此外，由于铸造过程中工件的尺寸较大，两台连续机之间缓冲区的存储容量有限，因此应减少过程库存。因此，为了减少在制品库存，应减少工件的总流动时间。这通常也被视为具有资源约束的无等待进程需求[3]。为了响应这一要求，本文以最小化总流程时间（TFT）为优化准则，它决定了每台机器上单个作业的总处理时间。以TFT为目标的无等待流水车间的研究对任何金属制造业都是合理有效的。
本文的其余部分安排如下。第二节介绍铸造生产工艺。第3节正式定义和制定了NWFSSP。第4节描述了元启发式算法PSO和SA以及实现所提出的元启发式算法的详细过程。第五节对所提出的算法在铸造环境下的性能进行了实证评估，并与目前为止最好的算法进行了性能比较。最后，在第6节中作了总结发言。
铸造企业主要生产工艺
考虑的工厂生产各种材料组合的铸造产品。根据客户订单生产的铸件有多种尺寸和不同材料（合金）组合。合金的类型决定了力学性能，如抗拉强度、抗压强度、断裂剪切模量、拉伸弹性模量、扭转弹性模量、耐久极限、硬度、价格等。铸件是用各种尺寸的模具生产的，但模具的数量和类型都不受限制。每个模具都填充了一种单一类型的熔融金属（铁/有色金属）。客户订单确定了一组必须在此系统中处理的生产作业。每项工作都对应一种合金和模具类型，它们必须以典型的顺序经历连续的阶段完成。铸造厂是一个流水线生产系统，其中操作顺序是固定的，工作流是单向的。第一步是根据计划订单，使用模板制备模具/型芯。在第二阶段，熔化的金属从熔炉倒入梯子，然后倒入允许冷却的模具中。随后，将铸件从模具中取出，然后进行喷丸处理以进一步进行精加工。然后，对成品铸件进行分组、贮存和热处理。热处理后的铸件经过修整和精加工，然后进行检验并发送给客户。图1给出了铸造厂操作的典型工艺顺序。
在铸造过程中，每个阶段都被视为一台机器。所有铸件（工件）以相同的工艺顺序通过所有9个阶段[3]，每个阶段都有规定的工件加工时间。由于工艺要求，铸件不能在熔化和浇注之间等待。为了合理利用炉子，在制品库存（WIP）应最少。准备熔融金属的时间和热处理的时间在很大程度上取决于用于生产典型铸件的合金类型。在第二和第三阶段假设的加工时间不能改变，因为为了保持加热或冷却的温度，准备好的铸件在工艺过程的第四阶段既不能太软也不能太硬而导致无法切割[4]。
2
无等待
3
4
不等待资源约束
9
8
7
6
5
1
客户订单和原材料
将熔化的金属从炉子倒入梯子
将熔化的金属从梯子倒入保持冷却的模具
模具中熔融金属的硬化
模具上的针织铸件
铸件抛丸
抛丸铸件完成
成品铸件热处理
铸件的成形和精加工过程
成品铸件质量控制检验
将检查过的铸件运往
图1 铸造厂操作的技术顺序
10
最常被考虑的优化标准之一就是确定一个最基本生产计划，使最大作业完成时间最小化。
3、问题定义
客户随机提交具有特定项目类型、数量和合金的订单，这将导致任何铸造厂产品的高度多样性。因此，在生产开始之前，很难用精确的方法、合理的计算时间来安排任务。因此，为了解决这类问题，提出了元启发式算法[5]。在这里，我们从使用经典的无等待流水车间调度（NWFSS）概念建立的数学模型开始。生产任务是由一组工件{J1，J2，hellip;.Jn}来完成的，这些工件代表了生产特定尺寸铸件所需浇注到模具中的合金要求。生产系统由机器序列{M1，M2，hellip;.Mm}组成，附加的约束是不等待，因为作业不能在任何阶段的中间等待。设={1，2。n}表示要在“m”机器上处理的“n”个作业的序列，（i，s）表示作业i开始和作业s开始之间第一台机器上的最小延迟。此外，让p（i，j）表示给定序列的第i个位置处作业j机器上的处理时间，让（i-1，i）表示在序列的第（i-1）个和第（i）个位置发现的两个连续作业开始之间的第一台机器上的最小延迟。设C（i）为给定序列第i个位置的作业完成时间。
For i = 1,2,. . . ,n and j = 1,2,. . . ,m
总流动时间（TFT）的公式如下：
n x n的延迟矩阵提供给定n个作业序列中任意两个连续作业i和k（ine;k）的开始之间的所有delta;（i，k）值，以确定目标函数值。由（7）得到的delta;（i，k）值的延迟矩阵
对于给定的矩阵大小n(作业）x m（机器）与处理时间?P?[i，j]生成（n！）选择最优序列（sigma;*）的可行解序列（sigma;）的个数，可按（8）表示
F (*) le; F (); forall; isin; (8)
问题是确定n个作业的序列，使该序列得到的总流动时间最小。
4、提出混合粒子群算法（PHPSO）
尽管元启发式方法在科学界和工业界应用于组合优化问题的领域正在迅速发展[7]；但是元启发式方法在解决组合优化问题上的应用起步较晚。Bewoor等人[8]，[9]对各种元启发式算法的比较分析提倡PSO的有效性。最近的过去见证了显著的转变，向混合启发式优化[10]。本文的工作还展示了混合元启发式技术在解决铸造环境中观察到的实际生产调度问题中的应用。
4.1粒子群优化算法
PSO是一种优化算法，它模拟了在一个特定区域寻找食物的鸟群的生物学例子[6]。在给定的搜索空间中，鸟类遵循最接近食物的策略来搜索食物，而粒子群优化算法正好适应这种策略来搜索最优解向量。一个单一的解称为粒子，它的适应值由函数求最小，每个粒子的速度指示粒子的飞行。该算法先用随机位置的粒子进行初始化，然后探索搜索空间寻找更好的解。在每次迭代中，每个粒子都会调整其速度以遵循两个最佳解。第一个是认知部分，粒子遵循它自己的最佳解，称为pbest，另一个是swarm当前的最佳解，称为gbest。在NWFSS环境中，每个粒子从其邻域中的最佳粒子学习，从而更容易适应变化的环境。（9）和（10）中给出的用Vnew表示的新速度和用Xnew表示的新位置。
其中，w是惯性权重，它在本地和全局搜索能力之间提供平衡。加速度常数c1和c2在（9）中分别是发展鸟类自身自信（认知行为）和群体自信（社会行为）的认知参数。低值允许粒子在被拖回之前远离目标区域漫游，而高值会导致粒子从目标区域突然移动。本文将加速度常数c1和c2分别设为1.65和1.75。r1和r2是[0,1]之间的偶数分布随机数。本文将r1和r2分别设置为0.5。Xnew和Vnew分别是粒子的新位置和速度，Xcurr和Vcurr分别是粒子的当前位置和速度。在标准粒子群优化算法中，考虑到粒子的前一速度和当前位置与自身最佳历史位置和邻域最佳位置的距离，通过（9）找到粒子的新速度。通常，速度中每个分量的值设置为范围（Vmax，-Vmax），以控制粒子在搜索空间外的过度漫游。在这个新的速度下，粒子按照（10）移动到一个新的位置。重复此过程，直到达到用户定义的停止标准。
4.2解的表示
解的表示是PSO算法设计中最重要的问题之一。通常，基于作业排列的编码方案在许多论文中都有广泛的应用。然而，由于粒子群算法中粒子位置的连续性，使得粒子群算法不能直接采用标准的编码方案。为了在NWFSS的问题域和PSO粒子之间建立一个直接的关系，对n个作业给出了n个维数。每个维度代表一个典型的作业，粒子Xi={x1，x2，x3，hellip;.xn）对应于NWFSS中n个作业的连续位置值。粒子本身不呈现排列。因此，在粒子群优化算法中，需要找到合适的作业序列与粒子位置之间的映射，因此，本文采用基于随机键值[11]的排序序值（ROV）规则来确定粒子Xi的位置值xij所隐含的排列。ROV规则将连续位置值转化为离散的作业排列，这是连续PSO算法应用于排序问题的关键，从而可以评估粒子的性能。特别地，表示为Xi={x1，x2，hellip;..xn}的粒子的位置信息本身并不表示序列，而粒子的每个位置值的秩表示作业索引，作业索引可用于构造作业的排列。在我们的ROV规则中，首先对位置值最小的粒子进行处理，并赋予其最小的秩值1。如果在基于粒子群优化的搜索过程中存在两个或多个位置值相同的粒子，则对维数较小或最小的位置值赋予秩值1。其余位置值的秩值随维数的增加递增1。然后，以同样的方式处理第二个最小的位置值。注意，如果存在k个相同的最小位置值，则具有最小维度的第二个最小位置值的秩值应为k 1。同样，所有的位置值都将被处理，以便将粒子的位置信息转换为作业置换pi;ij=[j1，j2，j3hellip;jn]。
4.3族群初始化
在标准粒子群算法中，初始的群生成往往是随机的。为了提供有效的解决方案，必须生成具有一定质量和多样性的初始种群。本文提出了一种基于NEH启发式的族群初始化方法。NEH启发式有两个阶段。在第一阶段中，作业的顺序是它们的总流动时间的升序和。在第二阶段中，通过基于第一阶段的初始顺序评估部分调度来建立作业序列。假设已经为前k个作业确定了当前序列，则通过在当前序列的k 1可能时隙中插入作业k 1来构造k 1部分序列。在这个k 1序列中，生成最小总流动时间的序列保持为下一次迭代的当前序列。然后考虑第一阶段的作业k 2，依此类推，直到所有作业都已排序。
4.4基于模拟退火（SA）的局部搜索
退火是冶金中的一个过程，在这个过程中，金属被缓慢冷却，使其达到一种低能状态，在这种状态下金属非常强[13]。当应用于工程设计时，将能量与目标函数进行类比。这个设计是在一个高“温度”下开始的，在那里它有一个很高的目标。然后对设计进行随机扰动。如果目标较低，则新设计为当前设计；如果目标较高，则仍可以根据（11）中给出的玻尔兹曼系数给出的概率接受。
式中，alpha;是玻尔兹曼常数，T是当前温度prod;E是能量变化。玻尔兹曼概率与从0和1之间的均匀分布中得出的随机数进行比较；如果随机数小于玻尔兹曼概率，则接受该配置。这使得算法能够避开局部极小值。适当的初始温度应该足够高，这样系统的所有状态都有相等的被访问的概率。本文将初始温度设为3.0，最终温度设为0.9，alpha;为0.99分。
4.5混合粒子群算法的计算过程
基于ROV规则的解表示、基于NEH的局部搜索的种群初始化和基于SA的局部搜索的邻域搜索，PHPSO根据以上提出的NWFSS混合PSO框架的完整计算过程可以总结如下：
算法：PHPSO算法在铸造中的应用
步骤1：对于铸造环境，根据客户需要的合金生产数据被视为生产的“作业”（n） 步骤2：铸造生产过程遵循的工艺顺序要求使用“m”型机器。这里m=8。 步骤3：输入每台机器上每个作业所需的处理时间，以查找作业序列，以最小化总完成 时间（makespan）。
步骤4：利用NEH算法生成初始种群。采用排序序值（ROV）算法将连续粒子位置转换为离散作业排列。
步骤5：对于i:=0到n-1，计算makespan目标的do粒子最佳值（pbest）和swarm最佳值（gbest）。通过更新粒子的位置和速度进行进化搜索。
步骤6：对于
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[234153]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
