下载文档原格式
基于启发式算法的工厂调度优化研究随着制造业的快速发展，如何提高生产效率成为了制造业中一个重要的问题。
而作为现代制造业的核心环节，工厂调度、产线优化和物流管理的效率也成为了决定生产效率的关键因素。
面对日益繁忙的生产线，如何将订单、人力资源、机器设备等资源合理分配并进行调度，已成为了工厂内优化的难点之一。
然而，这样的调度问题往往是一种NP难问题，传统的算法很难在合理的时间内求出最佳解。
因此，一些基于启发式算法的工厂调度优化方法先进出现。
启发式算法是模拟大自然人工制定的一类算法，它将模拟生命，尤其是生态系统中的进化和生长过程，来制定最佳解决方案。
启发式算法的典型例子是遗传算法、模拟退火算法和蚁群算法等等。
在一个典型的工厂调度问题中，通常会涉及调度目标、工件之间的限制和约束条件等多个方面，这给求解算法带来了不小的难度。
而基于启发式算法的方法，能够较好地针对这类问题进行求解。
以遗传算法为例，其求解过程主要包括三个步骤：编码（基因编码）、选择和演化。
首先，将工作安排看作是一个基因序列，对其进行编码形成一个可计算的个体。
然后，根据适应度函数计算每个个体的适应度值，通过选择、交叉和变异等操作，不断从旧个体群中生成新的个体群。
最终，当某个代际的个体满足条件时，求解过程停止并输出最优解。
在生活中，有很多实际案例可以应用基于启发式算法的工厂调度优化方法。
例如，我国某家装企业面对订单的急剧增长，开始面临生产压力过大的困扰，而利用遗传算法进行调度优化后，使得企业生产效率提升10%以上。
但是，虽然基于启发式算法的工厂调度优化方法具有很高的求解效率和应用价值，但其也存在一些局限性。
一般来说，求解过程高度依赖个体群的初始化和随机性处理，这使得其难以获得真正的全局最优解。
同时，算法对问题的求解难度和参数的设定要求较高，对使用者的技能和经验要求比较高。
综上所述，基于启发式算法的工厂调度优化方法在解决NP难问题方面具有很大的优势，但其也存在一些局限性。
一种改进的关键工序算法刘智勇 徐昕江苏科技大学经济管理学院，江苏 镇江 212003摘要：针对max ///n m p F 问题，改进了关键工序法法，该算法同时注重关键工件与关键工序，通过对关键工件与非关键工件在关键工序前后的加工时间计算、比较来获得各工件加工的先后顺序，缩短最长流程时间。
并将该启发式算法与关键工序法进行了对比分析，最后利用仿真的方法来验证所提出的方法的可行性。
关键词：Flow-shop 关键工件 关键工序 启发式算法 最长流程时间 0引言Flow-shop 调度问题（flow shop scheduling problem,FSP ）是许多实际流水线生产调度问题的简化模型，它无论是在离散制造工业还是在流程工业中都具有广泛的应用，因此其研究具有重要的理论意义和工程价值。
n/m/p/F max 问题是Flow-shop调度问题中的一种特殊情况，即所有工件在各台机器上的加工顺序都相同，也称流水作业排列排序问题或同顺序排序问题。
其求解方法有精确方法[1]（分支定界法、穷举法等）、智能搜索法[2,3,4]（神经网络法、遗传算法、蚁群算法等）、启发式算法[4,5,6,7]（Palmer 算法、C-D-S 法、关键工序法、最小排序系数法等）等等。
由于Flow-shop 调度问题一般都属于NP 难题(nondeterministic polynomial)。
精确方法只能求解小规模问题，对于大规模问题几乎被认为是无效算法，智能搜索法在求解上虽比启发式算法更接近最有解，但由于设计针对具体问题的智能搜索法对于许多人来说比较困难，特别是对于实际工程人员更是如此。
所以启发式算法仍是用的很多的方法。
主要的启发式算法有Palmer 算法、关键工序法和最小排序系数法等。
其中，关键工序法贯穿着当前先进的管理思想，能够很好的对现实情况进行解释和分析。
然而关键工序法所求的可行解很可能与最优解相差甚远，鉴于此，本文对其进行了改进。
改进迭代贪婪算法求解可重入流水车间调度问题可重入流水车间调度问题（reentrant flow shop scheduling problem）是指在多工序流水车间中，存在可重入现象的调度问题。
在车间中，每个作业需要按照一定的工序顺序加工，而每个工序都有不同的机器可以完成。
不同于一般流水车间问题，可重入流水车间问题允许同一作业在同一工序上重复进行，增加了调度的复杂性和难度。
迭代贪婪算法是一种常用于解决可重入流水车间调度问题的启发式算法。
它的基本思想是通过多次迭代，每次选择当前局部最优的决策来逐步优化最终调度结果。
然而，传统的迭代贪婪算法存在着一些不足之处，例如容易陷入局部最优解、收敛速度较慢等。
因此，本文将针对这些不足之处进行改进，以求更好地解决可重入流水车间调度问题。
一、改进之处在改进迭代贪婪算法求解可重入流水车间调度问题时，我们可以从以下几个方面进行改进：1. 变异操作策略的引入：传统的迭代贪婪算法只考虑选择当前局部最优解进行迭代更新，但这种策略存在着局限性。
我们可以引入变异操作策略，即在每次迭代中，按照一定概率引入一定程度的随机性，以避免陷入局部最优解。
通过引入变异操作，可以增强算法的全局搜索能力，提高算法的质量和效率。
2. 邻域搜索的扩展：邻域搜索是迭代贪婪算法中的关键步骤。
传统的迭代贪婪算法仅仅根据局部最优解进行邻域搜索，但这种策略可能无法充分探索搜索空间。
我们可以考虑扩展邻域搜索的范围，在搜索过程中引入一定程度的随机性，以增加解空间的探索度。
通过扩展邻域搜索的范围，可以更全面地搜索潜在解，提高算法的全局搜索能力。
3. 优化目标函数的定义：目标函数的定义直接关系到算法求解可重入流水车间调度问题的效果。
传统的迭代贪婪算法通常采用简单的目标函数，例如最小化总加工时间或最大化作业的完工时间。
然而，这样的目标函数并不能充分考虑到车间效率与资源利用率等因素。
我们可以重新定义目标函数，结合车间实际情况和约束条件，以综合考虑多个指标，从而求得更合理、更优的调度结果。
计算机测量与控制．２０２０．２８（１１） 犆狅犿狆狌狋犲狉犕犲犪狊狌狉犲犿犲狀狋牔犆狅狀狋狉狅犾 ·１９２ ·收稿日期：２０２００４０２； 修回日期：２０２００５０６。
基金项目：国家自然科学基金项目（６１４７３２１６）；陕西省教育厅科学研究计划项目（１７ＪＫ０４５９）；陕西省自然科学基金（２０１５ＪＭ６３３７）；陕西省自然科学基金面上项目（２０２０ＪＭ－４８９）；西安建筑科技大学基础研究项目（ＺＲ１８０４９）。
作者简介：王 森（１９９４），男，陕西渭南人，硕士，主要从事重调度优化方向的研究。
通讯作者：熊福力（１９７４），男，黑龙江肇东人，硕士生导师，副教授，主要从事人工智能与系统优化、生产计划与调度优化、智能建筑方向的研究。
文章编号：１６７１４５９８（２０２０）１１０１９２０４ ＤＯＩ：１０．１６５２６／ｊ．ｃｎｋｉ．１１－４７６２／ｔｐ．２０２０．１１．０３９ 中图分类号：ＴＰ４９７文献标识码：Ａ一种启发式算法和改进遗传混合算法在流水车间重调度中的应用王 森，熊福力，李 志（西安建筑科技大学信息与控制工程学院，西安 ７１００５５）摘要：在解决以合同惩罚和存储成本最小化为优化目标的流水车间重调度问题时，提出了一种启发式算法和改进的遗传混合算法；传统的遗传算法是一种基于优胜劣汰的随机、自适应的优化算法；通过复制，交叉和变异，将问题解编码所表示的“染色体”群在逐代进化，最终收敛到最合适的群体，从而得到问题的最优或满意解；但缺点是求解结果依赖于初始值，且运行时间过长；因此对传统遗传算法做了相应的改进，考虑到启发式算法的快速性，为充分发挥两种算法的优势，提出启发式算法和改进遗传混合算法；最后对性能进行分析；试验结果表明：该算法运行时间短，且在大规模数据集下，更易于靠近全局最优解。
关键词：遗传算法；染色体；初始值；启发式算法犃狆狆犾犻犮犪狋犻狅狀狅犳犪犎犲狌狉犻狊狋犻犮犃犾犵狅狉犻狋犺犿犪狀犱犐犿狆狉狅狏犲犱犌犲狀犲狋犻犮犎狔犫狉犻犱犃犾犵狅狉犻狋犺犿犻狀犘狉狅犱狌犮狋犻狅狀犚犲狊犮犺犲犱狌犾犻狀犵ＷａｎｇＳｅｎ，ＸｉｏｎｇＦｕｌｉ，ＬｉＺｈｉ（ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＣｏｎｔｒｏｌＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉ ａｎＵｎｉｖｅｒｓｉｔｙｏｆＡｒｃｈｉｔｅｃｔｕｒｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｉ ａｎ ７１００５５，Ｃｈｉｎａ）犃犫狊狋狉犪犮狋：Ａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍａｎｄａｎｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃｈｙｂｒｉｄａｌｇｏｒｉｔｈｍａｒｅｐｒｏｐｏｓｅｄｔｏｓｏｌｖｅｔｈｅｒｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｏｆｆｌｏｗｓｈｏｐｗｉｔｈｔｈｅｏｂｊｅｃｔｉｖｅｏｆｍｉｎｉｍｉｚｉｎｇｔｈｅｃｏｎｔｒａｃｔｐｅｎａｌｔｙａｎｄｓｔｏｒａｇｅｃｏｓｔ．Ｔｈｅｔｒａｄｉｔｉｏｎａｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓａｒａｎｄｏｍａｎｄａｄａｐｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｓｕｒｖｉｖａｌｏｆｔｈｅｆｉｔｔｅｓｔ．Ｂｙｍｅａｎｓｏｆｒｅｐｌｉｃａｔｉｏｎ，ｃｒｏｓｓｏｖｅｒａｎｄｍｕｔａｔｉｏｎ，ｔｈｅ“ｃｈｒｏｍｏｓｏｍｅ”ｇｒｏｕｐｒｅｐｒｅｓｅｎｔｅｄｂｙｔｈｅｓｏｌｕｔｉｏｎｃｏｄｉｎｇｉｓｅｖｏｌｖｅｄｆｒｏｍｇｅｎｅｒａｔｉｏｎｔｏｇｅｎｅｒａｔｉｏｎ，ａｎｄｆｉｎａｌｌｙｃｏｎｖｅｒｇｅｓｔｏｔｈｅｍｏｓｔａｐｐｒｏｐｒｉａｔｅｇｒｏｕｐ，ｓｏａｓｔｏｏｂｔａｉｎｔｈｅｏｐｔｉｍａｌｏｒｓａｔｉｓｆａｃｔｏｒｙｓｏｌｕｔｉｏｎｏｆｔｈｅｐｒｏｂｌｅｍ．Ｂｕｔｔｈｅｄｉｓａｄｖａｎｔａｇｅｉｓｔｈａｔｔｈｅｓｏｌｕｔｉｏｎｄｅｐｅｎｄｓｏｎｔｈｅｉｎｉｔｉａｌｖａｌｕｅ，ａｎｄｔｈｅｒｕｎｎｉｎｇｔｉｍｅｉｓｔｏｏｌｏｎｇ．Ｉｎｏｒｄｅｒｔｏｇｉｖｅｆｕｌｌｐｌａｙｔｏｔｈｅａｄｖａｎｔａｇｅｓｏｆｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓ，ａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍａｎｄａｎｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃｈｙｂｒｉｄａｌｇｏｒｉｔｈｍａｒｅｐｒｏｐｏｓｅｄ．Ｆｉｎａｌｌｙ，ｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｓａｎａｌｙｚｅｄ，ａｎｄｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｒｕｎｓｉｎａｓｈｏｒｔｔｉｍｅ，ａｎｄｉｓｅａｓｉｅｒｔｏａｐｐｒｏａｃｈｔｈｅｇｌｏｂａｌｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｉｎａｌａｒｇｅｄａｔａｓｅｔ．犓犲狔狑狅狉犱狊：ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｃｈｒｏｍｏｓｏｍｅ；ｉｎｉｔｉａｌｖａｌｕｅ；ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ０ 引言流水车间重调度问题是以流水车间调度问题（ｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ，ＦＳＰ）为基础模型的一种动态调度问题，多年来，研究者们大多关注以最大完工时间为优化目标，较少关注工件交货期对流水车间调度问题的影响。
求解流水车间调度问题的瓶颈指向启发式算法屈国强【摘要】To solve flow shop scheduling problem with the makespan minimization criterion, a bottleneck focused heuristic algorithm was proposed according to the characteristics of workpiece time. Different machines generally had different load, to construct initial workpiece sequence, this characteristic was fully used. The workpieces with shorter processing time before bottleneck stage and with longer processing time after bottleneck stage were pro cessed priority. At every stage before or after bottleneck, the workpiece sequence was adjusted according to features of workpiece processing time before or after bottleneck if there were workpieces waiting to be processed. Finally, workpiece adjacent pairwise interchanges and insertion operation were used to improve the initial scheduling. The proposed heuristic algorithm was performed well when bottleneck tends to middle stage or workpiece processing time at bottleneck tends to increase. The data experimental results indicated the effectiveness of the proposed approach.%针对最小化时间表长的流水车间调度问题，提出一种根据工件加工时间特征构建工件调度的瓶颈指向启发式算法。
