预测调度算法在平行机问题中的应用  

Application of Predictive Scheduling Algorithm to Parallel Machine Problems

作　　者：周俊杰[1] 巢志骏[1] 席裕庚[1] 

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

出　　处：《控制工程》2008年第5期534-537,563,共5页Control Engineering of China

基　　金：国家自然科学基金资助项目(60474002;60504026);国家863计划基金资助项目(2006AA04Z173)

摘　　要：常用的实时生产调度的在线算法由于只利用当前已到达的工件信息,导致调度性能不够理想。针对复杂度较高的平行机调度问题,通过对在线算法OMPR(单机可中断松弛)的改进,设计了一种具体的预测调度算法PPSA(平行机预测调度算法)。预测调度算法合理地把预知信息与已知信息结合起来进行决策,使调度解的性能得到进一步提高。仿真分析显示,该算法的性能明显优于在线算法OMPR,表明预测调度算法是一种计算简单、性能优良的实时调度算法。The performance of the currently most used online scheduling algorithms is unsatisfactory because they only use the information of arrived jobs. For the parallel machine problem with high complexity, a specific parallel predictive scheduling algorithm （PPSA）is presented by modifying the online algorithm OMPR. Predictive scheduling algorithms combine some future information with known information reasonably to make decision so that the scheduling performance can be further improved. Simulation results show that the performance of PPSA obviously outperforms that of the online algorithm OMPR, and that the predictive scheduling algorithm is a simple and qualified real-time scheduling algorithm.

关 键 词：预测调度算法 在线算法 性能比 平行机 

分 类 号：TP27[自动化与计算机技术—检测技术与自动化装置]