CN101271543A - 一种应用了基于精英解池的遗传算法的生产排程系统和方法 - Google Patents

Abstract

本发明提供了一种生产排程系统和方法。此系统由生产计划部门终端、服务器、存储历史数据的数据库组成，生产计划部门终端通过服务器对连接着的各信息终端进行实时数据采集、整理，然后应用基于精英解池的遗传算法对订单进行编码，再执行选择交叉等遗传操作，并进行评价和逐层优化，生成最优生产排程；最终，生产排程方案通过服务器下达到生产车间，并实时接收加工现场的反馈数据以做方案调整。本系统硬件环境易于实现，而在方法上结合启发式规则和遗传算法，能够有效改善订单数量较多，具有多层结构及复杂工艺的情况下，求解排程方案时的求解结果，提高运算速度，具有适用范围广、可拓展型强、运算速度快、优化性能好等优点。

Description

一种应用了基于精英解池的遗传算法的生产排程系统和方法

技术领域

本发明涉及一种生产排程系统和方法，尤其是一种应用了基于精英解池的遗传算法的生产排程系统和方法。

背景技术

生产排程问题，又称生产作业计划或生产排程。从有限资源角度看，生产排程是一个决策过程，是指生产部门为完成销售部门下达的订单，根据确定的生产计划和订单交货期安排，按照产品的加工工艺路线，将有限资源安排给不同的工作，并决定何时开始，由哪部设备加工，并完成哪件工作，并设法达到预定的如交货期要求和提高设备利用率的目标。这些有限资源主要包括：机器和设备(包括搬运设备)、工夹具、作业员、存储容器或空间等。

面向工单的机械行业生产企业通常有着-下特点：生产方式以工单加工为主，市场预测为辅；工单繁忙、插单次数比较多；客户交货期要求准确、急迫；产品生产形式表现为多品种、大中小批量；产品的工艺过程经常变更，生产计划变动频繁；能力需求根据每个产品建立，工序间联系少，很难预测；要求BOM及库存的精确度较高；由于工单繁忙，库存备用严重、最后库存资金占用过高等。

除此之外，企业产品的工艺路线有多条，工艺路线对应的产品质量等级不同。工艺路线中的工序对应不同的工作中心来完成加工任务，工作中心是一条生产线或多台并行设备或单台加工设备，即机台。不同的机器加工产品的质量等级存在不同，根据客户工单要求选择对应质量等级的工艺路线和加工工作中心、设备组及设备。

生产排程问题传统上由ERP(Enterpri se Resource Planning，企业资源管理)系统进行解决，但传统ERP系统仅仅根据交付周期或日期来安排生产的优先次序，所有工作都是在假定无限生产能力的前提下进行，未考虑有限物料的约束条件等等情况，无法适应以上所提到的工单企业的各种特点，使所得的生产排程方案效率低、实用性差。

发明内容

本发明的目的是提供一种生产排程问题生产排程系统和方法，根据客户的实际生产流程建立系统模型，从ERP中导入需求、库存等数据，在通过在多种排程方案的比较后，由系统自动选取最优化方案，实现了智能化排程，形成所有生产资源的详细的生产计划(精确到秒)。从而，解决工单性企业在企业资源管理上效率低下的问题，降低生产成本、提高企业效益。

本发明设计了一种应用了基于精英解池的遗传算法的生产排程系统，此系统由生成排程方案的生产计划部门终端、服务器、存储历史数据的数据库组成，生产计划部门终端通过服务器对连接着的各信息终端进行实时数据采集、整理，进行生产排程；当排程方案确定之后，再通过服务器下达到生产车间，并实时接收加工现场的反馈数据，及时调整排程方案。

所述各相关信息终端包括：客户、销售部门、设备管理部门、仓储部门、加工车间。

在终端、服务器及数据库的硬件选择时，客户端的功能主要是客户端可以采用通用的PC机，也可以是多台独立的小型服务器构成，其基本要求是具有一定的运算能力、输入输出功能、以及将运算结果通过网络传输出去的功能，并能够接受远程服务器运算的结果。

客户端的基本配置为：

计算机主机：PIII 500MHZ以上；

记忆容量：256MB以上；

硬盘空间：20GB以上；

显示器：1024×768真彩色显示器，建议使用1280×1024或更高配置；

