动态车间调度问题调度规则算法仿真试验的样本容量确定方法

熊禾根，钱国洁，范华丽，蒋国璋

（武汉科技大学 机械自动化学院，武汉 430081）

0 引言

车间作业调度问题是制造系统信息化与自动化技术需要解决的关键问题之一，是先进制造技术中的重要研究主题，也是运筹学研究的热门问题之一。基于调度要素相关信息获取的时间特性，车间调度问题可分为静态和动态两种类型。在绝大多数实际制造系统中，作业任务是陆续到达的，属于动态调度问题。此外，与经典调度问题相比，实际制造系统的调度问题中通常包括许多复杂和不确定因素，因而，在求解算法方面，虽然学者及工程技术人员提出了诸多智能算法，如进化类算法[1,2]、蚁群算法[3,4]、粒子群算法[5,6]、专家系统方法[7,8]、神经网络算法[9,10]等，但基于调度规则的算法仍以其求解复杂大规模动态调度问题经济、快速而有效的特点得到许多研究者的关注，并在实际调度系统中得到较广泛应用。在过去的50余年中，各类文献资料中所提出的调度规则已有上百种；然而，由于调度规则的性能好坏与求解问题的模型密切相关的，且目前尚无有效的解析方法可对规则性能进行有效的分析评价。因此，对于调度规则的使用，多数研究者一般基于已有的研究结果，先在已提出的调度规则初步甄选出若干规则，或尝试开发一些新调度规则；然后采用模拟实验的方法，对具体调度问题进行调度仿真，通过对仿真结果的统计分析，来评价调度规则于具体调度问题的性能[2]。

1 相关研究及问题提出

德国帕绍大学Holthaus和印度理工学院Rajendran是对调度规则设计、仿真及评价研究最多的学者。文献[3]提到重复仿真次数为10次；文献[4～6]中提到独立仿真次数为20次；文献[7]中提到的独立仿真次数为30次；文献[8]中提到的迭代次数为100。可见，在不同文献中，关于独立仿真次数的采用有所差别，且尚无一个公认基准，文献中也未给出采用相应仿真次数的理论依据。显然，把仿真调度看做一种随机试验，从统计学意义上，独立仿真次数越多，仿真数据的统计结果更能反映总体特性；但另一方面，对于复杂大规模调度问题来说，更多独立仿真次数必然需要付出更大的代价。因而，在满足一定置信度和置信区间内，合理的仿真次数应该为多少，其研究具有重要意义。

2 样本容量的确定方法

2.1 基本思路

基于调度规则的仿真调度过程实际上相当于一个随机试验过程。采用一个调度规则进行一次仿真调度，相当于进行一次随机试验抽样，所得到的某个调度性能指标值（如最大完工时间、最大延期/拖期、总延期/拖期、拖期工件总数/百分比等）即是一个抽样观测值。仿真调度的目的是对不同调度规则进行若干次仿真调度，相当于进行多次抽样，根据抽样结果，进行合理的统计分析，以对不同调度规则性能进行比对，判断其性能差异是否具有统计学意义，差异程度如何，孰优孰劣，从而为实际调度系统应用中调度规则的选择提供参考。

2.2 确定方法

2.2.1 抽样方法

基于所需考察的动态调度问题模型，以车间为空闲状态开始（即所有机器均闲置，其前无加工队列），生成仿真调度案例。初始阶段，车间的任务量较少，显然，此时即开始采样将产生初始偏误。应待车间达到稳定状态时开始进行有效数据的采样。许多文献提到500个工件到达后可认为车间达到稳定状态，因此，有效的采样从第501个到达的工件开始[9]。动态车间系统可以看作是一种“非中断式”系统，仿真采样需要关注的是调度性能指标的长期平均值或稳态行为。文献中通常以到达稳定状态后完成2000个工件的加工作为系统达到对其长期行为的一个合理近似。因此，采样的结束可按第2500个工件加工完成为节点，为保持采样一直处于车间稳定状态，在第2500个工件完成之前，需保持工件一直按模型陆续到达车间。

2.2.2 计算公式与步骤

1）样本容量的计算公式

对于动态车间作业调度仿真试验来说，样本容量即是独立仿真调度的次数。样本容量越大，样本的统计量与总体的统计量越接近；对应地，仿真调度所获得的性能指标值能更接近地反映其真值。但显然这样需要付出更多的消耗（计算时间或成本等）。可以认为总体是服从正态分布的，以多次仿真调度所获得的性能指标值均值作为统计量，在总体方差未知的情况下，有：

令Δ表示均值估计偏差，即：

可得样本容量为：

在确定置信度1-α及均值估计偏差Δ后，可由式(3)计算所需样本容量，即独立仿真调度的运行次数。然而，因式(3)右侧的t分布的双侧1002/α百分位点与n有关，因此，需通过试算确定样本容量。

