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

Network model and heuristic scheduling rule designing method for complex open shop problems

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

With the reason that there still lacks of a systematical method to design scheduling rules,a framework to systematically design heuristic scheduling rules based on complex network theory was proposed.Through describing complex open shop（COS） objects by complex scheduling networks,the related complex scheduling problems can be transferred to node executing problems on complex scheduling networks,then complex scheduling problems can be studied under the background of complex network theory.Then through node executing experiments on different complex scheduling networks,it is found that the network average executing time increases logarithmically as the average degree characteristic of the complex scheduling network rises.This fact provides the theoretical basis for designing the scheduling rule based on node degree,that is,minimize the average degree of the remaining complex scheduling network by priorly executing those nodes with large degree.Computer simulations show that,compared with other scheduling rules,the proposed node degree based scheduling rule can indeed produce better maximum finish time（MFT） properties.