不确定条件下的作业车间多目标调度模型及其遗传优化

黄明，刘鹏飞，梁旭

(大连交通大学 软件学院，辽宁 大连 116028)

0 引言

作业车间调度问题中的不确定性条件主要表现在制造过程中时常发生的扰动(如急件加工，机器损坏等)、生产信息获得的不完整性、资源的优化配置等［1］.目前，虽然对于不确定性条件下的作业车间调度问题取得了一定的研究成果，但多数研究重点侧重于采用某种具体算法求解不确定条件的某一种或几种特定条件［2-3］，未形成系统的理论体系，对不确定条件下的作业调度模型研究较少，文献［4］提出了一种不确定性条件下的生产调度模型，该模型采用决策系数策略，在用智能算法求解模型时通常使用随机取权的方法.文献［5］研究了以生产成本及设备利用率指标为调度目标的车间调度问题，建立了一个面向各种生产资源约束的多目标优化调度模型，但其模型仍然为单层的线性模型，将各函数利用权值相加，结果受权值参数干扰很大.

针对以上问题，本文提出一种新的不确定条件下的作业车间多目标调度模型，该模型为双层调度模型，分别以作业时间最短和成本最低为调度目标，采用Pareto最优解［6］得到调度序列.其中的成本调度目标，不仅考虑到了车间调度问题中常见的生产资源约束、成本约束问题，还兼顾了企业中的机器使用率问题，具有很高的实用性.此外，本文采用遗传算法对新模型求解，针对新的调度模型提出了一种改进的多目标遗传算法，该算法先利用遗传算法针对需要进行调度的作业进行调度运算，生成作业时间最短、机器空闲时间最小的解，再在这组解中评估生产成本，得到一组Pareto最优解，可以在兼顾机器使用率的同时使生产成本最小化.本文采用某机车厂的一组实际生产数据对改进的算法进行了验证，结果证明了新调度模型及其改进算法的有效性.

1 不确定条件下的作业车间多目标调度模型

1.1 不确定条件分析

在企业的生产过程中，会遇到各种各样的不确定因素［4］，如订单取消，劳动力因素，每道工序中产品的作业时间、中间存储单元的存储量等;生产中机器故障，急件加工等情况也是不确定条件;此外，企业的资源优化配置也属于不确定因素，需要对各种生产资源进行优化配置，以使企业的生产成本更低，赢得最大的经济效益.本文将以作业车间为生产背景，分析生产过程中影响调度作业的各种因素，从一般车间扰动情况和生产成本最小两方面对作业车间调度进行建模，因此，此问题实质上是一个多目标的决策问题.

1.2 不确定条件下的作业车间多目标调度模型

传统的作业车间多目标调度模型［4-5］仅是简单的将生产成本、生产周期等目标加权后相加，其权值带有一定的随机性，最后简单对未加工的任务进行重新计算，其调度结果不仅在实质上是一个单目标的调度结果，缺乏客观性，且调度结果对参数改变很灵敏.因此，针对传统模型存在的缺点，本文提出了一种新的不确定条件下的作业车间多目标调度模型，该模型是一个双层调度模型，在兼顾调度时间最短的基础上，同时寻求发生车间扰动(例如机器损坏、加工时间延迟、紧急订单等)之后的生产成本、管理费用、库存费用的最小化，以达到利益的最大化和资源消耗的最小化.

新模型对参与调度的生产任务从加工时间、生产效率、双资源(机器和人)的利用率、在库管理成本四个方面分别进行了评估，并提出了集约工程的概念，即为了节省生产成本而使同种零件(定义为工艺相同且工艺顺序相同的零件)批量制作的方法.

新的作业车间多目标调度模型描述如下:

模型的调度对象为发生车间扰动(例如机器损坏、加工时间延迟、紧急订单等)之后，规定已着手的任务继续做完，则剩下的未加工任务均为进行生产调度的对象.

为描述调度约束，给出如下符号定义:对于车间要生产的工件i，其订单生产数量用xi表示，ai为当前调度实际生产数量;oij表示工件i的第j道工序;Ti为第i个工件生产完工时间;tij为第i道工序在第j台机器上的作业时间，rtij为第i个工件使用第j台机器前需要的机器准备时间;ctij为第i个工件在第j道工序完毕后搬运至下一工序所用机器的时间，则第i个工件的第j道工序作业时间为(rtij+tij+cij);sdayi为第i个工件在生产完毕入库或存放在临时存储中心后至下次出库(包括出库直接售卖情况和出库后进行装配情况)所产生的库存停滞天数;mlj为第j台机器未进行加工使用的空闲时间.

为描述企业的各项成本，给出如下符号定义:调整设备单价hm指人操作机器的人工成本;企业日常的仓库管理工作中，管理一天仓库所发生的费用为am;部门单价dmj为根据部门设备种类不同而分别设定的部门劳动单价，在求解模型中可以根据某工件i在该道工序占用的机器j的类别来确定需要使用何种部门单价.

