不确定条件下车间调度混合算法的调度优化策略

党欣旸

摘要：随着时代的发展，国际经济竞争日趋激烈。人们对产品的要求逐步增高，使得企业对工件的时间规划和做工要求上更加精益求精。實际生产的不确定性也越来越受到各界的重视，诸如机器发生故障的不确定性、用户具体要求的模糊性、工件实际加工时间的模糊性等不确定因素也在车间调度中被加以考虑。而这类问题也由于更接近于实际生产活动而倍受关注，诸类不可预测事件具有动态性，相较于确定性的问题难度有所加深，算法也更加复杂。通过众多学者的不断努力，目前已经出现不少的研究成果。

关键词：生产调度；不确定性；调度建模；调度算法

1.随机模拟和期望值函数

车间调度问题作为一个NP复杂度问题，通常用一个非线性规划模型来描述。随机规划模型的一般表示形式为（1.1）：

期望值反映的是变量的平均值，能够一定程度上体现随机变量的某些特征。期望值对一些随机问题具有非常重要的意义。因此，如果利用随机变量期望值的性质，上述（1.1）可以转化为下面的随机规划模型：

2.随机模拟目标函数的确定

用Ri表示车间中的m台可用设备；n个工件则对应了有Tn个订单生产任务，每个工件包含Ki道工序来源于其对应的加工工序集OPiKi并由它决定了Ti的取值，记作Ti={OPi1，OPi2，…，OPiKi}；设备用Rj（1

在实际生产的过程中可能会产生许多不确定的客观因素而影响调度的执行，从而影响实际作业需要完成的目标。所以要对调度进行优化，本文的优化目标是完工时间较短和成本消耗较低。对于一个需要进行生产调度的订单来说，由于所包含的零部件的工艺复杂性程度存在差别，可以取“最慢工件任务的完工周期最短”作为时间目标，设置信概率为η，pt表示平均加工时间，则可以用机会约束描述为：

3.生成目标函数

车间调度的目标之一是调度时间的最小化，不确定条件下的作业车间调度模型同样要求得到的调度作业序列是一个作业时间最短的序列。而在企业的生产车间中，往往是n个加工顺序不同的工件以不同的时间在m台机器上完成加工，工序之间往往存在前后约束，所以调度时间的目标应该是最小化最大完工时间，所以，模型得到每一个调度作业序列所包含工件的最大完成时间，即Cmax，定义了调度模型的调度任务，即调度序列不包括已完成的工序或工件且不包括已着手的工序（该部分工序应该继续加工至该工序结束后再安排它工序）；运用描述了模型对于时间评估因素的要求，即得到的N个调度方案中要求取调度时间最小化的调度作业序列。评估调度时间，可以按照调度时间最小化合理调度安排各作业，同理，各个作业间如果进行了合理调度，则各机器空余时间自然会现对变少，满足作业车间对加工时间最小化的目标。基于这些考量，目标函数可以表示为：

小结

本章采取通过神经网络逼近随机模拟的方式，成功的模拟了实际加工情况中的动态事件发生的不确定性，并用改进的优化算法寻优并与单纯的遗传算法和退火模拟算法做对比显示出了改进算法的优越性。（作者单位：大连交通大学）

参考文献：

[1]王书锋，邹益仁.车间作业调度（JSSP）技术问题简明综述[J].系统工程理论与实践.2003，1：49-55.

[2]陈永亮，徐燕申，张冠伟.基于知识的模块化柔性生产线快速设计系统.组合机床与自动化加工技术，2002（7）：4一20.

[3]范路桥，常会友，朱旭东.作业调度问题研究[J].现代计算机（专业版），2005，187：21-25.

[4]X U Zhenhao，GU Xingsheng.Scheduling algorithm for flow-shop under uncertainty with zero wait [J].Computer Integrated Manufacturing Systems，2004，10（10）：1247-1251.

[5]李郝林，施展.遗传算法在生产调度应用中的关键技术[J].组合机床与白动化加工技术，2003，7：27-31.