项目调度中的测试问题集选取研究

J4 ›› 2014, Vol. 36 ›› Issue (07): 1307-1315.

项目调度中的测试问题集选取研究

田文迪1，许静1，别黎2，崔南方3

(1.武汉纺织大学管理学院，湖北武汉 430073；2.中南民族大学管理学院，湖北武汉 430074；3.华中科技大学管理学院，湖北武汉 430074）

收稿日期:2012-10-29 修回日期:2013-02-28 出版日期:2014-07-25 发布日期:2014-07-25
基金资助:
国家自然科学基金资助项目（71201119,71271097）;湖北物流发展中心资助项目（2014A09）

Study of the test instances sets selection
in project scheduling problems

TIAN Wendi1,XU Jing1,BIE Li2,CUI Nanfang3

(1.School of Management,Wuhan Textile University,Wuhan 430073;
2.School of Management,SouthCentral University for Nationalities,Wuhan 430074;
3.School of Management,Huazhong University of Science and Technology,Wuhan 430074,China)

Received:2012-10-29 Revised:2013-02-28 Online:2014-07-25 Published:2014-07-25

摘要/Abstract

摘要：

为了更好测试和比较项目调度问题求解算法的性能，通常需要利用测试问题集对相关算法进行测试和比较。对现有测试问题集的研究进行综述，并重点介绍国际上常用的两套标准问题集（Patterson问题集和PSPLIB标准问题库）和两款用于生成问题集的软件（单项目调度问题集生成器RanGen和多项目调度问题集生成器RCMPSP），最后，提出项目调度问题中选取问题集的一般流程以及构建问题集的一般方法，并通过实例说明该问题集选取方法的有效性及应用前景。

关键词: 项目调度, 测试问题集, 问题集生成器

Abstract:

In order to test and compare the performance of algorithms in the project scheduling problems, test instances sets are required. Some literatures are reviewed and surveyed on the instances sets. As internationally and commonly used, two basic instances sets (Patterson sets and PSPLIB) and two instances sets generators (the single project generator RanGen and the multiproject generator RCMPSP) are introduced. Finally, the selection flow of test instances sets in project scheduling problems and the general method of constructing test instances sets are proposed. Two cases are used to illustrate the effectiveness and application prospects of these methods.

Key words: project scheduling;test instances set;instances set generator

田文迪1，许静1，别黎2，崔南方3. 项目调度中的测试问题集选取研究[J]. J4, 2014, 36(07): 1307-1315.

TIAN Wendi1,XU Jing1,BIE Li2,CUI Nanfang3. Study of the test instances sets selection
in project scheduling problems [J]. J4, 2014, 36(07): 1307-1315.

参考文献

［1］Tavares LV. A review of the contribution of operational research to project management ［J］. European Journal of Operational Research, 2002,136(1):118.
［2］Zhang Jingwen, Xu Yu, He Zhengwen, et al. A review on the time/cost tradeoffs problem in project scheduling ［J］. Journal of Industrial Engineering and Engineering Management, 2007, 21(1):9297. (in Chinese)
［3］De Reyck B. Scheduling project with generalized precedence relations:Exact and heuristic approach ［D］. Leuven:Katholieke Universiteit Leuven, 1998.
［4］Brucker P, Drexl A, Mhring R, et al. Resourceconstrained project scheduling:Notation, classification, models and methods ［J］. European Journal of Operational Research, 1999,112:341.
［5］Herroelen W,De Reyck B,Demeulemeester E.Resource constrained scheduling:A survey of recent developments ［J］. Computers and Operations Research, 1998, 25:279302.
［6］Demeulemeester E, Herroelen W. Project schedulingA research handbook ［M］.Boston:Kluwer Academic Publishers, 2002.
［7］Patterson J. A comparison of exact procedures for solving the multiple constrained resource project scheduling problem ［J］. Management Science, 1984, 30:854867.
［8］Demeulemeester E, Herroelen W. A branchandbound procedure for the multiple resourceconstrained project scheduling problem［J］. Management Science, 1992, 38(12):18031818.
［9］Kolisch R, Sprecher A, Drexl A. Characterization and generation of a general class of resourceconstrained project scheduling problems［J］. Management Science, 1995, 41(10):16931703.
［10］Demeulemeester E, Dodin B, Herroelen W. A random activity network generator ［J］. Operations Research, 1993, 41(5):972980.
［11］Agrawal M K, Elmaghraby S E, Herroelen W S. DAGEN:A generator of test sets for project activity nets ［J］. European Journal of Operational Research, 1996, 90(2):376382.
［12］Kolisch R, Sprecher A, Drexl A. Characterization and generation of a general class of resourceconstrained project scheduling problems［R］. Kiel, Germany, 1992.
［13］Kolisch R,Sprecher A.PSPLIBA project scheduling library ［J］. European Journal of Operational Research, 1996, 96:205216.
［14］Schwindt C. A new problem generator for different resource constrained project scheduling problems with minimal and maximal time lags ［R］. WIORReport449, Karlsruhe, Germany:Institut für Wirtschaftstheorie und Operations Research, Universitt Karlsruhe, 1995.
［15］Schwindt C.Generation of resourceconstrained project scheduling problems with minimal and maximal time lags ［R］. WIORReport489,VKarlsruhe, Germany:Institut für Wirtschaftstheorie und Operations Research, Universitt Karlsruhe, 1996.
［16］Schwindt C.Generation of resourceconstrained project scheduling problems subject to temporal constraints ［R］. WIOR Report543, Karlsruhe, Germany:Institut für Wirtschaftstheorie und Operations Research, Universitt Karlsruhe, 1998.
［17］Tavares L V.Advanced models for project management ［M］.Boston:Kluwer Academic Publisher,1998.
［18］Vanhoucke M, Demeulemeester E, Herroelen W. RanGen:A random network generator for activityonthenode networks ［J］. Journal of Scheduling, 2003, 6(1):1334.
［19］Vanhoucke M,Coelho J,Tavares L,et al.An evaluation of the adequacy of network generators with systematically sampled networks ［J］. European Journal of Operational Research, 2008, 187(2):521524.
［20］Gutiérrez M, Durán A, Alegre D, et al. Hiergen:a computer tool for the generation of activityonthenode hierarchical project networks ［C］∥Proc of the Computational Science and Its Applications—ICCSA, Part III, Assisi, 2004:857866.
［21］Browning T R,Yassine A A.A random generator of resourceconstrained multiproject network problems ［J］. Journal of Scheduling, 2010, 13(2):143161.
［22］Weglarz J. Project scheduling:Recent models, algorithms and applications［M］. Boston:Kluwer Academic Publisher, 1999.
［23］Deblaere F,Demeulemeester E,Herroelen W.Reactive scheduling in the multimode RCPSP［J］. Computers and Operations Research, 2011, 38(1):6374.
［24］Tian W,Demeulemeester E.On the interaction between roadrunner or railway scheduling and priority lists or resource flow networks ［J］. Flexible Services and Manufacturing Journal, 2012, DOI:10.1007/s1069601291454.
附中文参考文献：
［2］张静文, 徐渝, 何正文，等, 项目调度中的时间/费用权衡问题研究综述［J］. 管理工程学报，2007，21(1):9297.