›› 2012, Vol. 27 ›› Issue (5): 950-965.doi: 10.1007/s11390-012-1276-2

• Special Issue on Evolutionary Computation • Previous Articles     Next Articles

Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows: A Monte Carlo Ant Colony System Approach

Wei-Neng Chen (陈伟能), Member IEEE, and Jun Zhang (张军), Senior Member, IEEE   

  1. Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China
  • Received:2011-09-03 Revised:2012-07-13 Online:2012-09-05 Published:2012-09-05
  • Supported by:

    This work was supported in part by the National Science Fund for Distinguished Young Scholars of China under Grant No. 61125205, the National Natural Science Foundation of China (NSFC) under Grant No. 61070004, NSFC-Guangdong Joint Fund under Key Project No. U0835002.

Project scheduling under uncertainty is a challenging field of research that has attracted increasing attention. While most existing studies only consider the single-mode project scheduling problem under uncertainty, this paper aims to deal with a more realistic model called the stochastic multi-mode resource constrained project scheduling problem with discounted cash flows (S-MRCPSPDCF). In the model, activity durations and costs are given by random variables. The objective is to find an optimal baseline schedule so that the expected net present value (NPV) of cash flows is maximized. To solve the problem, an ant colony system (ACS) based approach is designed. The algorithm dispatches a group of ants to build baseline schedules iteratively using pheromones and an expected discounted cost (EDC) heuristic. Since it is impossible to evaluate the expected NPV directly due to the presence of random variables, the algorithm adopts the Monte Carlo (MC) simulation technique. As the ACS algorithm only uses the best-so-far solution to update pheromone values, it is found that a rough simulation with a small number of random scenarios is enough for evaluation. Thus the computational cost is reduced. Experimental results on 33 instances demonstrate the effectiveness of the proposed model and the ACS approach.