磁盘需求：16倍速以上之CD-ROM或DVD-ROM；

当工厂规模不大时，服务器端可以采用通用的PC机，但建议采用大型服务器以适应大型加工企业，其基本要求是具有较好的运算性能、具有较强的数据存储及维护能力，网络传输高效稳定。

服务器端的基本配置为：

计算机主机：Celon 2.66G以上；

记忆容量：1GB以上；

硬盘空间：160GB以上；

显示器：1024×768真彩色显示器，建议使用1280×1024或更高配置；

磁盘需求：16倍速以上之CD-ROM或DVD-ROM；

数据库采用ACCESS数据库，同时也支持如SQL Server等数据库系统。

此生产排程系统运用了如以下步骤的生产排程方法进行生产排程：

1.用户设置工厂基础数据和排程参数；

2.生产排程系统对订单、设备、物料信息进行动态采集、更新、分析，生成参与排程的工单，生产计划部确认排程工单信息、优化目标、约束条件；

3.对参与排程的工单进行编码，生成初始化种群；

4.采用基于订单结构的解码空间映射方法产生操作表，调用正排运算或倒排运算进行解码操作，得到排程方案；

5.对排程方案进行约束条件检验，对可行解进行优化目标的适应度值计算和对不可行解满足约束的程度进行适应度值计算，并设置可行解池和不可行解池两个精英解池，保留优秀个体；

6.根据可行解个数和可行解差界度或最大迭代次数判断是否终止遗传算法：若是，继续下一步；若否，则继续从可行解池和不可行解池中选择优秀个体，进行选择、交叉、变异，生成子代种群，回到步骤④；

7.输出适应度值最高的排程方案；

8.用户同生产排程系统交互式确认排程方案：满意时，排程系统将工单下达到车间；否则，选择性修改参数：工厂基础数据、工单信息、优化目标、约束条件，回到步骤②。

所述步骤1中的设置包括修改、增加、删除、确认操作。

所述步骤1中的工厂基础数据为车间管理基础数据，包括：产品物料清单(Bill of material)结构基础数据，物品信息基础数据，工作中心、设备组、设备信息基础数据，标准工序信息基础数据，工艺路线基础数据，工序间准备时间信息基础数据，工厂日历信息、出勤模式信息基础数据。

所述步骤1中的所述排程参数为优化目标参数，约束级别划分参数，重排程参数，定单更改参数，紧急插单参数。

所述步骤2中的所述优化目标，是通过排程系统终端根据工厂历史数据对比已有工厂模型库、选择最佳项向生产计划部门推荐，由生产计划部门最终选择确认一个或多个优化目标，并设置优化目标之间的权重关系。

所述步骤2中的约束条件，是通过排程系统终端预先提供，由生产计划部门选择一个或多个，并设置约束条件之间的权重关系。

所述步骤2中的分析，是根据订单属性对订单进行订单优先级计算，并根据优先级、工艺、设备、物料信息对订单进行拆分或合并，生成工单，然后基于工单信息、设备信息、物料信息，将设备组、物料预分配给订单。其中订单属性，为客户重要等级、或订单利润率、或订单交货期、或产品制造提前期、或产品种类、或产品数目。其中，订单优先级计算，是先建立影响订单优先级的各个准则，并获取工厂各个专家对影响订单优先级的各个准则之间的权重关系的不同认识，然后通过建立层次结构来分解复杂问题，引入测度理论，通过两两比较，用相对标度将人的判断标量化，结合三角模糊数，把群组中不一致的判断融合到评价中，并逐层建立判断矩阵，求解各判断矩阵的权重，最后计算方案的综合权重并排序。

所述步骤3中的生成初始化种群，为启发式生成或随机式生成。

所述步骤6中的优秀个体为非本代操作产生的优秀个体。

所述步骤6中的交叉或变异，应用了隔代轮换策略，每次迭代使用不同的算子直至所有交叉算子完成一个轮回，再从头开始。

