Optimizing insuring critical path problem under uncertainty based on GP-BPSO algorithm

Document Type : Article


College of Management and Economics, Tianjin University, Tianjin 300072, China


This study considers a novel class of bi-level fuzzy random programming problem about insuring critical path. In this study, each task duration is assumed as a fuzzy random variable and follows the known possibility and probability distributions. Because there doesn’t exist an effective way to solve the problem directly, we first reduce the chance constraint to two equivalent random subproblems under two kinds of different risk attitudes. Then, we may use sample average approximation (SAA) method for reformulating the equivalent random programming subproblems as their approximation problems. Since the approximation problems are also hard to be solved, we explore a hybrid genotype phenotype binary particle swarm optimization algorithm (GP-BPSO) for resolving two equivalent subproblems, where dynamic programming method (DPM) is used for finding the solution in the lower level programming. At last, a series of simulation examples are performed for demonstrating the validity of the hybrid GP-BPSO compared with the hybrid BPSO algorithm.


Main Subjects

1. Joseph, M., Cecil, P.R., and Edward, D.W., Project
Management with CPM, PERT, and Precedence Diagramming,
Van Nostrand Reinhold Pub. (1983).
2. Chen, Y.L., Rinks, D., and Tang, K. \Critical path
in an activity network with time constraints", Eur. J.
Oper. Res., 100(1), pp. 122-133 (1997).
3. Guerriero, F. and Talarico, L. \A solution approach
to nd the critical path in a time-constrained activity
network", Comput. Oper. Res., 37(9), pp. 1557-1569
4. Mohring, R.H. \Minimizing costs of resource requirements
in project networks subject to a xed completion
time", Oper. Res., 32(1), pp. 89-120 (1984).
5. Mitchell, G. and Klastorin, T. \An e ective methodology
for the stochastic project compression problem",
IIE Trans., 39(10), pp. 957-969 (2007).
6. Shen, S., Smith, J.C., and Ahmed, S. \Expectation
and chance-constrained models and algorithms for
insuring critical paths", Manage. Sci., 56(10), pp.
1794-1814 (2010).
7. Goh, J. and Hall, N.G. \Total cost control in project
management via satis cing", Manage. Sci., 59(6), pp.
1354-1372 (2013).
8. Li, Z., Liu, Y., and Zang, W. \Stochastic insuring
critical path problem with value-at-risk criterion",
Lecture Notes in Electrical Engineering, 3, pp. 3-10
9. Li, Z., Liu, Y., and Yang, G. \A new probability
model for insuring critical path problem with heuristic
algorithm", Neurocomputing, 148, pp. 129-135 (2015).
10. Li, H. and Womer, N.K. \Solving stochastic resourceconstrained
project scheduling problems by closed-loop
approximate dynamic programming", Eur. J. Oper.
Res., 246(1), pp. 20-33 (2015).
11. Zadeh, L.A. \Fuzzy sets", Information and Control,
8(3), pp. 338-353 (1965).
12. Chen, S.P. and Hsueh, Y.J. \A simple approach to
fuzzy critical path analysis in project networks", Appl.
Math. Model., 32(7), pp. 1289-1297 (2008).
13. Zammori, F.A., Braglia, M., and Frosolini, M. \A
fuzzy multi-criteria approach for critical path de nition",
International Journal of Project Management,
27(3), pp. 278-291 (2009).
14. Amiri, M. and Golozari, F. \Application of fuzzy
multi-attribute decision making in determining the
critical path by using time, cost, risk, and quality
criteria", The International Journal of Advanced Manufacturing
Technology, 54(1-4), pp. 393-401 (2011).
15. Zareei, A., Zaerpour, F., Bagherpour, M., Noora, A.A.,
and Vencheh, A.H. \A new approach for solving fuzzy
critical path problem using analysis of events", Expert
Syst. Appl., 38(1), pp. 87-93 (2011).
16. Li, Z. and Dai, X. \Optimization of insuring critical
path problem with uncertain activity duration times",
Journal of Uncertain Systems, 7(1), pp. 72-80 (2013).
17. Kaur, P. and Kumar, A. \Linear programming approach
for solving fuzzy critical path problems with
fuzzy parameters", Appl. Soft Comput., 21, pp. 309-
319 (2014).
18. Jayagowri, P. and Geetharamani, G. \Using metric
distance ranking method to nd intuitionistic fuzzy
critical path", J. Appl. Math., 2015(20), pp. 1-12
19. Pelikan, M., Stikova, H., and Vrana, I. \Detection
of resource overload in conditions of project
ambiguity", IEEE Trans. Fuzzy Syst. (2016). DOI:
20. Sireesha, V. and Shankar, N.R. \A node-weighted
rooted tree (NWRT) method to nd project characteristics
and critical path in a triangular fuzzy project
network", Comput. Appl. Math., pp. 1-15 (2017). DOI:
21. Liu, Y.K. and Liu, B. \Fuzzy random variables: A
scalar expected value operator", Fuzzy Optim. Decis.
Ma., 2(2), pp. 143-160 (2003).
22. Liu, Y.K., Liu, Z.Q., and Gao, J. \The modes of
convergence in the approximation of fuzzy random
optimization problems", Soft Comput., 13(2), pp. 117-
125 (2009).
23. Qin, R. and Liu, Y.K. \A new data envelopment analysis
model with fuzzy random inputs and outputs",
Journal of Applied Mathematics and Computing, 33(1-
2), pp. 327-356 (2010).
24. Ma, Y. and Xu, J. \A novel multiple decisionmaker
model for resource-constrained project scheduling
problems", Can. J. of Civil Eng., 41(6), pp. 500-
511 (2014).
25. Yang, K. and Liu, Y. \Developing equilibrium optimization
methods for hub location problems", Soft
Comput., 19(8), pp. 2337-2353 (2015).
26. Gao, Y. and Qin, Z. \A chance constrained programming
approach for uncertain p-hub center location
problem", Comput. Ind. Eng., 102, pp. 10-20 (2016).
27. Meiyi, W., Xiang, L., and Lean, Y. \Time-dependent
fuzzy random location-scheduling programming for
hazardous materials transportation", Transportation
Research. Part C: Emerging Technologies, 57, pp. 146-
165 (2015).
28. Kumar, R.S., Tiwari, M.K., and Goswami, A.
\Two-echelon fuzzy stochastic supply chain for the
manufacturer-buyer integrated production-inventory
system", J. Intell. Manuf., 27(4), pp. 875-888 (2016).
29. Chen, Y., Gao, J., Yang, G., and Liu, Y. \Solving
equilibrium standby redundancy optimization problem
by hybrid PSO algorithm", Soft Comput., 22(17), pp.
5631-5645 (2018). DOI 10.1007/s00500-017-2552-4
30. Liu, Y.K. and Liu, B. \Fuzzy random programming
with equilibrium chance constraints", Inform. Sciences,
170(2), pp. 363-395 (2005).
31. Phelps, C., Royset, J.O., and Gong, Q. \Optimal
control of uncertain systems using sample average
3722 Z. Li and B. Li/Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 3713{3722
approximations", SIAM J. Control Optim., 54(1), pp.
1-29 (2016).
32. Kennedy, J. and Eberhart, R.C. \A discrete binary
version of the particle swarm algorithm", In Systems,
Man, and Cybernetics, 1997. Computational
Cybernetics and Simulation, 1997 IEEE International
Conference, 5 pp. 4104-4108, IEEE (Oct. 1997).
33. Lee, S., Soak, S., Oh, S., Pedrycz, W., and Jeon,
M. \Modi ed binary particle swarm optimization",
Progress in Natural Science, 18(9), pp. 1161-1166
34. Wang, S. and Watada, J. \A hybrid modi ed PSO
approach to VaR-based facility location problems with
variable capacity in fuzzy random uncertainty", Inform.
Sciences, 192, pp. 3-18 (2012).
35. Beheshti, Z., Shamsuddin, S.M., and Hasan, S.
\Memetic binary particle swarm optimization for discrete
optimization problems", Inform. Sciences, 299,
pp. 58-84 (2015).
36. Li, P., Xu, D., Zhou, Z., Lee, W.J., and Zhao, B.
\Stochastic optimal operation of microgrid based on
chaotic binary particle swarm optimization", IEEE
Transactions on Smart Grid, 7(1), pp. 66-73 (2016).
37. Liu, J., Mei, Y., and Li, X. \An analysis of the
inertia weight parameter for binary particle swarm
optimization", IEEE Trans. Evolut. Comput., 20(5),
pp. 666-681 (2016).
38. Jiang, F., Xia, H., Tran, Q.A., Ha, Q.M., Tran, N.Q.,
and Hu, J. \A new binary hybrid particle swarm optimization
with wavelet mutation", Knowledge-Based
Syst., 130, pp. 90-101 (2017).
39. Liu, B. and Liu, Y.K. \Expected value of fuzzy variable
and fuzzy expected value models", IEEE Trans. Fuzzy
Syst., 10(4), pp. 445-450 (2002).
40. Liu, Y.K. and Gao, J. \The independence of fuzzy
variables with applications to fuzzy random optimization",
International Journal of Uncertainty, Fuzziness
and Knowledge-Based Systems, 15(supp02), pp. 1-20
41. Shapiro, A. and Homem-de-Mello, T. \A simulationbased
approach to two-stage stochastic programming
with recourse", Math. Program., 81(3), pp. 301-325
42. Luedtke, J. and Ahmed, S. \A sample approximation
approach for optimization with probabilistic
constraints", SIAM J. Optimiz., 19(2), pp. 674-699
43. Bellman, R. \Dynamic programming and Lagrange
multipliers", P. Natl. A. Sci., 42(10), pp. 767-769
44. Huang, Y., Qu, L., and Tang, C. \Optimal coverage
scheme based on QPSO in wireless sensor networks",
Journal of Networks, 7(9), pp. 1362-1368 (2012).