论文部分内容阅读
调度算法的性能分析,由于其在实际应用中对提高生产效率起着至关重要的作用,从而吸引了众多学者的兴趣。而预测调度算法由于可以充分利用生产过程中的任务信息,所以能比只利用当前时刻信息的在线算法更有效地进行调度。而相比起必须提前知道所有信息进行优化的离线算法,预测调度算法对加工环境的信息约束又有着很强的适应性。然而,目前已有文献针对预测调度算法的性能分析还几乎是空白。本文主要借鉴在线算法性能分析的手段和方法,并发展出实例转换的全新分析方法,对预测调度算法在最小化完工时间问题中的设计与性能分析进行了研究。首先,通过算法集划分和构造相应极端实例,我们得到了1|r_j|∑C_j问题预测调度算法的竞争比下界,从而确定预测调度算法针对该问题的性能极限。之后,我们分别针对1|r_j|∑C_j和P |r_j|∑C_j问题设计了三种单步预测调度算法,从竞争比和平均性能比角度进行了性能分析,发现它们都远优于在线算法。本文主要研究成果包括:1)对于1|r_j|∑C_j问题,从在线算法D-SPT出发,设计出两种单步预测调度算法,在性能上大大改善了原在线算法。2)在对单步预测调度算法P-SPT1竞争比的求解中,创造性地提出了实例转换的求解思想,并获得了成功。这也是本文的重要理论贡献。3)通过划分算法集和构造特殊实例的手段,求解了1|r_j|∑C_j问题预测调度算法的竞争比下界。从相反的角度,刻画了预测调度算法随着预测步长的性能极限。4)对于更复杂的P |r_j|∑C_j问题,通过借鉴OMPR算法的两层调度结构,并利用已构造出的单机预测规则P-SPT1,设计了一种同速机单步预测调度算法,在性能上同样都远优于原在线算法。5)尝试将实例转换的方法推广应用于P-SPT2和P-PSA的竞争比求解中,但在实际的推导中遇到了一些障碍。我们将推导过程所存在的困难一一作了详细的描述和分析,并给出了一些可能的解决思路。这些工作为进一步的深入分析也有着借鉴和帮助意义。