假设在机器损坏，来紧急订单后，对于工件i的第m道工序，已完成生产的数量为yi，紧急订单拆分工件后，需要新加工的工件i数量为zi，则新模型的数学描述为:

在式(1)中，模型M是由2个因素组成的向量，Timefitness为时间向量，Cost为成本向量，各个因素的详细描述如下:

(1)时间评估因素Timefitness

车间调度的目标之一是调度时间的最小化，不确定条件下的作业车间调度模型同样要求得到的调度作业序列是一个作业时间最短的序列.而在企业的生产车间中，往往是n个加工顺序不同的工件以不同的时间在m台机器上完成加工，工序之间往往存在前后约束，所以调度时间的目标应该是最小化最大完工时间［7］，所以，模型运用式(3)得到每一个调度作业序列所包含工件的最大完成时间，即Cmax，式(4)定义了调度模型的调度任务，即调度序列不包括已完成的工序或工件，且不包括已着手的工序(该部分工序应该继续加工至该工序结束后再安排它工序);运用式(2)描述了模型对于时间评估因素的要求，即得到的N个调度方案中要求取调度时间最小化的调度作业序列.

运用式(2)和式(3)评估调度时间，可以按照调度时间最小化合理调度安排各作业，同理，各个作业间如果进行了合理调度，则各机器空余时间自然会现对变少，满足作业车间对加工时间最小化的目标.

(2)生产效率因素pd

不确定条件下的调度问题包括当车间发生扰动(例如机器损坏、加工时间延迟、紧急订单等)之后的车间调度，所以在建模中必须考虑到各工序间的生产成本问题，对此，本文提出一种集约生产的概念，即为了节省生产成本而使同种物品(定义为工艺相同且工艺顺序相同的零件)批量制作，可以节省大量的机器准备时间和物品搬运时间，从而提高了生产效率.式(5)、(6)定义了模型对于各成本的调度要求，即成本和要求最小化.式(8)则说明了工件i的实际生产数量ai，即如果某工件在调度时刻，存在m道已完成工序或m道已着手工序，则集约生产的数量仅取原任务数量，新订单的工件i作为新任务参加调度;如果某工件已生产结束了yi数量，且无已完成工序或已着手工序，则集约生产的数量取xi－yi+zi;式(7)详细描述了新模型对于生产效率的要求.

(3)双资源利用率因素mm

通常情况下，在车间发生扰动之前，车间的资源已进行了组合分配，那么，在扰动发生之后，必须重新分配车间资源，所以，不确定条件下的调度问题必须考虑的另一个影响因素是双资源制约因素.本文提出了控制人和机器的等待时间最小以使人的劳动成本和机器的使用成本达到最高的策略，其具体控制策略通过式(9)实现为所有机器未进行加工的时间和，乘以hm(即人操作机器的人工成本)可以得到对机器进行调整时或机器空闲，手工闲置时的双资源利用成本.

(4)在库成本因素sc

工件在车间加工完毕后，一般将送至仓库或临时存储中心进行保管.为了降低车间的存储成本，管理要求工件在仓库或临时储存中心的停滞时间尽量缩短，即在满足交货期的前提下使库存物品或临时存储中心的工件存放数量达到最少.针对此问题，本文提出式(10)来计算在库成本(包括使用仓库或临时存储中心的成本)，描述了工件i的在库成本为工件i的在库停滞天数乘以管理仓库的单价费用，且停滞天数越少，在库成本越小，式(6)描述的成本费用会越低，达到追求成本最小化的调度目标.

2 求解新模型的多目标遗传调度算法

遗传算法(Genetic Algorithms，GA)是由美国密执根(Minchigan)大学的Holland教授于1975年首先提出的一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，因其算法本身简单，具有本质并行性等优点［8］，广泛应用于各种优化领域.至今，遗传算法在调度领域中己经得到了比较广泛的应用，国内外学者发表了大量应用遗传算法解决调度问题的文章［9］，遗传算法对于调度问题的适用性已得到肯定.因此，本文采用了遗传算法对上述提出的新模型进行求解.

新模型采用向量来描述不确定条件下的作业车间调度目标，所以调度结果采用Pareto最优解是一个可行的方法.此外，车间调度的目的是根据各种制约条件，生成可行的调度以指导生产，如果提供一组解，那么调度人员需要请专家指导在Pareto最优解进行最终选择，算法缺乏实用性.因此，本文采用一种改进的多目标遗传调度算法来求解新模型，其算法基本框架为:得到需要进行调度的生产任务，根据模型规则计算各工件的生产数量，确定调度任务，优化生成调度时间最小的解，然后在这组解中评估各个成本因素，得到Pareto最优解，取成本函数最小的染色体进行最优保留策略［10］，循环迭代后，输出总体成本最优的解.该策略同时兼顾了调度时间最小化和各项生产成本的最小化.

改进的多目标遗传算法步骤如下:

Step 1:得到需要进行本次车间调度的生产任务，规则为:

