Please wait a minute...
浙江大学学报(工学版)
J4  2011, Vol. 45 Issue (6): 961-968    DOI: 10.3785/j.issn.1008-973X.2011.06.001
自动化技术、计算机技术     
复杂open shop问题的网络模型及
调度规则设计
宣琦, 吴铁军
浙江大学 控制科学与工程学系,浙江 杭州 310027
Network model and heuristic scheduling rule designing method for
complex open shop problems
XUAN Qi, WU Tie-jun
Department of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China
 全文: PDF  HTML
摘要：

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

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

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

引用本文:

宣琦, 吴铁军. 复杂open shop问题的网络模型及
调度规则设计[J]. J4, 2011, 45(6): 961-968.

XUAN Qi, WU Tie-jun. Network model and heuristic scheduling rule designing method for
complex open shop problems. J4, 2011, 45(6): 961-968.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2011.06.001    或    https://www.zjujournals.com/eng/CN/Y2011/V45/I6/961

［1］ 宣琦.基于复杂网络理论的复杂调度问题求解方法研究 ［D］.杭州: 浙江大学,2008.
XUAN Qi. Research on complex scheduling problems based on complex network theory ［D］. Hangzhou: Zhejiang University,2008.
［2］ 钱晓龙,唐立新,刘文新.动态调度的研究方法综述［J］.控制与决策,2001,16 (2): 141-145.
QIAN Xiaolong, TANG Lixin, LIU Wenxin. Dynamic scheduling: a survey of research methods ［J］. Control and Decision, 2001, 16 (2): 141-145.
［3］ PANWALKAR S S, ISKANDER W. A survey of scheduling rules ［J］. Operations Research, 1977, 25 (1): 45-61.
［4］ 李建详,唐立新,吴会江,等.基于规则的热轧钢管调度 ［J］.钢铁,2004,39 (9): 39-42.
LI Jianxiang, TANG Lixin, WU Huijiang, et al. Scheduling the production of hot rolling steel tube: a rulebased heuristics ［J］. Iron & Steel, 2004, 39 (9): 39-42.
［5］ 寿涌毅.并行工程项目调度的随机组合抽样算法［J］.浙江大学学报:工学版,2006,40 (2): 344-347.
SHOU Yongyi. Composite random sampling algorithm for scheduling concurrent projects ［J］. Journal of Zhejiang University: Engineering Science, 2006, 40 (2): 344-347.
［6］ 宣琦,吴铁军.Open Shop复杂调度网络模型及特征分析［J］.浙江大学学报: 工学版,2011,45(4): 589-595.
XUAN Qi, WU Tiejun. Open shop complex scheduling network model and characteristic analysis ［J］. Journal of Zhejiang University: Engineering Science, 2011, 45(4): 589-595
［7］ ALBERT R, BARABSI A L. Statistical mechanics of complex networks ［J］. Reviews of Modern Physics, 2002, 74(1):47-97.
［8］ BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: structure and dynamics ［J］. Physics Reports, 2006, 424 (45): 175-308.
［9］ PINEDO M. Scheduling: theory, algorithms, and systems ［M］. 2nd ed. New Jersey: Prentice Hall, 2002: 18-19.
［10］ 王冰,席裕庚,谷寒雨.一类单机动态调度问题的改进滚动时域方法 ［J］.控制与决策, 2005, 20 (3): 257-265.
WANG Bin, XI Yugeng, GU Hanyu. An improved rolling horizon procedure for singlemachine scheduling with release times ［J］. Control and Decision, 2005, 20 (3): 257-265.
［11］ MANIMARAN G, MURTHY C S R. An efficient dynamic scheduling algorithm for multiprocessor realtime systems ［J］. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(3): 312-319.
［12］ SELLADURA V, ARAVINDAN P, PONNAMBALAM S G, et al. Dynamic simulation of job shop scheduling for optimal performance ［J］. International Journal of Operations & Production Management, 1995, 15 (7): 106-120.
［13］ ABDULRAZAQ T S, POTTS C N. Dynamic programming statespace relaxation for singlemachine scheduling ［J］. Journal of the Operational Research Society, 1988, 39(2): 141-152.
［14］ GOVIL M K, FU M C. Queueing theory in manufacturing: a survey ［J］. Journal of Manufacturing Systems, 1999, 18 (3): 214-240.
［15］ NARAHARI Y, VISWANADHAM N. A petri net approach to the modeling and analysis of flexible manufacturing system ［J］. Annals of Operations Research, 1985, 3(8): 449-472.
［16］ 罗小川,刘兴刚,李丹程,等.分布式测量系统服务窗口动态调度方法研究 ［J］.自动化学报,2008,34(6): 690-696.
LUO Xiaochuan, LIU Xinggang, LI Dancheng, et al. Dynamic scheduling algorithm of service windows in a distributed measurement system ［J］. Acta Automatica Sinica, 2008, 34(6): 690-696.
［17］ 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.
［18］ TAILLARD E. Benchmarks for basic scheduling problems ［J］. European Journal of Operational Research, 1993, 64(2): 278-285.
［19］ BOZOKI G, RICHARD J P. A branchandbound algorithm for the continuousprocess jobshop scheduling problem ［J］. IIE Transactions, 1970, 2(3): 246-252.
［20］ DROZDOWSKI M. Scheduling multiprocessor tasksAn overview ［J］. European Journal of Operational Research, 1996, 94(2): 215-230.
［21］ ADAMS J, BALAS E, ZAWACK D. The shifting bottleneck procedure for job shop scheduling ［J］. Management Science, 1988, 34 (3): 391-401.
［22］ MOHANASUNDARAM K M, NATARAJAN K, VISWANATHKUMAR G, et al. Scheduling rules for dynamic shops that manufacture multilevel jobs ［J］. Computers & Industr
[1] 宣琦, 吴铁军. Open shop复杂调度网络模型及特征分析[J]. J4, 2011, 45(4): 589-595.