一种改进的基于遗传算法的中药生产调度系统

安 鑫，郭剑毅，2，花 植，王海雄

(1.昆明理工大学信息工程与自动化学院，云南昆明650051;

2.云南省计算机技术应用重点实验室智能信息处理研究所，云南昆明650051)

作业车间调度问题(job－shop scheduling problem，JSSP)可以描述为:给定一个药品集合和一个机器集合，每个工件多道工序，每道工序需要在一台给定的机器上非间断地加工一段时间;每一台机器一次最多加工一道工序;调度就是把工序分配给机器上某个时间段。其目标是找到最短时间长度的调度［1］。典型的中药生产企业生产体系由多条生产线构成，每条生产线接收原材料或前一条生产线输出的半成品，多条生产线协同完成一种药品的生产。若将每种剂型的生产流程进行分解，每个设备对应一道生产工序，则中药制药的生产调度问题可看成是一般的JSSP问题。

目前国内在中药制药生产调度系统上的研究很少。文献［2］提出用标准遗传算法来解决中药生产调度问题。然而由于标准遗传算法本身的缺陷，在寻优求解过程中容易陷入局部最优，且计算速度慢，使系统得不到理想的结果。笔者通过对中药制药企业的生产工艺流程进行分析，将基于并行遗传算法［3］与小生境遗传算法［4］相结合的改进遗传算法应用到中药制药生产调度系统中，通过改进遗传算法寻找到最优解或次优解，避免了寻优过程中出现早熟和陷入局部最优现象，并得到合理的生产调度方案，为中药制药生产调度提供了新的思路。

1 工艺流程分析及算法的提出

1.1 工艺流程

由于生产调度系统的通用性差，因此分析中药制药生产工艺流程对解决中药制药生产调度问题至关重要。某中药制造车间主要有胶囊剂生产线、外包生产线、片剂生产线、提取生产线、眼用制剂生产线、颗粒剂生产线、锭剂生产线和散剂生产线等8条生产线，每条生产线都需要经过预前处理、成型和外包等工序，每种剂型的加工顺序不变，且同种剂型不同药品的加工工序基本相同，各生产线又由多个设备组成，每种药品都有其生产加工流程和相应生产工序对应的生产加工设备，从而组成一个复杂的生产体系。

1.2 算法的提出

生产调度问题已被证明是非确定型多项式(non－deterministic polynomial，NP)，即 NP 难问题［5］。中药生产调度系统是一个多目标系统，且在调度过程中受到诸多条件的约束，目前解决作业车间调度问题的典型方法是基于神经网络和遗传算法的JSSP［6］。标准遗传算法的初始种群以及随后进化的种群都只有一个，在遗传算子进行选择和交叉操作时，保持了解空间的多样性，但是随着优化计算的进行，到了计算后期，寻优进入平衡态，解空间内的可能解集中于某个极值点，其后代产生近亲繁殖，陷入局部最优而无法得到全局最优解或次优解。在寻优过程中一旦陷入局部最优，就很难自行跳出局部极值［7］。而利用遗传算法的隐含并行性对种群中各个可能解进行交叉、变异操作并对多个可能解进行判别和寻优计算，即可有效避免陷入局部最优。小生境遗传算法的基本思想就是为了保持种群内的多样性，在种群内部随机选取若干个体构成排挤成员，通过遗传操作产生新个体，判断新个体和排挤成员的相似性，剔除与排挤成员相似的新个体。在优化计算的过程中，包含多个生存环境，同时种群内部的多样性得到延续。

为了弥补标准遗传算法的不足，笔者采用了基于并行遗传算法与小生境遗传算法相结合的改进遗传算法，利用并行遗传算法寻优计算的并行性和小生境遗传算法寻优计算的多样性等优点，相对标准遗传算法，这种改进遗传算法在克服早熟和局部极值等问题上有较大的改善。

2 基于改进遗传算法的模型原理

2.1 基于工序的编码方法

有效的编解码方式能够使随后进行的遗传算法寻优求解过程更加高效、可靠。针对生产调度问题的编码方式有很多，CHENG［8］总结了遗传算法在解决生产调度问题的8种染色体编码方法，考虑产生可能解的合法性和可行性，以及中药生产的作业车间调度模型，笔者将采用基于工序的编码方法。

