动态单机调度的一种滚动时域策略及全局性能分析

针对全局信息不完全的一种单机的动态调度模型,设计了局部调度子问题带终端惩罚函数的滚动调度策略,并对这种滚动调度策略下的全局性能进行了分析.通过对未知工件按FIFO规则进行虚拟调度,对滚动调度进程中的全局性能进行评估,证明了在所给滚动调度策略下,随着工件信息的逐步获取,全局调度中的虚拟调度逐步变为已知调度,并经过滚动局部调度而部分实现,决策时刻向前推进,对全局性能指标的估计越来越接近将实现的实际值,逐步实现的全局调度性能相对历次的估计值不断改善.终端罚函数滚动调度策略可以保证滚动调度进程中全局性能的稳定性,当工件到达较快时,文中的滚动调度策略更有优势.

A Rolling Horizon Strategy for Dynamic Single-machine Scheduling Problem and Analysis of the Global Performances

A rolling horizon strategy for the single-machine scheduling problems with incomplete global information was presented. A terminal penalty function was appended to the objective function of each sub-problem in the rolling scheduling strategy. The global performances were analyzed. The global procedural performance was estimated based on a virtual schedule for unknown jobs using FIFO rule. When information of partial jobs is obtained, the partial virtual schedule is specified, locally scheduling is made based on known jobs, and a partition of the local schedule is implemented. It is concluded that while the decision time is being put forward, the estimation of the global performance is getting close to the ultimately implemented actual cost and getting better and better step by step. It is assured that global performance is consistently not worse than that of FIFO anyway. This kind of rolling scheduling strategy is more advantageous when jobs release rapidly.