本发明的有益效果是提供了一种生产排程问题生产排程系统和方法，本系统采用了简单的客户/服务器模式，硬件环境较易于实现，既能够直接从ERP中导入需求、库存等数据，进行排程计算，也能在没有ERP系统支持的情况下，单独运行本系统。方法上结合了启发式规则和遗传算法，提高了遗传算法盲目随机操作的效率，加速了算法的收敛，并且利用遗传算法本身所具有的随机性特征又能在一定程度上弥补启发式算法的强偏差性。而遗传算法编码技术和遗传操作比较简单、优化不受限制性条件的约束、尤其是具有并行计算能力和全局解空间搜索能力等优点，能够有效改善订单数量较多，各类约束条件较为复杂，订单具有多层结构及复杂工艺的情况下求解排程方案时的求解结果，提高运算速度，使得本系统和方法具有适用范围广、可拓展型强、运算速度快、优化性能好等优点。能有效降低工厂成本，提高工厂管理水平，缩短产品生产周期，提升工厂竞争力。

附图说明

图1是应用了基于精英解池的遗传算法的生产排程系统的硬件拓扑结构示意图；

图2是应用了基于精英解池的遗传算法的生产排程方法流程图。

图3是生成参与排程的工单及确认优化目标、约束条件流程图。

图4是订单优先级排序流程图。

图5是基于订单结构的遗传算法编码流程图。

图6是基于订单结构的遗传算法解码流程图。

图7是基于约束重要度分层的排程方案检验和评价流程图。

图8是分层优化方式实现多目标优化流程示意图。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

本发明采用客户端/服务器端的硬件拓扑结构如图1所示：整个系统以服务器为中心，服务器连接着数据库、生产计划部门终端和各信息终端(终端即客户端)，包括：销售部门终端(采集订单数据)、仓库部门终端(采集物料信息)、设备管理部门终端(采集设备信息)和加工车间终端。其中，加工车间可以配备打印机以打印最终的排程方案，便于执行。另外，服务器还通过Internet同异地工厂终端、委外单位终端和客户终端进行连接，以交换订单信息等。

本实施例中的客户端平台性能如下：

CPU主频：Celon 2.66G；

内存容量：512M；

运行操作系统为Windows XP；

一个并行打印端口，配置为USB端口。

本实施例中的服务器采用HP的ProLiant DL380G4(378735-AA1)，其性能如下：

CPU类型：Xeon DP；

CPU频率(MHz)：3000；

处理器描述：标准处理器数量1；

支持CPU个数：2；

CPU二级缓存：2MB；

运行操作系统为Windows 2003Server。

此生产排程系统应用了基于精英解池的遗传算法的生产排程方法在此实施例中的实施流程请参阅图2，具体包括以下步骤：

1.用户(即生产计划部门)同生产排程系统，通过生产计划部门终端交互式设置工厂基础数据和排程参数，在此过程中排程终端用户可以对这些数据进行设置包括修改、增加、删除、确认等操作。

其中，工厂基础数据主要为车间管理基础数据，包括：产品BOM结构基础数据，物品信息基础数据，工作中心、设备组、设备信息基础数据，标准工序信息基础数据，工艺路线基础数据等基础数据，工序间准备时间信息基础数据，工厂日历信息、出勤模式信息基础数据等一系列基础数据。工厂排程参数为优化目标参数，约束级别划分参数，重排程参数，定单更改参数，紧急插单参数。

2.生产排程系统对订单、设备、物料信息进行动态采集、更新、分析，生成参与排程的工单，生产计划部门同生产排程系统通过生产计划部门终端交互式确认排程工单信息、优化目标、约束条件，其流程请参阅图3，具体包括以下步骤：

a.交互式确定优化目标权重：首先，生产排程系统的生产计划部门终端根据工厂历史数据的分析，通过统计学上的聚类分类等数据挖掘技术，获取工厂加工特征；然后，终端运用模式识别技术，通过与预设的工厂模型库进行比较，判断工厂最适合那种优化目标，并自动推荐；最终，由生产计划部门选择确认一个或多个优化目标，并设置优化目标之间的权重关系。其中，优化目标模型分为：准时交货(满足交货期前提下最迟化加工)、最早化完工时刻、最小化交货延迟时间、最小化生产流程时间、最小化生产准备时间、最小化生产成本、最大化设备利用率、最大化瓶颈能力。

b.交互式确定约束条件权重：工厂通过生产排程系统的生产计划部门终端预先指定约束条件，然后由生产计划部门选择一个或多个，并设置约束条件之间的权重关系。其中，约束类型分为：定单级约束，如交货期约束、定单最长在线时间约束、定单最短在线时间约束等；工单级的约束，如工单最早开工时刻约束、工单最晚开工时刻约束、工单最早完工时刻约束、工单最晚完工时刻约束、工单最长在线时间约束、工单最短在线时间约束等；工序级的约束，如当前时刻约束，指定开工时刻约束、工序最晚完工时刻约束、工序最大时间间隔约束、最小加工批量约束、物料入库期约束。