基于工序编码方法是将调度编码作为工序的序列，每个基因代表一道工序，比如对于3个药品3台机器问题，一个染色体包括3×3个基因，每个药品出现在染色体中3次。数据如表1所示。

表1 3个药品3台加工设备的加工数据

给出一个染色体［3 2 2 1 1 2 3 1 3］，其中1、2、3分别表示药品加工工序1、2、3，假设每个药品有3个加工工序，则每个药品在染色体中出现3次。以药品2为例，第一个2表示药品2的第1个工序在设备1上加工，第二个2表示药品2的第2个工序在设备3上加工，第三个2表示药品2的第3个工序在设备2上加工。很显然，染色体的任何一种排列都能产生可行解。

2.2 解码实现

设计编码算法产生的码 s［i］，i=1，…，n×m，及其任意转换方式解码成可行的活动调度策略的算法。解码算法如下:

令 k［i］=1，i=1，…，n;

For i=1 to n×m;

得到加工药品 s［i］的机器号 Jm(s［i］，k［s［i］］);

令 k［s［i］］=k［s［i］］+1;

将药品 s［i］在机器 Jm(s［i］，k［s［i］］－1)上的操作以最早允许加工时间加工，即从零时刻到当前时刻对该机器上的各加工空闲依次判断能否将该药品插入加工。若能，则在空闲中插入加工，并修改该机器上的加工队列;否则，以当前时刻加工该药品，将该药品排在当前队列的末尾。算法中，药品i能在空闲时间段［a，b］插入加工的条件为:

max［t(i)，a］+t_proc≤b

其中:a和b分别为空闲起始和终止时刻;t(i)为药品i目前的最早允许加工时间;t_proc为药品在机器上的加工时间。

2.3 操作算子

在改进遗传算法寻优过程中，寻优计算主要包括两部分:种群内寻优和种群间优良模式的交换。两个种群同时相互独立地以不同的遗传进化参数进行寻优计算，产生不同的优良模式，在达到设定的进化代数后，两个种群停止各自寻优计算，分别从各自种群中选出N个个体以及种群内适应度最高的个体，N是随机产生的整数且小于种群规模数大于零，之后将两个种群内的N个个体以及种群内适应度最高的个体进行交换，从而将不同优良模式引入不同种群，实现不同优良模式杂交。同时在两个不同进化参数种群分别独立进化的过程中，实现不同优良模式寻优的并行性。

2.3.1 选择算子

两个相互独立的种群独立进行寻优计算时，首先需要分别从各自的种群中进行选择操作。两个种群独自选择时采用的是最优个体保存策略方法，在两个种群进行个体交换时采用适应度比例法，这样保证适应度高的个体得到保留，又不至于使算法陷入局部最优。2.3.2 交叉算子

在中药制药调度系统中设计交叉算子最重要的标准是子代对父代优良特性的继承性和子代的可行性，笔者采用文献［9］提出的新的交叉算子POX(precedence operation crossover)，如图 1所示，它能够更好地继承父代优良特征并且子代总是可行的。

图1 POX交叉

2.3.3 变异算子

遗传算法中的变异主要是为了保证其局部的随机搜索能力和维持种群的多样性。笔者采用的是基本位变异，即对可能解编码字符串依照变异概率随机将字符串中的一位或几位进行变异运算。

2.3.4 种群间的个体交换

对两个相互独立的种群分别进行寻优计算后，再进行种群间的个体交换。其具体方法如下:

(1)随机产生整数 N，N的取值范围是［1，min(pop1，pop2)］，pop1为种群1的个体数量减去1，pop2为种群2的个体数量减去1。

(2)每个种群内随机选取N个个体和最优个体，在pop1和pop2间交换选中的N+1个个体。

(3)完成种群间个体交换。

2.3.5 适应度函数

中药生产调度系统以中药生产时间F(x)最短为目标函数，FIT［F(x)］为适应度函数，根据目标函数映射方法最小化问题原则，适应度函数取目标函数的导数使得适应度函数值和个体适应度呈正比关系，即FIT［F(x)］=1/F(x)。

3 中药制药生产调度结果处理

