Please wait a minute...
浙江大学学报(工学版)
J4  2011, Vol. 45 Issue (4): 589-595    DOI: 10.3785/j.issn.1008-973X.2011.04.001
    
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
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      

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.

Published: 05 May 2011
CLC:  TP 11  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

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

URL:

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


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

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

［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.