c.确定主生产计划，从而获取订单属性。其中，订单属性为，客户重要等级、或订单利润率、或订单交货期、或产品制造提前期、或产品种类、或产品数目等属性。

d.根据订单属性对订单进行订单优先级计算，并根据优先级、工艺、设备、物料等信息对订单进行拆分或合并，生成工单，然后基于工单信息、设备信息、物料信息，将设备组、物料预分配给订单，流程请参阅图4，具体包括以下步骤：

i.建立影响订单优先级的各个准则，如：ERP系统给出交货期、利润、客户等级、质量要求、定单物料五个评价准则，并获取工厂各个专家对影响订单优先级的各个准则之间的权重关系的不同认识。取得的认识以下表格所示，x_i为对应准则C_i的重要度等级：

ii.在优先级计算时，在准则层处理过程中，经过对专家意见的归一化处理，本实施例采用S函数作归一化处理，归一化公式为： $P_{G_i}=\frac{1}{1+e^{-a(x_i-b)}},$ 其中a和b是系数，a决定了S函数的增长率，b决定了S函数的归一化的程度。x_i为准则i的重要度等级。构建准则层上三角比较矩阵，从低到高排列这些准则，两两比较给出上三角表格，比较值按照五个等级给出数值：1、3、5、7、9，不能给出的，用相邻的4、6、8表示。1表示同等重要；3表示重要一点；5表示重要得多；7表示更重要；9表示极端重要。

例如：根据各专家对影响订单优先级的各个准则之间的权重关系的不同认识，计算出了其中一个专家的比较表格：

	交货期C1	利润C2	客户等级C3	质量要求C4	定单物料C5
						交货期C1	1	3	5	7	9
利润C2		1	3	5	7
						客户等级C3			1	3	5
质量要求C4				1	3
						定单物料C5					1

构建准则层模糊判断矩阵A_R＝(α_ij)_N*N，计算准则层模糊综合程度，它的模糊判断矩阵它的元素是一个三角模糊数，即α_ij＝(l_ij，m_ij，u_ij)是一个以m_ij作为中间点的闭区间，而m_ij就是比较判断所采用的1-9中的整数。A_R采用正负反矩阵的形式，即： ${\mathrm{\α}}_{\mathrm{ji}}={\mathrm{\α}}_{\mathrm{ij}}^{-1}=(\frac{1}{u_{\mathrm{ij}}},\frac{1}{m_{\mathrm{ij}}},\frac{1}{l_{\mathrm{ij}}}).$ l_ij为三角模糊数的左截至点，u_ij三角模糊数的右截至点。。并令m_ij-l_ij＝u_ij-m_ij＝δ，δ为常数，实践表明¹/₂＜δ＜1比较适宜。若取δ＝2/3，根据三角模糊数理论，得到如下的判断矩阵

$\left(\begin{array}{ccccc}\left(\mathrm{1,1,1}\right)& (7/\mathrm{3,3,11}/3)& (13/\mathrm{3,5,17}/3)& (19/\mathrm{3,7,23}/3)& (25/\mathrm{3,9,29}/3)\\ (3/\mathrm{7,1}/\mathrm{3,3}/11)& \left(\mathrm{1,1,1}\right)& (7/\mathrm{3,3,11}/3)& (13/\mathrm{3,5}/17/3)& (19/\mathrm{3,7,23}/3)\\ (3/\mathrm{13,1}/\mathrm{5,3}/17)& (3/\mathrm{7,1}/\mathrm{3,3}/11)& \left(\mathrm{1,1,1}\right)& (7/\mathrm{3,3,11}/3)& (13/\mathrm{3,5,17}/3)\\ (3/\mathrm{19,1}/\mathrm{7,3}/23)& (3/\mathrm{13,1}/\mathrm{5,3}/17)& (3/\mathrm{7,1}/\mathrm{3,3}/11)& \left(\mathrm{1,1,1}\right)& (7/\mathrm{3,3,11}/3)\\ (3/\mathrm{25,1}/\mathrm{9,3}/29)& (3/\mathrm{19,1}/\mathrm{7,3}/23)& (3/\mathrm{13,1}/\mathrm{5,3}/17)& (3/\mathrm{7,1}/\mathrm{3,3}/11)& \left(\mathrm{1,1,1}\right)\end{array}\right)$

