Open shop复杂调度网络模型及特征分析

给出open shop 复杂调度网络模型,即通过将open shop复杂调度对象描述成复杂网络,并将相关的复杂调度问题描述成对应复杂网络上的节点遍历问题,从而将复杂调度问题纳入复杂网络理论体系进行研究.分析几个复杂调度网络场景的一些基本结构特征,发现复杂调度网络具有小世界、模块化等很多现实复杂网络共同具有的特点.前者说明调度对象事件之间具有较强的局部和全局耦合；后者能够为分块解决复杂调度问题提供理论基础.复杂调度网络中的平均度值和平均聚类系数与调度目标即网络平均遍历时间具有较强的关联,网络平均度值和网络平均遍历时间基本满足对数关系,这为后续设计基于复杂网络特征的调度规则提供启发式信息.给出网络可折叠度的概念,发现复杂调度网络本质上具有较大的网络可折叠度,可以通过折叠复杂调度网络来降低它的复杂度，从而提高后续的分析和算法执行效率.

Open shop complex scheduling network model and characteristic analysis

An open shop complex scheduling network was provided. The related complex scheduling problems were transferred to node traverse problems on complex scheduling network and studied under the framework of complex network theory through building complex network models for open shop complex scheduling objects. Then some structural characteristics of several complex scheduling network scenes were analyzed. Results show that the complex scheduling network has small world and modular properties as many other real world complex networks. The former means there are strong local and global coupling among scheduling events, and the latter can provide the theoretical basis for dividually solve complex scheduling problems. There are also strong correlation between the average degree/clustering coefficient and the average traverse time of complex scheduling network, and the average traverse time grows logarithmically as the average degree increases, which will provide heuristic information for designing novel scheduling rules based on complex network characteristics in the future. The definition of network foldability was provided. Results show that complex scheduling network has large network foldability essentially. The complexity can be largely decreased through a folding process, and the following analyzing and therefore scheduling algorithm efficiency will be largely improved.