在中药制药生产调度系统中，信息通过改进算法子系统求得最优解或次优解，通过解码生成调度方案，并根据调度结果绘制成相应的甘特图或生产报表，为生产计划制定和生产决策人员提供支持，甘特图显示调度结果如图2所示。

从图2可清晰地看出以下信息:某药品各道工序的开始和结束时间;各种药品的完工时间及所有药品的完工时间;各生产线上设备的生产利用时间。各药品严格按照生产工艺安排生产次序，对照生产工艺库各药品对应的工序先后和工序时间，从甘特图可以看出调度方案是可行的。

图2 甘特图显示调度结果

4 原型系统的实现与测试

4.1 原型系统

根据该系统的设计目标和原则，原型系统采用Client/Server技术的两层应用体系结构模型来实现，数据的存取和管理相互独立，有单独的数据库管理系统对数据集中管理，方便调度人员通过客户端实现对服务器的访问。系统主要包括数据管理子系统、调度算法子系统、计划分解子系统和调度结果处理子系统，算法系统作为单独的子系统独立出来以便扩展。

4.2 系统测试

4.2.1 性能验证

改进后遗传算法性能验证选用的是MT06、MT10和MT20标准测试用例，分别对改进后的混合遗传算法在中药调度系统中的寻优结果进行分析和比较。算法的参数配置如表2所示。

表2 标准遗传算法与改进遗传算法参数配置

通过标准遗传算法和改进后的遗传算法解决MT06、MT10和MT20标准测试用例，并分别运算10次，得到如表3所示的实验数据对比结果。

从实验数据可知，改进遗传算法在计算小规模寻优求解问题MT06问题时能够迅速收敛并得到最优解，在计算规模偏大的寻优求解问题MT10问题和MT20问题时还无法达到最优解，只能得次优解，由于该系统是针对某中型中药制药企业进行研究的，规模相对较小，因此，可进行实际应用，并得到可行的调度方案。

表3 实验数据对比

4.2.2 应用验证

对比该中药制药企业的生产计划表，系统可以自动生成调度方案，且药品信息、设备信息和工序信息都是从相应的数据库中取得的，一旦有变动，只需更改数据库。同时改变了人工调度方式设备利用率低，调度效率不高，调度结果达不到最优，费时费力，且制作报表时容易出错等问题，大大提高了生产排程的效率。

5 结论

通过分析中药制药生产流程和特点，利用基于并行遗传算法与小生境遗传算法相结合的改进遗传算法来解决中药制药调度问题，有效地抑制了早熟和局部极值现象，通过测试验证了调度方案的可行性，为解决中药制药生产调度问题提供了理论依据和实用价值。

［1］CONWAY RW，MAXWELLW，MILLER LW.Theory of scheduling［M］.Addison － Wesley:Reading Mass，1967:21－36.

［2］GUO JY，HUA Z.A schedulingmodelof Chinesemedicine production based on genetic algorithm research and applications［C］//International Conference on Machine Learning and Cybernetics2009.Baoding:［s.n.］，2009:241－253.

［3］FALKENAUER E，BOUFFOUIX S.A genetic algorithm for job shop scheduling［C］//Proceedings of IEEE International Conference on Robotics and Automation Sacremento.［S.l.］:［s.n.］，1991:824 －829.

［4］GRUDININ N.Reactive power optimization using successive quadratic programmingmethod［J］.1998(4):1219－1225.

［5］STEPHEN A C.The complexity of theorem － proving procedures［C］//Proc of the 3rd Annual ACM Symp on Theory of Computing.New York:AC Press，1971:151－158.

［6］王万良，吴启迪.生产调度智能算法及其应用［M］.北京:科学出版社，2007:54－63.

［7］王凌.车间调度及其遗传算法［M］.北京:清华大学出版社，2003:122－129.

［8］CHENG RW，GEN M，TSUJIMURA Y.A tutorial survey of job－shop scheduling problems using genetic algorithms－I representation［J］.Computers＆ Industrial Engineering，1996，30(4):983 －997.

［9］张超勇，饶运清.基于POX交叉的遗传算法求解job－shop调度问题［J］.中国机械工程，2004，15(23):2149－2153.