为了能考虑更多的群组意见，可以给出几个不同群组的比较表格，根据这些表格可以得到相应的判断矩阵。

对每一个准则进行单排序计算： $W_i^O=\min \left(V(S_i^O\&GreaterEqual;S_j^O)\right),$ i＝1，2，…，N即表示第i个准则相对总目标的单排序权重。 $V(S_i^O\&GreaterEqual;S_j^O)=\left\{\begin{array}{cc}1,& m_i\&GreaterEqual;m_j\\ \frac{l_j-u_i}{(m_i-u_i)-(m_j-l_j)},& (l_j\&le;u_i)\&cap;(m_i<m_j)\\ 0,& \left(\mathrm{others}\right)\&cap;(m_i<m_j)\end{array}\right.,$ (j＝i，2，…，N；且j≠i)。其中 $S_i^O=\underset{j=1}{\overset{N}{\mathrm{\&Sigma;}}}{\mathrm{\&Delta;}}_{\mathrm{ij}}\&CircleTimes;{\left(\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}\underset{j=1}{\overset{N}{\mathrm{\&Sigma;}}}{\mathrm{\&Delta;}}_{\mathrm{ij}}\right)}^{-1},$ Δ_ij＝A_C(i，j)为准则层判断矩阵。

对每一个准则的权重W_i ^O进行归一化处理等操作，获得准则层相对总目标的单排序权重矩阵 ${\hat{W}}^O={({\hat{W}}_1^O,{\hat{W}}_2^O,\&CenterDot;\&CenterDot;\&CenterDot;,{\hat{W}}_N^O)}^T,$ 建立订单优先级各个影响准则之间的权重。如得到五个评价指标相对总目标的单排序权重： ${\hat{W}}^O={\left(\mathrm{0.3,0.3,0.07,0.09,0.24}\right)}^T.$

iii.订单层权重矩阵的建立采用与准则层权重矩阵建立一致的方式。在订单层中，对每一个准则，分析不同的订单所占的权重，经过对订单权重的归一化处理，构建订单层上三角比较矩阵，构建订单层模糊判断矩阵，计算订单层模糊综合程度，订单单排序计算，订单权重归一化处理等操作，获得订单层权重矩阵 ${\hat{W}}^C={({\hat{W}}^{C_1},{\hat{W}}^{C_2},\&CenterDot;\&CenterDot;\&CenterDot;,{\hat{W}}^{C_N})}^T,$ 建立各订单相对于该准则来讲的权重关系。如对四个订单计算优先级，决策者对每个订单两两比较进行打分的结果，可得到各个订单相对于某评，得到各订单相对于各准则的单排序权重：

${\hat{W}}^C={\left(\begin{array}{cccc}0.306& 0.053& 0.321& 0.32\\ 0.48& 0.117& 0.001& 0.402\\ 0.354& 0.12& 0.157& 0.369\\ 0.224& 0.237& 0.355& 0.184\\ 0.251& 0.307& 0.365& 0.007\end{array}\right)}^T.$

iv.通过合成总排序计算综合订单不同的准则下对总目标的总排序权重 $\hat{W}={({\hat{W}}_1,{\hat{W}}_2,\&CenterDot;\&CenterDot;\&CenterDot;,{\hat{W}}_M)}^T={\hat{W}}^C{\hat{W}}^O,$ 并经过归一化处理和拉伸取整处理，最终获得订单优先级。如计算各个订单相对于总目标的总排序权重为 $\hat{W}={\left(\mathrm{0.341,0.1544,0.2181,0.2607}\right)}^T.$

e.根据订单的优先级及其他属性，对需要排程计算的新订单进行拆分与合并，生成工单。通过遍历订单BOM结构，为每个需要排程计算的工单选择合适的工艺路线，并为每个工单的每道工序指定合适的设备组加工。动态获取需要使用的设备组的设备状态信息。

f.通过对库存物料及半成品数量的实施时采集，及工厂基础数据的分析，求取需要参与排程计算的工单每道工序实际需要加工的数量及需要消耗的库存物料情况。当物料不足时，初步预估物料采购时间。

