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

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

调度问题中在线算法只能够利用已经到达的工件信息进行调度,但在实际生产中,往往有可能预知即将到达的未来工件信息,并且利用信息进行决策。针对经典单机加权完工时间调度问题,根据预测控制的思想,提出了一种单步预测调度的算法,并且分别在理论证明和仿真两方面进行了分析。对单步预测调度算法进行了性能分析,在理论上证明了预测调度算法的竞争比下界为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.