考虑并行机的流水车间调度问题研究

摘  要

随着世界经济一体化，贸易全球化，中国要想从制造大国迈向制造强国，不仅仅需要先进的技术，更需要先进的管理。面对客户的需求变得更加的多样化和个性化，制造企业需要不断地提高对市场的响应速度，降低生产的成本，提高产品的质量，因此柔性制造成为了企业在市场竞争中立于不败之地的重要法宝。科学合理的车间调度能够最优化地配置企业的生产资源，提高企业生产效率，缩短制造周期，快速地响应市场的需求。

本文首先综述了流水车间调度的研究现状，对车间调度进行了描述和分类，分析了流水车间调度的特点，建立了柔性流水车间调度的数学模型，简要介绍了求解流水车间调度问题常用的方法；其次对遗传算法进行了概述，详细介绍了遗传算法的基本思想和基本概念，分析了遗传算法的特点和改进方向，论述了遗传算法的操作设计和参数设计；再次，对求解流水车间调度的遗传算法进行了详细的设计，包括染色体编码和解码方式、遗传算子和算法流程；最后结合柔性流水车间调度的实例，借助visual studio软件，对实际问题进行了仿真，绘制所求问题的迭代图和甘特图，并对实验结果进行了分析，仿真结果验证了数学模型的正确性，以及遗传算法在求解柔性流水车间调度问题中的可行性和有效性。

关键词: 柔性流水车间调度，遗传算法，基于操作的编码，POX交叉

A Research On Flow-shop Scheduling Problem Considering Parallel Machines

ABSTRACT

With the integration of the world economy and the globalization of trade, China wants to move from the manufacturing country to the manufacturing power, not only the advanced technology, but also the advanced management. Facing the needs of customers become more diversified and personalized, manufacturing enterprises need to constantly improve the response speed of the market, reduce the cost of production, and improve the quality of products, so flexible manufacturing has become an important magic weapon for enterprises to stand in an invincible position in the market competition. Scientific and reasonable workshop scheduling can optimize the production resources of enterprises, improve production efficiency, shorten the manufacturing cycle, and quickly respond to the demand of the market.

This paper first summarizes the research status of flow shop scheduling, describes and classifies the shop scheduling, analyzes the characteristics of flow shop scheduling, establishes a mathematical model of the flexible flow shop scheduling, and briefly introduces the common methods for solving the scheduling problem of flow shop scheduling, and gives an overview of the genetic algorithm in detail. This paper introduces the basic ideas and basic concepts of genetic algorithm, analyzes the characteristics and improvement direction of the genetic algorithm, discusses the operation design and parameter design of the genetic algorithm. Again, the genetic algorithm for solving the scheduling of flow shop scheduling is designed in detail, including chromosome coding and decoding, genetic operators and algorithm flow. In the end, with the example of the flexible flow shop scheduling, the actual problems are simulated with the aid of Visual Studio software, the iterative graphs and Gantt graphs are drawn and the results of the experiment are analyzed. The simulation results verify the correctness of the mathematical model and the practicality and effectiveness of the genetic algorithm in solving the flexible flow shop scheduling problem.

KEY WORDS: Flexible Flow-shop Scheduling， Genetic Algorithm，Operation -based Coding， POX Crossover

第1章 绪 论

本章首先对选题的目的及意义进行了简要的介绍，其次综述了流水车间调度（Flow-shop Scheduling Problem，FSP）的研究现状，结合其研究过程中存在的问题，对其发展趋势进行了一定的预测。最后，对研究内容进行了具体的安排和详细的介绍。

1.1选题的目的及意义

20世纪末期，我国制造业获得了极大的发展，生产力极大提高，企业的生产规模越来越大。同时，随着人民生活水平的提高，对于产品的需要更加多元化，多样化和个性化，使得多品种、小批量生产方式成为占市场主要份额的重要生产方式。这种生产方式使得企业生产过程更加的复杂，生产要素急剧增加，企业生产管理变得越来越困难，原来所使用的简单的、粗放的、仅凭管理者经验的生产管理方式已经不再适用于现代企业生产管理。同时随着经济全球化，市场竞争日趋激烈，制造企业要想取得长足的发展，获得最大的效益，必须提高企业响应速度和生产效率、提高产品质量并且减少生产成本。据相关资料显示，非切削过程占用了整个生产过程的大部分时间[1]。因此，科学的调度技术和优化方法可以合理地分配和使用企业生产资源，对于降低企业固定成本，提高资金周转效率，提高设备利用效率，缩短生产周期，降低生产成本，具有十分重要的理论和实践意义。