g.通过人机交互的方式，让用户确定上述信息。当用户需要修改时，可以进行手动操作。

3.对参与排程的工单进行编码，生成初始化种群，流程请参阅图5，具体步骤包括：

a.确定随机初始种群与启发式初始种群个数。

为了种群的多样性，采用随机方式来产生部分初始群体。为了加快算法收敛的速度，采用启发式产生其余部分的初始种群。随机方式和启发式产生初始种群的比例通过一个经验阈值控制。

b.判断随机产生初始种群是否满足规模，若满足则执行步骤d，否则继续。

c.随机产生一个初始个体，并插入到子代总群，回到步骤b。个体生成的具体方法是采用间接置换编码方法，对参与排程计算所有工单的所有工序进行编码，生成基因串，并通过建立基因串和工序之间的对应关系，得到一个合适的置换顺序，将一组工序的分配处理规则作为状态，生成基因串。其步骤如下：

①初始化可选集合为所有无父工单的工单所组成的集合；

②判断可选集合是否为空；若否，则继续下一步；若是，则输出基因串，编码结束；

③从可选集合中选取待排程工序所属工单插入到基因串中，当工单或此工单所有工序结束编码时，从集合中删除该工单；

④判断被删除工单是否有子工单：若无子工单，则转到步骤②；否则，将子工单插入可选集合，转到步骤③。

在此过程中，一个初始个体即待排程工单在基因串中的排列顺序是随机确定的，只需要满足工单的父子结构关系。

d.判断启发式产生初始种群是否满足规模，若满足则执行步骤f，否则继续。

e.启发式产生一个初始个体，并插入到子代总群，回到步骤d。

启发式产生一个初始个体即通过启发式规则，构造一组工单顺序串，即基因串。它与步骤c随机产生一个初始个体的区别在于工单在基因串中的顺序是按照一定的启发式规则确定的。可采用的启发式规则为：交货期越早的越优先开工，即按照工单交货期排序构造基因串；工单优先级越高的越优先开工，即按照工单优先级排序构造基因串；加工时间越长的越优先开工，即按照工单加工周期长短排序构造基因串；同一个工单的工序尽量开工时刻尽量接近以节约在线时间，即同工单所有工序在基因串中紧挨着排列等。其他步骤同随机方式产生基因一致。

f.输出子代种群。

4.采用基于订单结构的解码空间映射方法产生操作表，并调用正排运算或倒排运算进行解码操作，得到排程方案。

由于基因串隐性的记录了所有参与排程计算的工单的所有工序之间的排程先后关系。但在基因串中，所有的基因只有工单信息，而没有具体的工序信息。在遗传算法解码之前，需要建立基因串和工序之间的对应关系。即解码空间映射，是为了获取基因串对应的工序顺序表，用来进行基因串的解码。具体流程请参阅图6，包括以下步骤：

a.不重复获取子种群中的一条基因串；

b.从基因串依次获取一位基因、获取该基因所代表的工单号，判断工单号在基因串已获取次数，已得到对应工序号，将工单号和工序号依次记录到工序顺序表，重复步骤b直至基因串访问完毕；

c.对工序顺序表进行正排或倒排运算，得到排程方案，并作为基因串的属性保存，其中，

正排运算是指从可生产时刻起(工单从此时刻起可以开始生产，即工单物料投放期)，按照工艺路线规定的顺序，从第一道工序起安排工单每道工序的开工时刻，直到计算出最后一道工序的开工时刻；

倒排运算是指从工单交货期起(在排程之列的工单有不同的交货期)，按照工艺路线规定的顺序，从最后一道工序开始，安排工单每道工序的完工时刻，直到计算出第一道工序的完工时刻。

d.判断子代种群中是否存在未解码的基因串：如否，则输出解码的子种群；如是，则转到步骤a；

5.请参阅图7，对子种群排程方案进行约束条件检验，对可行解进行优化目标优化性能的适应度值计算和对不可行解满足约束的程度进行适应度值计算，并设置可行解池和不可行解池两个精英解池，保留优秀个体，具体步骤如下：

a.不重复获取子种群中的子代个体，即排程方案；

b.排程方案约束检验：

每个排程方案经过所有约束条件检验，就每一项进行对比是否符合，判断后，对相应标志信息进行赋值。