[1] Brucker P, Drexl A, Möhring R, Neumann K, Pesch E.Resource-constrained project scheduling: Notation, classifica-tion, models and methods. European Journal of OperationalResearch, 1999, 112(1): 3-41.
[2] Blazewicz J, Lenstra J K, Rinnooy Kan A H G. Schedulingsubject to resource constraints: Classification and complex.Discrete Applied Mathematics, 1983, 5(1): 11-24.
[3] Ödamar L. A genetic algorithm approach to a general cate-gory project scheduling problem. IEEE Transactions on Sys-tems, Man, and Cybernetics —— Part C: Application and Re-views, 1999, 29(1): 44-59.
[4] Tseng L Y, Chen S C. Two-phase genetic local search algo-rithm for the multimode resource-constrained project schedul-ing problem. IEEE Transactions on Evolutionary Computa-tion, 2009, 13(4): 848-857.
[5] Kolisch R. Project Scheduling under Resource Constraints:E±cient Heuristics for Several Problem Classes. Physica-Verlag, 1995.
[6] Russell A H. Cash flows in networks. Management Science,1970, 16(5): 357-373.
[7] Herroelen W, De Reyck B, Demeulemeester E. Project net-work models with discounted cash flows: A guided tourthrough recent developments. European Journal of Opera-tional Research, 1997, 100(1): 97-121.
[8] Ulusoy G. Four payment models for the multi-mode resourceconstrained project scheduling problem with discounted cashflows. Annals of Operations Research, 2001, 102(1-4): 237-261.
[9] Mika M, Waligóra G, Weglarz J. Simulated annealing andtabu search for multi-mode resource-constrained projectscheduling with positive discounted cash flows and differentpayment models. European Journal of Operational Research,2005, 164(3): 639-668.
[10] Chen W N, Zhang J, Chung H S H, Huang R Z, Liu O. Op-timizing discounted cash flows in project scheduling —— Anant colony optimization approach. IEEE Transactions onSystems, Man, and Cybernetics —— Part C: Applications andReviews, 2010, 40(1): 64-77.
[11] Herroelen W, Leus R. Project scheduling under uncertainty:Survey and research potentials. European Journal of Opera-tional Research, 2005, 165(2): 289-306.
[12] Li Z, Ierapetritou M. Process scheduling under uncertainty:Review and challenges. Computers and Chemical Engineer-ing, 2008, 32(4-5): 715-727.
[13] Sahinidis N V. Optimization under uncertainty: State-of-the-art and opportunities. Computers and Chemical Engineering,2004, 28(6-7): 971-983.
[14] Park H K. Cash flow forecasting in construction project.KSCE Journal of Civil Engineering, 2004, 18(3): 265-271.
[15] Yang I T, Chang C Y. Stochastic resource-constrainedscheduling for repetitive construction projects with uncertainsupply of resources and funding. International Journal ofProject Management, 2005, 23(7): 546-553.
[16] Wu X, Zhou X. Stochastic scheduling to minimize expectedmaximum lateness. European Journal of Operational Re-search, 2008, 190(1): 103-115.
[17] Ke H, Liu B. Project scheduling problem with stochastic ac-tivity duration times. Applied Mathematics and Computa-tion, 2005, 168(1): 342-353.
[18] Guo Z X, Wong W X, Leung S Y S, Fan J T, Chan S F.Genetic optimization of order scheduling with multiple un-certainties. Expert Systems with Applications, 2008, 35(4):1788-1801.
[19] Long L D, Ohsato A. Fuzzy critical chain method for projectscheduling under resource constraints and uncertainty. Inter-national Journal of Project Management, 2008, 26(6): 688-698.
[20] Daniels R L, Carrillo J E. fi-robust scheduling for single-machine systems with uncertain processing times. IIE Trans-actions, 1997, 29(11): 977-985.
[21] Creemers S, Leus R, De Reyck B, Lambrecht M. Projectscheduling for maximum NPV with variable activity dura-tions and uncertain activity outcomes. In Proc. IEEE In-ternational Conference on Industrial Engineering and Engi-neering Management, Dec. 2008, pp.183-187.
[22] Creemers S, Leus R, Lambrechts M. Scheduling MarkovianPERT networks with maximum-NPV objective. TechnicalReport KBI 0811, Department of Decision Sciences and In-formation Management, KU Leuven, Belgium, 2008.
[23] Sobel M J, Szmetekovsky J G, Tilson V. Scheduling projectswith stochastic activity duration to maximize expected netpresent value. European Journal of Operational Research,2009, 198(3): 697-705.
[24] Wiesemann W, Kuhn D, Rustem B. Maximizing the netpresent value of a project under uncertainty. European Jour-nal of Operational Research, 2010, 202(2): 356-367.
[25] Szmerekovsky J G. Single machine scheduling under mar-ket uncertainty. European Journal of Operational Research,2007, 177(1): 163-175.
[26] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimiza-tion by a colony of cooperating agents. IEEE Transactionson Systems, Man, and Cybernetics —— Part B: Cybernetics,1996, 26(1): 29-41.
[27] Dorigo M, Gambardella L M. Ant colony system: A cooper-ative learning approach to TSP. IEEE Transactions on Evo-lutionary Computation, 1997, 1(1): 53-66.
[28] Merkle D, Middendorf M, Schmeck H. Ant colony optimiza-tion for resource-constrained project scheduling. IEEE Trans-actions on Evolutionary Computation, 2002, 6(4): 333-346.
[29] Chen W N, Zhang J. An ant colony optimization approach toa grid workflow scheduling problem with various QoS require-ments. IEEE Transactions on Systems, Man, and Cybernet-ics —— Part C:Application and Reviews, 2009, 39(1): 29-43.
[30] Hu X M, Zhang J, Chung H S H, Liu O, Xiao J. An intelligenttesting system embedded with an ant colony optimizationbased test composition method. IEEE Transactions on Sys-tems, Man and Cybernetics ——Part C:Application and Re-views, 2009, 39(6): 659-669.
[31] Gutjahr W J. S-ACO: An ant based approach to combinato-rial optimization under uncertainty. In Proc. the 4th ANTS,Sept. 2004, pp.238-249.
[32] Gutjahr W J. A converging ACO algorithm for stochasticcombinatorial optimization. In Proc. the 2nd Symposium onStochastic Algorithms, Foundations and Applications, Sept.2003, pp.10-25.
[33] Balaprakash P. Ant colony optimization under uncertainty.Technical Report No. TR/IRIDIA/2005-028, IRIDIA, Uni-versite Libre de Bruxelles, 2005.
[34] Brucker P, Knust S, Schoo A, Thiele O. A branch andbound algorithm for the resource-constrained project schedul-ing problem. European Journal of Operational Research,1998, 107(2): 272-288.
[35] Lee J K, Kim Y D. Search heuristics for resource constrainedproject scheduling. Journal of the Operational Research So-ciety, 1996, 47(5): 678-689.
[36] Chiang C W, Huang Y Q, Wang W Y. Ant colony opti-mization with parameter adaptation for multi-mode resource-constrained project scheduling. Journal of Intelligent &Fuzzy Systems: Applications in Engineering and Technology,2008, 19(4-5): 345-358.
[37] Józefowska J, Mika M, Rózycki R, Waligóra G, WeglarzJ. Simulated annealing for multi-mode resource-constrainedproject scheduling. Annals of Operations Research, 2001,102(1-4): 137-155.
[38] Bianchi L, Dorigo M, Gambardella L M, Gutjahr W J. Meta-heuristics in stochastic combinatorial optimization: A survey.Technical Report IDSIA-08-06, IDSIA, Dalle Molle Institutefor Artificial Intelligence, 2006.
[39] Bianchi L, Dorigo M, Gambardella L M, Gutjahr W J. A sur-vey on metaheuristics for combinatorial optimization. Nat.Comput., 2009, 8(2): 239-287.
[40] Jin Y, Branke J. Evolutionary optimization in uncertain en-vironments —— A survey. IEEE Transactions on EvolutionaryComputation, 2005, 9(3): 303-317.
[41] Vieira G E, Herrmann J W, Lin E. Rescheduling manufactur-ing systems: A framework of strategies, policies and methods.Journal of Scheduling, 2003, 6(1): 39-62.
[42] Shtub A, Bard J F, Globerson S. Project Scheduling: Pro-cesses, Methodologies and Economics (2nd edition). PrenticeHall, 2002.
[43] Kolisch R, Hartmann S. Heuristic algorithms for solving theresource-constrained project scheduling problem: Classifica-tion and computational analysis. In Handbook on Recent Ad-vances in Project Scheduling. Weglarz J (ed), Dordrecht, TheNetherlands: Kluwer Academic Publishers, 1999, pp.197-212.
[44] Demeulemeester E, Dodin B, Herroelen W. A random ac-tivity network generator. Operations Research, 1993, 41(5):972-980.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Xue Xing; Sun Zhongxiu; Zhou Jianqiang; Xu Xihao;. A Message-Based Distributed Kernel for a Full Heterogeneous Environment[J]. , 1990, 5(1): 47 -56 .
[7] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[8] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[9] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[10] Liao Xianzhi; Jin Lan;. A Mechanism Supporting the Client/Server Relationship in the Operating System of Distributed System “THUDS”[J]. , 1991, 6(3): 256 -262 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved