A multi-objective resource-constrained optimization of time-cost trade-off problems in scheduling project

Document Type: Research Paper

Authors

Faculty of Industrial Engineering, Imam Hossein (AS) University, Tehran, Iran

Abstract

This paper presents a multi-objective resource-constrained project scheduling problem with positive and negative cash flows. The net present value (NPV) maximization and making span minimization are this study objectives. And since this problem is considered as complex optimization in NP-Hard context, we present a mathematical model for the given problem and solve three evolutionary algorithms; NSGA-II, MOSA and MOPSO are applied to find the set of Pareto solutions for this multi-objective scheduling problem. In order to show performance of the algorithms, different metrics are applied and comparisons between the two algorithms are also considered. The computational results for a set of test problems taken from the project scheduling problem Bandar Abbas Gas condensate Refinery project and library are presented and discussed. Finally, the computational results illustrate the superior performance of the NSGA-II, MOSA and MOPSO algorithm with regard to the proposed metrics. In order to solve proposed method from NSGA-II algorithm, the results are compared with GAMS software in some problems. The proposed method is a Converge to the optimum and efficient solution algorithm.

Keywords

Main Subjects


Article Title [Persian]

مسئلة بهینه‌سازی تابع چند هدفه با ملاحظة محدودیت منابع با استفاده از موازنة زمان-هزینه در زمان‌بندی پروژه

Authors [Persian]

  • مصطفی زارعی
  • حسینعلی حسن پور
دانشکده مهندسی صنایع، دانشگاه امام حسین (ع) تهران
Abstract [Persian]

در این مقاله مسئلة زمان‌بندی پروژه با تابع چند هدفه با در نظر گرفتن محدودیت منابع با جریان‌های نقدی مثبت و منفی بررسی شده است. اهداف مقاله حداکثر کردن ارزش خالص فعلی و حداقل نمودن زمان اتمام پروژه است. از آنجا که این مسئله از جمله مسائل بهینه‌سازی پیچیده در خانوادة مسائلNP-hard  محسوب می‌شود، مدلی ریاضی برای مسئلة مورد نظر ارائه و برای حل مدل پیشنهادی از سه الگوریتم NSGA-II، MOSA وMOPSO  برای پیدا کردن مجموعه‌ای از راه‌حل‌های پارتو برای مسئلة زمان‌بندی چند هدفه استفاده شده است. برای نشان‌دادن عملکرد الگوریتم‌ها، شاخص‌های مقایسه‌ای مختلف برای مقایسة بین الگوریتم‌ها در نظر گرفته شده است. نتایج محاسباتی برای مجموعه‌ای از مسائل زمان‌بندی پروژة پالایشگاه میعانات گازی بندر عباس و کتابخانه‌ای ارائه و بررسی شد. در نهایت، نتایج محاسباتی عملکرد برتر NSGA-II نسبت به الگوریتم MOSA و MOPSO با توجه به معیارهای ارائه شده نشان داده شد. به منظور حل روش پیشنهادی، جواب‌های به‌دست آمده از الگوریتم پیشنهادی NSGA-II با جواب‌های دقیق از نرم‌افزار GAMS در بعضی مسائل مقایسه شد. نتایج نشان می‌دهد که روش ارائه‌شدة الگوریتم پیشنهادی کارا و همگرا به جواب بهینه است.

Keywords [Persian]

  • الگوریتم‌های NSGA-II
  • MOSA و MOPSO
  • الگوهای پرداخت هزینه
  • زمان‌بندی پروژه
  • شاخص‌های مقایسه‌ایالگوریتم‌های تکاملی