2）样本容量的计算步骤

基于上述的公式与方法，样本容量的计算步骤叙述如下。

Step3：查t分布分位数表，并由式(3)计算n值；

3 仿真案例

动态车间调度模型的仿真基本数据如下：车间机器数量为10，车间利用率取为85%，每个工件所含工序数量由离散均匀分布DU[3，6]产生，工序工时由均匀分布U[5，15]产生，交货期设置的宽裕度系数取为6。采用MDD（Modif i ed Due-Date）调度规则，进行若干次仿真调度。记拖期工件数量为T，以拖期工件百分比T%为性能指标。取置信度为99%，拖期工件百分比均值的估计偏差为±2%。仿真调度的原始数据及统计分析结果如表1所示。表中指标及统计量计算方式如下：

由表1可知，置信度99%下拖期工件百分比均值估计偏差为±2%时的样本容量为17，即需要独立运行17次仿真调度，可满足要求。

事实上，由表中数据可知，一定次数运行后方差相对比较稳定，因此，一种简略而变通的估计方式是：进行一定次数的独立仿真运行（如取），对方差取均值，即：

此后，可不再继续运行，将方差固定取为，再根据式(3)及t分布分位数表估计样本容量。

4 结论

仿真调度是评价调度规则性能好坏最常用的方法。一次仿真调度相当于一次随机试验。为使评价结果具有统计学意义，且尽量降低仿真试验的代价，有必要合理确定仿真调度的运行次数。本文将统计学的区间估计方法应用于仿真试验调度设计中，推导了样本容量的计算公式，提出了样本容量的确定方法，并进一步利用仿真案例进行了说明。

表1 仿真调度数据及统计分析结果

[1] 王凌,郑大钟.基于遗传算法的Job Shop调度研究进展[J].控制与决策,2001,16(Z1):641-646.

[2] Wannaporn Teekeng,Arit Thammano.Modif i ed Genetic Algorithm for Flexible Job-Shop Scheduling Problems[J].Procedia Computer Science,2012(12):122-128.

[3] Rajendran Chandrasekharan, Ziegler Hans. Ant-colony algorithms for permutation fl owshop scheduling to minimize makespan / total flowtime of jobs[J].European Journal of Operational Research,2004,155(2):426-438.

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

[5] 宋晓宇,曹阳,孟秋宏.求解Job Shop调度问题的粒子群算法研究[J].系统工程与电子技术,2008,30(12):2398-2401.

[6] Koulinas Georgios,Lazaros Kotsikas,Konstantinos Anagnostopoulos. A particle swarm optimization based hyperheuristic algorithm for the classic resource constrained project scheduling problem[J].Information Sciences,2014,277:680-693.

[7] David A. Ress,Kenneth R.Currie. Development of an expert system for scheduling work content in a job shop environment [J].Computers & Industrial Engineering,1993,25(1-4):131-134.

[8] 曾明如,游文堂,钱信,韩伟.基于专家系统的货位管理与作业调度优化[J].南昌大学学报(工科版),2009,31(4):385-388.

[9] Haibin Yu,Wei Liang.Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling[J].Computers &Industrial Engineering,2001,39(3-4):337-356.

[10] 刘辉,陈友玲.基于客户满意度的模糊神经网络JSP研究[J].世界科技研究与发展,2011,33(5):809-813.

[11] 熊禾根,李建军,孔建益,杨金堂,蒋国璋.考虑工序相关性的动态Job shop调度问题启发式算法[J].机械工程学报,2006,42(8):50-55.

[12] Holthaus Oliver,Rajendran Chandrasekharan.Efficient dispatching rules for scheduling in a job shop[J].Int.J.Production Economics,1997,48:87-105.

[13] Holthaus O.Design of efficient job shop scheduling rules[J].Computers ind. Engng,1997,33(1-2):249-252.

[14] Rajendran Chandrasekharan , Holthaus Oliver.A comparative study of dispatching rules in dynamic fl owshops and jobshops[J].European Journal of Operational Research,1999,116:156-170.

[15] Jayamohan M S,Rajendran Chandrasekharan. Development and analysis of cost-based dispatching rules for job shop scheduling[J].European Journal of Operational Research,2004,157:307-321.

[16] Holthaus Oliver.Scheduling in job shops with machine breakdowns:an experimental study[J].Computers and Industrial Engineering,1999,36:137-162.

[17] Chen Binchao,Matis Timothy I.A flexible dispatching rule for minimizing tardiness in job shop scheduling[J].Int. J. Production Economics,2013,141:360-365.

[18] Raghu T S,Rajendran Chandrasekharan. An efficient dynamic dispatching rule for scheduling in a job shop[J].Internationul Journal of Production Economics,1993,32:301-313.