流水车间调度问题是生产调度中的一个重要的研究部分，制造业实际生产中，为提高机器的使用效率及生产效率，同一工序往往设置多台可选的机器，为提高流水车间问题的实际研究意义，本文提出一种考虑并行机的流水车间调度问题，该问题也称为柔性流水车间调度问题。该问题属于NP-Hard问题，需要采用智能算法进行求解。

1.2国内外研究现状及发展趋势

1.2.1国内外研究现状

1954年，Johnson对两个依次加工型机台的流水车间调度问题进行研究，揭开了生产调度问题研究的序幕[2]。相关学者已经证明了对于存在3台机器以上的车间调度问题是NP难问题，因此，对于含有并行机的流水车间调度一定也是NP难问题，无法找到精确的算法将其求解出来[3]。

早期流水车间调度主要采用线性规划、整数规划、目标规划、动态规划和分支定界等方法求解单机生产或小批量生产，研究范围窄，约束少，简单而常规调度问题。同时，一些学者将启发式算法应用于流水车间调度问题。七十年代以来，随着科学技术的进步，大规模生产模式开始广泛出现，这无疑增加了车间调度的难度，大量学者开始研究算法的复杂性，虽然车间调度NP-Hard问题的理论研究取得了许多的成果，但是由于难以找到多项式算法，因此很多学者开始关注启发式算法。一些学者总结了112种调度规则，并对其进行了分类。九十年代及以后，随着最优化设计方法的成熟及多品种小批量生产模式的出现，智能优化方法与车间调度工程的结合成为该领域研究的热点[4]。

近年来，流水车间调度的新理论也层出不穷，如国外学者 Rajkumar等提出用贪心随机自适应搜索（Greedy Randomized Adaptive Search Procedures，GRASP）过程来解决柔性作业车间有限资源约束问题[5]。Zribi等采用分步法求解柔性作业车间调度问题(Flexible Job-shop Scheduling Problem，FJSP)，先基于启发式与局部搜索方法解决机台选择问题，再对加工工序进行排序处理[6]。国内学者王金鹏等通过对遗传算法（Genetic Algorithm，GA）进行改进，提出了一种最优子种群遗传算法，这种算法的不仅提高了遗传算法的精度，而且能够有效地避免算法陷入局部最优解[7]。宋书强等通过对粒子群算法（Particle Swarm Optimization，PSO）进行改进，提出了量子粒子群算法，这种算法不仅寻优的性能较好，而且收敛速度也比传统的遗传算法好[8]。余文丽等提出了一种具有良好自适应的遗传算法用于改善算法收敛过早的现象[9]。梁黎明等提出了一种混合式遗传算法，这种算法是将邻域搜索和遗传算法相互结合，扩展了遗传算法的搜索空间，能够很好地解决柔性流水车间调度(Flexible Flow-shop Scheduling Problem，FFSP) [10]。针对生产过程中出现的机台故障动态事件，Hasan等提出一种局部搜索与遗传算法相结合的方法，能有效的降低工件的移位间隙，并分析得出机台故障在生产过程中越早发生，调度方案修复的可能性相对越大[11]。国内周刚等采用档案集保存最优解，并将最优解参与跟随蜂的交叉操作，设计了多种基于pareto排序的ABC算法求解FFSP和FJSP [12]。王万雷等针对多型号混线生产车间产品齐套性难以保证的调度问题，制定了一套适用于具有动态随机性、交期模糊性及双柔性的车间调度系统[13]。谢光等对求解多目标混合流水车间调度问题，以最小化最大完工时间、提前惩罚量和滞后惩罚量为目标，提出一种改进的MOEA/D算法；采用基于排列的编码策略，设计两种局部搜索策略，提高算法求解性能；设计一种全局搜索交叉算子，给出一种种群更新策略，进一步提升解的分布均匀性[14]。王芳等提出了一种求解柔性流水车间调度问题的高效分布估算算法，该算法的概率模型能提高分布估算算法的收敛质量和速度；同时为提高算法局部搜索能力和防止算法陷入局部最优，设计了局部搜索和重启机制[15]。崔琪等针对混合流水车间调度问题的NP难特性,提出一种改进的混合变邻域搜索的遗传算法，采用NEH启发式算法产生初始种群，产生了质量更好的初始解；对当前最优个体执行变邻域搜索，增强了遗传算法的局部搜索能力[16]。

目前，在生产调度问题的研究中，各种方法都得到了充分的发挥，新的研究方法层出不穷。虚拟制造(Virtual Manufacturing，VM)、柔性制造、精益生产（Lean Production，LP）、敏捷制造(Agile Manufacturing，AM)等多种现代化先进制造生产模式从传统的生产模式中得到创新与深化[17]。

