Please wait a minute...
浙江大学学报(工学版)
J4  2011, Vol. 45 Issue (4): 589-595    DOI: 10.3785/j.issn.1008-973X.2011.04.001
自动化技术、电信技术     
Open shop复杂调度网络模型及特征分析
宣琦1，2, 吴铁军1
1.浙江大学 控制科学与工程学系,浙江 杭州 310027; 2.浙江工业大学 自动化系,浙江 杭州 310023
Open shop complex scheduling network model and
characteristic analysis
XUAN Qi1,2, WU Tie-jun1
1. Department of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China；
2. Department of Automation, Zhejiang University of Technology, Hangzhou 310023, China
 全文: PDF  HTML
摘要：

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

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.
出版日期: 2011-05-05
:  TP 11  
基金资助:

中国博士后科学基金资助项目(20080441256).
通讯作者: 吴铁军，男，教授.     E-mail: tjwu@zju.edu.cn
作者简介: 宣琦(1981—)，男，浙江诸暨人，副教授，从事复杂网络研究.E-mail：crestxq@hotmail.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　

引用本文:

宣琦, 吴铁军. Open shop复杂调度网络模型及特征分析[J]. J4, 2011, 45(4): 589-595.

XUAN Qi, WU Tie-jun. Open shop complex scheduling network model and
characteristic analysis. J4, 2011, 45(4): 589-595.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2011.04.001    或    https://www.zjujournals.com/eng/CN/Y2011/V45/I4/589

［1］ 宣琦.基于复杂网络理论的复杂调度问题求解方法研究［D］.杭州: 浙江大学, 2008.
XUAN Qi. Research on complex scheduling problems based on complex network theory ［D］. Hangzhou: Zhejiang University, 2008.［2］ BALAS E. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm ［J］. Operations Research, 1969, 17(6): 941-957.
［3］ 吴哲辉.Petri网导论［M］.北京: 机械工业出版社,2006: 19-23.
［4］ GOVIL M K, FU M C. Queueing theory in manufacturing: a survey ［J］. Journal of Manufacturing Systems, 1999, 18 (3): 214-240.
［5］ 莫瑜.健壮性图着色问题算法及应用［D］.广州:中山大学, 2006.
MO Yu. Algorithm for robust graph coloring problem and its application ［D］. Guangzhou: Sun YatSen University, 2006.
［6］ ALBERT R, BARABSI AL. Statistical mechanics of complex networks ［J］. Reviews of Modern Physics, 2002, 74(1): 47-97.
［7］ BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: structure and dynamics ［J］. Physics Reports, 2006, 424 (4/5): 175-308.
［8］ WATTS D J, STROGATZ S H. Collective dynamics of ‘smallworld’ networks ［J］. Nature, 1998, 393(6684): 440-442.
［9］ BARABSI AL, ALBERT R. Emergence of scaling in random networks ［J］. Science, 1999, 286(5439): 509-512.
［10］ RAVASZ E, SOMERA A L, MONGRU D A, et al. Hierarchical organization of modularity in metabolic networks ［J］. Science, 2002, 297(5586): 1551-1555.
［11］ XUAN Q, LI Yanjun, WU Tiejun. Growth model for complex networks with hierarchical and modular structures ［J］. Physical Review E, 2006, 73(3): 036105.
［12］ XUAN Qi, LI Yanjun, WU Tiejun. A localworld network model based on internode correlation degree ［J］. Physica A: Statistical Mechanics and its Applications, 2007, 378(2): 561-572.
［13］ DROZDOWSKI M. Scheduling multiprocessor tasks: an overview ［J］. European Journal of Operational Research, 1996, 94(2): 215-230.
［14］ PINEDO M L. Scheduling: theory, algorithms, and systems ［M］. 2nd ed. 北京：清华大学出版社, 2005: 35-61.
［15］ COSTA L DA F, RODRIGUES F A, TRAVIESO G, et al. Characterization of complex networks: a survey of measurements ［J］. Advances in Physics, 2007, 56 (1): 167-242.
［16］ TAILLARD E. Benchmarks for basic scheduling problems ［J］. European Journal of Operational Research, 1993, 64(2): 278-285.
［17］ ERDS P, RNYI A. On random graphs ［J］. Publicationes Mathematicae, 1959, 6: 290-297.
［18］ RAVASZ E. Evolution, hierarchy and modular organization in complex networks ［D］. Indiana: University of Notre Dame, 2004.
[1] 宣琦, 吴铁军. 复杂open shop问题的网络模型及
调度规则设计[J]. J4, 2011, 45(6): 961-968.