调度的任务=原有任务+紧急订单任务－已着手的任务－已完成任务

Step 2:进行集约生产统计，将同种工艺且同样工艺顺序的工件集中进行生产.

Step 3:初始化染色体.

Step 4:运行遗传算法，进行交叉，变异，以本文的式(2)为目标函数进行优化.

Step 5:采用本文提到的式(3)计算种群中每个染色体的综合成本函数值，按照函数值最小的原则更新本次循环的Pareto非劣解.

Step 6:运用本次循环成本最小的染色体进行最优保留策略.

Step 7:重复step 4-step6，直至满足结束条件.

Step 8:将车间的已着手任务作为每个染色体最前面的基因.

Step 9:输出综合成本最优结果.

利用改进的多目标遗传调度算法求解调度模型，可以提供一个同时兼顾调度时间最小、机器利用率最高和综合成本最小的调度方案，具有很高的实用性.

3 仿真实验

本文将采用改进的多目标遗传算法对新模型进行试算，同时鉴于各个调度模型关注的调度目标不同，而本文同时关注了调度时间、生产效率、双资源利用率、库存成本四个方面，所以为了说明新模型可以提供兼顾调度时间最少和成本最小化的调度方案，本文将采用文献［4-5］中的随机加权法来测试对以上四个调度目标的改进.

仿真实验中，遗传算法的种群规模为6，最优解集规模为3，运用最优保留策略［10］，染色体采用基于自然数的编码方法［11］，单点交叉［6］，交换变异［6］，共运行30代，系统环境，测试数据、系统参数设置及预设车间情况如下:

(1)系统环境

操作系统:Microsoft Windows XP Professional版本2002

内存:512MB

CPU:2.80Hz

编程语言:C语言

(2)测试数据

采用了某机车厂的部分生产数据.关键数据如表1:

表1 测试所用生产数据

(3)算法参数

为了计算方便，设式(7)所有机器类别的dmj=1.0;设式(9)中 hm=0.4;式(10)中 am=0.6;设原订单的生产数量，工件1为10，工件2为5;设重调度时刻，工件2的第一道工序已着手，紧急订单需要2个新的工件2，5个工件1.

试算的结果如表2(迭代次数为系统随机选取):

表2 改进的遗传多目标算法仿真结果

表3为采用随机加权法的遗传算法运算结果，可以看出，由于各成本因素权值不定，导致染色体的进化不稳定，易陷入局部最优解;且适应度并不能直观反映出染色体的调度时间和成本优劣情况.而表2可以看出，本文采用改进的多目标遗传调度算法求解双层调度模型，能够有效地同时对调度时间和成本进行优化，保持基本一致的种群进化方向，得到的调度时间目标较随机加权的遗传算法更为优秀，可以更为有效地解决调度中常见的生产资源约束、成本约束问题.

表3 采用随机加权法的遗传算法仿真结果

4 结论

本文提出的不确定条件下的作业车间多目标调度模型相对于传统作业车间多目标调度模型，从调度时间目标和成本目标上分别进行优化，不仅考虑到了生产调度中常见的车间扰动问题、成本问题，还兼顾了企业中的机器使用率问题，具有很高的实用性;相应的改进算法引入了“集约生产”的思想，减少了机器准备时间，降低了生产成本，得到的Pareto最优解，可以在兼顾机器使用率的同时使生产成本最小化.

［1］刘明周，单晖.不确定条件下车间动态重调度优化方法［J］.机械工程学报，2010.45(10):137-141.

［2］陈知美，顾幸生.基于蚁群算法的不确定条件下的Job Shop调度［J］.山东大学学报(工学版)，2005，35(4):74-79.

［3］丁雷，丁爱民，宁汝新.工时不确定条件下的车间作业调度技术［J］.计算机集成制造系统，2010，16(1):98-103.

［4］顾幸生.不确定性条件下的生产调度［J］.华东理工大学学报，2000，26(5):441-444.

［5］鞠全勇，朱剑英.多目标批量生产柔性作业车间优化调度［J］.机械工程学报，2007，43(8):148-151.

［6］王小平，曹立明.遗传算法:理论、应用及软件实现［M］.西安:西安交通大学出版社，2002:52-55，73.

［7］何彦.面向绿色制造的机械加工系统任务优化调度方法研究［R］.重庆:重庆大学，2007:79-80.

［8］PENG Wu-liang，WANG Cheng-en.Critical chain method project scheduling based model and its GA solution［J］.Journal of Systems Engineering，2010，25(1):125-133.

［9］周辉仁，郑丕谔，安小会，等.基于遗传算法求解Job Shop调度优化的新方法［J］.系统仿真学报，2009，21(11):143-146.

［10］何琳，王科俊，李国斌，等.最优保留遗传算法及其收敛性分析［J］.控制与决策，2000，15(1):63-66.

［11］杨晓梅，曾建潮.采用多个体交叉的遗传算法求解作业车间问题［J］.计算机集成制造系统，2004，10(9):1114-1118.