若不满足约束条件，其标志信息令为-1，否则令为1。约束优劣信息为违反该约束的程度：例如某工单脱期了三天，则交货期约束条件检验信息表中该工单标志信息为-1，优劣信息为3(天)。

c.判断排程方案是否满足所有约束条件，即是否所有的约束条件检验标志信息都为1：如果是，继续步骤c；否则，继续步骤d。

d.该排程方案满足所有约束条件，为可行解，按照优化目标进行适应度计算，输出适应度值。排程方案检验与评价结束。

不同的优化目标，适应度函数不同。适应度值越大，则表示排程方案满足优化目标的程度越好。以准时交货为例，排程方案X的适应度函数为

$f\left(X\right)=\mathrm{Ln}\left(\frac{1}{\mathrm{\&Delta;}+\underset{j=1}{\overset{N}{\mathrm{\&Sigma;}}}(T_j^{\mathrm{due}}-t_j^{\mathrm{end}})}\right)$

函数Ln(x)是以指数e为底的对数函数，T_j ^due为定单j的交货期，t_j ^end为定单j计划完工时刻，Δ(0.04)为一个参数。

设置可解池，按照按适应度大小，将可行解依次存入可行解池。当解池中存储的个体达到了最大规模，删除解池中最后一个个体(基因串及其所对应的排程方案)。

e.该排程方案不满足约束条件，即存在约束条件检验标志信息为-1，则该排程方案为不可行解。按约束条件进行适应度计算进行适应度计算，输出适应度值。排程方案检验与评价结束。

适应度运算如下：求排程方案满足的约束条件的加权和，这里约束条件根据重要程度不同都有不同的权值，则不可行排程方案X的适应度值为

$F\left(X\right)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}{\mathrm{\&omega;}}_i{F}_i,$

ω_i为第i类约束条件的权值，F_i为第i类约束条件的满足个数，N为约束条件的类数。

设置不可解池，按照按适应度大小，将不可行解依次存入不可行解池。当解池中存储的个体达到了最大规模，删除解池中最后一个个体(基因串及其所对应的排程方案)

f.判断子代个体是否访问完毕：如是，条件检验结束；如否，转到步骤a。

6.根据可行解个数和可行解差异度或最大迭代次数判断是否终止遗传算法：若是，继续下一步；若否，则继续从可行解池和不可行解池中选择优秀个体，进行选择、交叉、变异，生成子代种群，回到步骤4。具体步骤如下：

a.根据可行解个数和可行解差异度或最大迭代次数判断是否终止遗传算法：当遗传算法获得的可行解足够多，其适应度差异不大时，终止遗传算法的迭代过程；当可行解数量较少或没有可行解时，通过最大迭代次数终止遗传算法的迭代过程；当不满足遗传算法终止条件，则算法继续迭代。

b.进行选择操作。当出现大量可行解时，则忽略不可行解的价值，选择适应度大的解作为交叉变异的父代；当出现大量不可行解时，需要保留全部可行解，再适当添加不可行解，作为交叉变异的父代。在遗传算法选择操作过程中，并非将本代操作获得的优秀个体作为下一次交叉变异操作的父代种群，而是在精英解池种选择优秀个体作为父代种群。

c.进行交叉、变异操作。在交叉、变异等依次变换操作时，父代不直接进入子代，避免二次解码。在交叉和变异过程中，需要保持订单结构，即工单之间有父子关系的，所有子工单及子工单所涉及的工序需编码在父工单及父工单所涉及的工序的左侧。交叉、变异操作应用了隔代轮换策略，每次迭代使用不同的交叉算子直至所有算子完成一个轮回，再从头开始。

7.获得适应度值最高的排程方案，流程请参阅图8，具体包括以下步骤：

判断可行解池是否为空，若可行解池为空，则输出不可行解中适应度值最高的个体作为最好的排程方案，若可行解池非空，则输出可行解中适应度值最高的个体作为最好的排程方案。

8.生产计划部门同生产排程系统通过生产计划部门终端互交式确认排程方案：满意时，生产排程系统将工单下达到车间；否则，选择性修改参数：工厂基础数据、工单信息、优化目标、约束条件，回到步骤2。

综上所述仅为发明的较佳实施例而已，并非用来限定本发明的实施范围。即凡依本发明申请专利范围的内容所作的等效变化与修饰，都应为本发明的技术范畴。