根据目前调度理论的发展情况来看，经典的调度算法依然是研究调度问题的基本方法，同时智能的调度算法发展的十分迅速，对于求解调度问题具有很好的效果。将两者相互融合将会成为一种趋势。

1.2.2发展趋势

虽然近年来国内外学者在流水车间调度领域取得了一定的研究成果，但是流水车间调度还存在一些问题，具体以下几个方面仍有待研究：

（1）调度算法。由于流水车间调度问题是一个NP难问题，因此很难用传统的优化算法求解。虽然在一个合理的时间内，各种近似启发式可以产生令人更满意的调度方案，如基于规则的算法，但它常常不能评估所得到的调度解决方案的次优性。为了解决这一问题，有必要探索一种可以通过增加合理的计算时间来增加解次优性的近似最优调度算法。这就需要对算法的参数设置、计算时间和计算复杂度进行进一步的分析和理论研究。基于统计优化的各种方法虽然能够解决调度问题，但是收敛速度较慢，也存在一定程度的枚举。而且很难确定是否是最优解。

（2）调度问题。流水车间调度优化问题是一类具有柔性、动态、模糊和多目标优化等问题的NP难题。

经典的调度问题是实际调度问题的一种简化，考虑的因素较少，如没有考虑并行机，特别是在当前柔性制造环境下，大量学者只针对工件无等待、批量加工等问题进行智能算法的适用性改进研究，目前多数柔性生产车间调度问题的解决方法首先对机台选择和工序排序分步处理，再结合智能算法进行求解。因此柔性车间调度问题将是进一步研究的一个重点方向。

流水车间调度可分为静态调度(Static scheduling)和动态调度(Dynamic scheduling)两类问题。不确定事件的发生导致静态调度方案不适用，决策者很难在较短的时间内做出适用于动态事件的最新调度方案。目前大量研究工作是对生产加工环境、生产任务己知的问题求解，但在实际生产制造过程中，往往会出现订单更新、交货期变化、设备故障、物料短缺等多种不可预知事件，这些事件都会引起动态调度[21]。因此，动态调度问题还有待进一步研究。

模糊调度问题是指工件的交货期、加工时间、加工工艺等生产因素没有明确的数据信息，问题具有模糊性。因此，模糊车间调度问题需要进一步研究。

多目标优化问题的难点在于对不可通约和相互矛盾的目标进行决策优化，而生产调度问题本身就是NP-Hard题，将二者结合的多目标流水车间调度问题是一种全新的具有挑战性的研究方向。因此在目前的研究基础上将动态调度、柔性调度、模糊调度和多目标调度求解方法进行融合，设计出一种全面的求解方法是流水车间调度的一个重要的趋势。

（3）调度系统。随着工业4.0概念的提出，越来越多的制造企业将智能制造的概念引入生产车间。目前制造业所面临的问题是如何利用信息技术，将上层的规划管理系统与底层的工业监控系统进行关联，从而优化工艺流程、实现精益生产，给管理者提供一个能快速、精准应对市场变化的决策支持。在实际车间调度中，生产计划和调度往往是分层的，就将可能会导致不可行的调度。采用大数据处理技术将调度与计划智能融合，实现真正的智能调度，需要进一步的研究[22]。

1.3本文研究内容

全文一共分为六章，每章主要内容如下：

第一章，简要介绍了流水车间调度的研究目的及意义，总结了流水车间调度的研究现状，并针对在其研究过程中存在的问题，对流水车间调度的发展趋势进行了展望。

第二章，简要对车间调度问题进行了描述和分类；分析了车间调度特点，详细介绍了柔性流水车间调度问题的基本概念，建立了该问题的数学模型；对常用的求解流水作业问题的方法进行了比较和分析。

第三章，对遗传算法进行了概述，详细介绍了遗传算法的基本思想和基本概念、分析了遗传算法的特点和改进方向，论述了遗传算法的操作设计和参数设计。

第四章，对应用于柔性流水车间调度的遗传算法进行了详细的设计，包括染色体编码和解码方式、遗传算子和算法流程。

第五章，以一个具体的柔性流水车间调度问题为例，完成程序设计与仿真，绘制了实例对应的迭代图和甘特图，并对实验结果进行了分析。

第六章，总结了本文的研究工作，分析了研究的不足，并对进一步的研究进行了展望。

图2-1 调度算法分类

图2-2柔性流水车间调度示意图

文档及资料打包下载：基于遗传算法的柔性流水车间调度设计与实现（论文+源码+答辩ppt）.zip