Aboutalebi, R.S.; Najafi, A.A. & Ghorashi, B. (2012). “Solving multi-mode resource-constrained project scheduling problem using two multi objective evolutionary algorithms”. African Journal of Business Management, 6, 4057-4065.
Afshar, A.; Ziaraty, A.K.; Kaveh, A. & Sharifi, F. (2009). “Non-dominated Archiving Multi colony Ant Algorithm in Time-Cost Trade-Off Optimization”. Journal of Construction Engineering and Management, 135, 668–674.
Azimi, F.; Aboutalebi, R. S. & Najafi, A. A. (2011). “Using Multi-Objective Particle Swarm Optimization for Bi-objective Multi-Mode Resource Constrained Project Scheduling Problem”. World Academy of Science, Engineering and Technology, 54, 285-289.
Aladini, K.; Afshar, A. & Kalhor, E. (2011). “Discount Cash Flow Time-Cost Trade off Problem Optimization; ACO Approach”. Asian Journal of Civil Engineering (Bulding and Housing), 12, 511-522.
Bashiri, M.; Kazemzadeh, R.; Atkinson, A.C. & Karimi, H. (2011). “Met-heuristic Based Multiple Response Process Optimization”. Journal of Industrial Engineering. University of Tehran, Special Issue, 13-23.
Chen, W.N.; Zhang, J. & Liu, H. (2010). A Monte-Carlo Ant Colony System for Scheduling Multi-mode Project with Uncertainties to Optimize Cash flows. proceeding of IEEE Congress on Evolutionary Computation (CEC), 1-8.
Dayanand, N. & Padman, R. (2001). “Project contracts and payment schedules: the client’s problem”. Management Science, 47, 1654-67.
D¨orner, K.F.; Gutjahr, W.J.; Hartl, R.F.; Strauss, C. & Stummer, C. (2008).
“Nature-inspired meta-heuristics for multi objective activity crashing”. Omega, 36, 1019–1037.
Dayanand, N. & Padman, R. (1998). Project contracts and payment schedules: The client's problem. Working Paper, The Heinz School, Carnegie Mellon University, Pittsburgh, Pennsylvania.
El-Rayes, K. & Kandil, A. (2005). “Time-Cost-Quality Trade-Off Analysis for Highway Construction”. Journal of Construction Engineering and Management, 131, 477-486.
Elloumi, S. & Fortemps, P. (2010). “A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem”. European Journal of Operational Research, 205, 31–41.
Feng, C.; Liu, L. & Burns, S.A. (1997). “Using Genetic Algorithms to Solve 

Construction Time-Cost Trade-Off Problems”. Journal of Computing in Civil Engineering, 11, 184-189.
Herroelen, W.S.; De Reyck, B. & Demeulemeester, E.L. (1997). “Project network models with discounted cash flows: A guided tour through recent developments”. European Journal of Operational Research, 100, 97-121.
Jongyul, K.; Changwook, K. & Inkeuk, H. (2012). “A practical approach to project scheduling: considering the potential quality loss cost in the time–cost tradeoff problem”. International Journal of Project Management, 30, 264–272.
Kwan, W.K.; Mitsuo, G. & Genji,Y. (2003). “Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling”. Applied Soft Computing, 2, 174–188.
Kashif Gill, M.; Kaheil, H.Y.; Khalil, A.; McKee, M. & Bastidas, L. (2006). “Multi objective particle swarm optimization for parameter estimation in hydrology”. Water Resources Research, 42(Iss.7).
Kim, J.Y.; Kang, C.W. & InKeuk, H. (2012). “A practical approach to project scheduling: considering the potential quality loss cost in the time–cost tradeoff problem”. International Journal of Project Management, 30, 264–272.
Khalilzadeh, M.; Kianfar, F. & Ranjbar, M. (2011). “A Scatter Search Algorithm for the RCPSP with Discounted Weighted Earliness-Tardiness Costs”. Life Science Journal, 8, 634-641.
Liu, L.; Burns, S.A. & Feng, C. (1995). “Construction Time-Cost Trade-Off Analysis Using LP/IP Hybrid Method”. Journal of Construction Engineering and Management, 121, 446-454.
Luong, D.L. & Ario, O. (2008). “Fuzzy critical chain method for project scheduling under resource constraints and uncertainty”. International Journal of Project Managemen, 26, 688–698.
Moselhi, O. (1993). “Schedule compression using the direct stiffness method”. Canadian Journal of Civil. Engineering, 20(1), 65-72.
Siemens, N. (1971). “A Simple CPM Time-Cost Tradeoff Algorithm”. Management Science, 17, 354-363.
Moussourakis, J. & Haksever, C. (2004). “Flexible Model for Time/Cost Tradeoff Problem”. Journal of Construction Engineering and Management, 130, 307-314.
Marek, M.; Grzegorz, W. O. & Wezglarz, J. (2005). “Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models”. European Journal of Operational Research, 164, 639–668.