Claims (14)

1.一种应用了基于精英解池的遗传算法的生产排程方法，其特征在于所述方法包括以下步骤：

①用户设置工厂基础数据和排程参数；

②对订单、设备、物料信息进行动态采集、更新、分析，生成参与排程的工单，生产计划部确认排程工单信息、优化目标、约束条件；

③对参与排程的工单进行编码，生成初始化种群；

④采用基于订单结构的解码空间映射方法产生操作表，调用正排运算或倒排运算进行解码操作，得到排程方案；

⑤对排程方案进行约束条件检验，对可行解进行优化目标的适应度值计算和对不可行解满足约束的程度进行适应度值计算，并设置可行解池和不可行解池两个精英解池，保留优秀个体；

⑥根据可行解个数和可行解差异度或最大迭代次数判断是否终止遗传算法：若是，继续下一步；若否，则继续从可行解池和不可行解池中选择优秀个体，进行选择、交叉、变异，生成子代种群，回到步骤④；

⑦输出适应度值最高的排程方案；

⑧用户确认排程方案：满意时，工单下达到车间；否则，选择性修改参数：工厂基础数据、工单信息、优化目标、约束条件，回到步骤②。

2.根据权利要求1所述的一种应用了基于精英解池的遗传算法的生产排程系统，其特征在于：

所述系统由生成排程方案的生产计划部门终端、服务器、存储历史数据的数据库组成，生产计划部门终端通过服务器对连接着的各信息终端进行实时数据采集、整理，进行生产排程；当排程方案确定之后，再通过服务器下达到生产车间，并实时接收加工现场的反馈数据，以及时调整排程方案。

3.根据权利要求2所述的应用了基于精英解池的遗传算法的生产排程系统，其特征在于：

所述各相关信息终端包括：客户终端、销售部门终端、设备管理部门终端、仓储部门终端、加工车间终端。

4.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述步骤①中的设置包括修改、增加、删除、确认操作。

5.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程方法，其特征在于：

所述步骤①中的工厂基础数据为车间管理基础数据，包括：产品物料清单(Bill of material)结构基础数据，物品信息基础数据，工作中心、设备组、设备信息基础数据，标准工序信息基础数据，工艺路线基础数据，工序间准备时间信息基础数据，工厂日历信息、出勤模式信息基础数据。

6.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程方法，其特征在于：

所述步骤①中的所述排程参数包括优化目标参数，约束级别划分参数，重排程参数，定单更改参数，紧急插单参数。

7.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程方法，其特征在于：

所述步骤②中的所述优化目标，是通过排程系统终端根据工厂历史数据对比已有工厂模型库、选择最佳项向生产计划部门推荐，由生产计划部门最终选择确认一个或多个优化目标，并设置优化目标之间的权重关系。

8.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述步骤②中的约束条件，是通过排程系统终端预先提供，由生产计划部门选择一个或多个，并设置约束条件之间的权重关系。

9.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述步骤②中的分析，是根据订单属性对订单进行订单优先级计算，并根据优先级、工艺、设备信息、物料信息对订单进行拆分或合并，生成工单，然后基于工单信息、设备信息、物料信息，将设备组、物料预分配给订单。

10.根据权利要求9所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述订单属性，为客户重要等级、或订单利润率、或订单交货期、或产品制造提前期、或产品种类、或产品数目。

11.根据权利要求9所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述订单优先级计算，是先建立影响订单优先级的各个准则，并获取工厂各个专家对影响订单优先级的各个准则之间的权重关系的不同认识，然后通过建立层次结构来分解复杂问题，引入测度理论，通过两两比较，用相对标度将人的判断标量化，结合三角模糊数，把群组中不一致的判断融合到评价中，并逐层建立判断矩阵，求解各判断矩阵的权重，最后计算方案的综合权重并排序。

12.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述步骤③中的生成初始化种群，为启发式生成或随机式生成。

13.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述步骤⑥中的优秀个体为非本代操作产生的优秀个体。

14.根据权利要求1所述的应用了基于精英解池的遗传算法的生产排程系统和方法，其特征在于：

所述步骤⑥中的交叉或变异，应用了隔代轮换策略，每次迭代使用不同的算子直至所有交叉算子完成一个轮回，再从头开始。

Images