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

结题报告

项目介绍

AI项目解读

基本信息

批准号：
71071056
项目类别：
面上项目
资助金额：
28.0万
负责人：
吴贤毅
依托单位：
华东师范大学
学科分类：
G0102.运筹与管理
结题年份：
2013
批准年份：
2010
项目状态：
已结题
起止时间：
2011-01-01 至2013-12-31

项目参与者：
许忠好；温利民；俞雪梨；杨磊；王秀军；黄金龙；熊怡；张俊英；张晓寒；
关键词：
policies Deteriorating Incomplete Stochastic jobs machine Dynamic scheduling information.breakdowns

项目摘要

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

结项摘要

调度理论的基石是确定性调度理论，其一个显著显著特点是，到达时间、处理时间、到期时间等相关数据都是事先知道的。然而，在现实问题中，这些参数往往在实现了之后才会知道，对于这种问题的处理，发展了随机调度(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》，以及一篇关于随机调度方面的综述性论文。