Möhring, R.H. & Stork, F. (2000). “Linear pre selective policies for stochastic project scheduling”. Math Methods Operation Research, 52, 501–15.
Najafi, A.A. & Niaki, S.T.A. (2006). “A genetic algorithm for resource investment problem with discounted cash flows”. Applied Mathematics and Computation, 183, 1057–1070.
Pan, H.; Robert, J. & Wilish, C.H. (2008). “Resource Constrained Project Scheduling with Fuzziness”. Industrial engineering and management systems conference.
Ritwik, A. & Paul, G. (2013). “A Heuristic Algorithm for Resource Constrained Project Scheduling Problem with Discounted Cash Flows”. International Journal of Innovative Technology and Exploring Engineering (IJITEE), 3, 99-102.
Rifat, S. & Önder Halis, B. (2012). “A hybrid genetic algorithm for the discrete time–cost trade-off problem”. Expert Systems with Applications, 39, 11428–11434.
Shu-Shun, L. & Chang-Jung, W. (2008). “Resource-constrained construction project scheduling model for profit maximization considering cash flow”. Automation in Construction, 17, 966–974.
Smith-Daniels, D.E.; Padman, R. & Smith- Daniels, V.L. (1996). “Heuristic scheduling of capital constrained projects”. Journal of Operations Management, 14, 241–254.
Seifi, M. & Tavakkoli-Moghaddam, R. (2008). “A new bi-objective model for a multi-mode resource-constrained project scheduling problem with discounted cash flows and four payment models”. IJE Transactions A: Basics, 21, 347-360.
Salimi, R.; Bazrkar, N. & Nemati, M. (2013). “Task Scheduling for Computational Grids Using NSGA- II with Fuzzy Variance Based Crossover”. Advances in Computing, 3, 22-29.
Ulusoy, G. & Cebelli, S. (2000). “An equitable approach to the payment scheduling problem in project management”. European Journal of Operational Research, 127, 262–278.
Varadharajan, T.K. & Rajendran, C. (2005). “A multi-objective simulated annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs”. European Journal of Operational Research, 167, 772–795.
Xu, S. (2011). “Applying Ant Colony System to Solve Construction Time-Cost Trade off Problem”. Advances Materials Research, 179, 1390-1395.
Xiong, Y. & Kuang, Y. (2008). “Applying an Ant Colony Optimization 

Algorithm-Based Multi-objective Approach for Time-Cost Trade-Off”. Journal of Construction Engineering and Management, 134, 153-156.
Zhengwen, H. & Yu, X. (2008). “Multi-mode project payment scheduling problems with bonus–penalty structure”. European Journal of Operational Research, 189, 1191–1207.
Zheng, D. X. M.; Ng, S.T. & Kumaraswamy, M. M. (2005). “Applying Pareto Ranking and Niche Formation to Genetic Algorithm-Based Multi objective Time--Cost Optimization”. Journal of Construction Engineering and Management, 131, 81-91.
Zitzler, E.; Deb, K. & Thiele, L. (2000). “Comparison of multi objective evolutionary algorithms: Empirical results”. Evolutionary Computation Journal, 8, 125–148.