作业时间服从指数分布的调度规则失效率分析

汤健超，张国基，张毕西，林彬彬

(1．华南理工大学计算机科学与工程学院，广东广州 510641；2. 华南师范大学计算机学院，广东广州 510631；3. 华南理工大学数学科学学院， 广东广州 510641；4.广东工业大学管理学院，广东广州 510520)

作业调度的研究具有重要的理论意义和工程价值，由于许多作业计划调度问题已被证明是NP完全问题，求解此类问题的精确解,对于中等规模情形时的计算时间已超出人们能接受的范围．因此，现在通常通过各种启发式的方式,试图求解问题的较优解．

在各种调度规则中，有一类是基于工序时间的调度规则，如最小时间规则(SPT)、最大时间规则(MPT)、最短剩余加工时间规则(SRPT)、最小松弛时间规则(SL/OP)等[1-2]．这一类规则，调度决策的参数基于参数的预计值，通常为参数的期望．而实际作业时间是波动的，因此调度结果可能会与调度目标背离．如根据SPT规则，预计工序时间E(TB)tA，此时的调度结果与其目标是不一致的，此处称为“调度规则失效”[3]．而在各类生产系统的实际运作过程中，都面临着大量随机因素的影响[4]，这些因素既有生产系统的外部因素，如物料到货期变更；同时也包括生产系统的内部因素，如：机器故障，操作工人的状态影响对作业生产造成影响，从而使作业的时间呈现随机波动的性态．在这些波动的影响下，许多确定型的作业计划工具和方法效果欠佳[5]．因此，研究作业计划的随机性特征及其对作业计划的影响，有着重要的理论和实践研究意义．

但……