复杂open shop问题的网络模型及调度规则设计

摘要

针对当前调度规则设计缺乏系统性这一现状,提出一种基于复杂网络理论的系统化设计启发式调度规则的框架.通过将复杂open shop(COS)调度对象描述成复杂调度网络,并将相关的COS调度问题描述成对应复杂调度网络上的结点执行问题,从而将COS调度问题纳入到复杂网络理论体系下进行研究.在此基础上,通过在不同复杂调度网络上进行结点执行实验,发现复杂调度网络平均度值特征和网络结点平均总执行时间之间呈现对数关系.这一事实为设计基于度值的调度规则提供了理论基础,即优先执行度值大的结点,使得后续复杂调度网络具有尽可能小的平均度值.仿真实例证实,与其他调度规则相比基于度值的COS调度规则能够取得更好的最大完成时间(MFT)性能.