非标准随机调度模型的最优动态策略

相对于确定性调度，随机环境下的调度除了调度的参数如就绪时间、处理时间、到期时间等具有随机的不确定性以外，另一个本质的特点是其调度计划具有动态的特性（这是由于，调度者对于未实现的随机变量的分布信息会在加工和调度过程中随着随机变量或其部分的实现而发生改变，信息的改变自然要求调整调度计划来保证策略的最优性），然而，随机调度的主流却是在静态策略类中寻找最优。另外，在标准的随机调度问题中总是假定机器处于良好状态，被加工工件或者产品不会腐坏，工件上累计的加工信息在机器中断时要么完全损失、要么完全保留，各个随机变量的分布已知，但是往往现实并非如此。因此本项目拟研究在机器带随机中断、产品可能腐坏、中断会造成工件加工信息的部分损失、或者关于随机变量的信息可能不完全等非标准条件下随机调度的动态最优策略及其相关的问题。

调度理论的基石是确定性调度理论，其一个显著显著特点是，到达时间、处理时间、到期时间等相关数据都是事先知道的。然而，在现实问题中，这些参数往往在实现了之后才会知道，对于这种问题的处理，发展了随机调度(stochastic scheduling)的理论。在随机调度中，根据技术条件的不同，策略有静态(static or permutation policies) 与动态(dynamic, adaptive or progressive policies)之分，而后者又可以分为完全动态策略(unrestricted dynamic policies)和不完全动态策略 (restricted dynamic policies) 。随机调度的重点应该是寻找最优动态策略。然而，文献中随机调度研究的绝大部分是将其转化为确定性调度问题进行研究并得到最优静态策略。标准的随机调度问题总是假定机器一直处于良好状态、无论工件在何时开始加工其加工时间的分布都与加工起始时间无关，各个参数随机变量的概率分布已知等。但是现实问题经常不满足这样的标准条件。.本项目组及其合作者在国家自然科学基金委项目《非标准随机调度模型的最优动态策略》资助下取得了如下的研究成果和进展：.(a) 带学习效果和随机中断的调度问题（time－varing随机调度问题）；(b) 具有不确定性工作损失的随机调度的一个统一方法；(c) 具有不可数状态和时间可回转的广义Bandit过程的最优决策方法；(d) 决策受限的最优停时问题。除了这些研究型的成果外，项目组成员在项目资助下还取得了如下的学术成果：（e）基本完成一部随机调度领域的专著《optimal stochastic scheduling》，以及一篇关于随机调度方面的综述性论文。