单步预测的单机调度算法及其仿真分析  

Simulation Analysis of One-Step Predictive Algorithm for Single Machine Scheduling Problem

在线阅读下载全文

作  者:张颖[1] 巢志骏[1] 席裕庚[1] 

机构地区:[1]上海交通大学自动化系,上海200240

出  处:《计算机仿真》2009年第1期301-304,312,共5页Computer Simulation

基  金:国家自然基金(60504026);国家863计划(2006AA04Z173)

摘  要:调度问题中在线算法只能够利用已经到达的工件信息进行调度,但在实际生产中,往往有可能预知即将到达的未来工件信息,并且利用信息进行决策。针对经典单机加权完工时间调度问题,根据预测控制的思想,提出了一种单步预测调度的算法,并且分别在理论证明和仿真两方面进行了分析。对单步预测调度算法进行了性能分析,在理论上证明了预测调度算法的竞争比下界为2,对于一般的情况进行了大量的仿真比较,由于在调度中增加了未来信息,单步预测调度算法的调度结果优于在线调度算法。For scheduling problems, online algorithms only use the information of jobs that have arrived. But in real manufacturing environment, sometimes information about future jobs can be predicted and then be used in decision - making. This paper applies the predictive control theory to a classic scheduling problem, proposes a predictive scheduling algorithm and analyzes it by theoretical proof and simulation. The lower bound of it is proved to be 2, with regarding to the simulation of more general instances, single - step scheduling outperforms online scheduling because it takes more future changes into consideration.

关 键 词:预测调度 竞争比 下界 总加权完工时间 

分 类 号:TP18[自动化与计算机技术—控制理论与控制工程]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象