×

Evolutionary multi-objective resource allocation and scheduling in the Chinese navigation satellite system project. (English) Zbl 1346.90866

Summary: The development of appropriate project management techniques for Research and Development (R&D) projects has received significant academic and practical attention over the past few decades. Project managers typically face the problem of allocating resources and scheduling activities, for which the underlying combinatorial problem is NP-hard. The inherent uncertainty in many R&D environments increases the complexity of the problem. This paper addresses the problem of resource allocation and activity scheduling with a focus on R&D projects. The work is different from the existing literature in at least three aspects: (1) the problem formulation is based on a real-world Chinese aerospace project, (2) each individual resource unit can have a different resource efficiency, and (3) the uncertainty of the duration of an activity is time-dependent (efficiency-dependent) in nature. The problem is formulated as a multi-objective optimization model with simultaneous consideration of makespan and balance of resource efficiency. A cooperative coevolutionary multi-objective algorithm (CCMOA) is designed to produce high-quality solutions. Two chromosome representations and three resource selection policies are tested for the algorithm. The proposed CCMOA is found to be competitive when compared to MOEA/D and NSGA-II, which are two popular algorithms for multi-objective optimization.

MSC:

90C90 Applications of mathematical programming
90B90 Case-oriented studies in operations research
90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming

Software:

PSPLIB; MOEA/D
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbass, H. A.; Bender, A.; Dam, H. H.; Baker, S.; Whitacre, J. M.; Sarker, R. A., Computational scenario-based capability planning, Proceedings of genetic and evolutionary computation conference (2008)
[2] Abdelsalam, H. M.E.; Bao, H. P., A simulation-based optimization framework for product development cycle time reduction, IEEE Transactions on Engineering Management, 53, 69-85 (2006)
[3] Artigues, C.; Leus, R.; Talla Nobibon, F., Robust optimization for resource-constrained project scheduling with uncertain activity durations, Flexible Services and Manufacturing Journal, 25, 175-205 (2013)
[4] Ashtiani, B.; Leus, R.; Aryanezhad, M. B., New competitive results for the stochastic resource-constrained project scheduling problem: exploring the benefits of pre-processing, Journal of Scheduling, 14, 157-171 (2011) · Zbl 1213.90128
[5] Ballestín, F.; Blanco, R., Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems, Computers & Operations Research, 38, 51-62 (2011) · Zbl 1231.90173
[6] Ballestín, F.; Leus, R., Resource-constrained project scheduling for timely project completion with stochastic activity durations, Production and Operations Management, 18, 459-474 (2009)
[7] Bauer, B. J., A success paradigm for project managers in the aerospace industry (2005), Capella University., (Ph.D. thesis):
[8] Brucker, P.; Drexl, A.; Möhring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research, 112, 3-41 (1999) · Zbl 0937.90030
[9] Bui, L. T.; Michalewicz, Z.; Parkinson, E.; Abello, M. B., Adaptation in dynamic environments: A case study in mission planning, IEEE Transactions on Evolutionary Computation, 16, 190-209 (2012)
[10] Chang, P. C.; Chen, S. H.; Zhang, Q.; Lin, J. L., MOEA/D for flowshop scheduling problems, IEEE congress on evolutionary computation, 1433-1438 (2008)
[11] Chen, A. N.K.; Edgington, T., Assessing value in organizational knowledge creation: Considerations for knowledge workers, MIS Quarterly, 29, 279-309 (2005)
[12] Chen, J.; Askin, R. G., Project selection, scheduling and resource allocation with time dependent returns, European Journal of Operational Research, 193, 23-34 (2009) · Zbl 1152.90483
[13] Cho, S. H.; Eppinger, S. D., A simulation-based process model for managing complex design projects, IEEE Transactions on Engineering Management, 52, 316-328 (2005)
[14] Chopra, S.; Meindl, P., Supply Chain Management: Strategy, Planning, and Operation (2007), Pearson education, Pearson Prentice Hall
[15] Coolen, K.; Wei, W.; Talla Nobibon, F.; Leus, R., Scheduling modular projects on a bottleneck resource, Journal of Scheduling, 17, 67-85 (2014) · Zbl 1297.90038
[16] Creemers, S.; De Reyck, B.; Leus, R., Project planning with alternative technologies in uncertain environments, European Journal of Operational Research, 242, 465-476 (2015) · Zbl 1341.90066
[17] De Reyck, B.; Leus, R., R&D project scheduling when activities may fail, IIE Transactions, 40, 367-384 (2008)
[18] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-ii, IEEE Transactions on Evolutionary Computation, 6, 182-197 (2002)
[19] Debels, D.; Vanhoucke, M., A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem, Operations Research, 55, 457-469 (2009) · Zbl 1167.90664
[20] Drezet, L. E.; Billaut, J. C., A project scheduling problem with labour constraints and time-dependent activities requirements, International Journal of Production Economics, 112, 217-225 (2008)
[21] Elmaghraby, S., On criticality and sensitivity in activity networks, European Journal of Operational Research, 127, 220-238 (2000) · Zbl 0990.90119
[22] Eppinger, S.; Nukala, M.; Whitney, D., Generalized models of design iteration using signal flow graphs, Research in Engineering Design, 9, 112-123 (1997)
[23] Golenko-Ginzburg, D.; Gonik, A., A heuristic for network project scheduling with random activity durations depending on the resource allocation, International Journal of Production Economics, 55, 149-162 (1998)
[24] Gutjahr, W. J., Bi-objective multi-mode project scheduling under risk aversion, European Journal of Operational Research, 246, 421-434 (2015) · Zbl 1346.90404
[25] Gutjahr, W. J.; Katzensteiner, S.; Reiter, P.; Stummer, C.; Denk, M., Multi-objective decision analysis for competence-oriented project portfolio selection, European Journal of Operational Research, 205, 670-679 (2010) · Zbl 1188.90127
[26] Hagstrom, J., Computational complexity of PERT problems, Networks, 18, 139-147 (1988)
[27] Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics, 45, 733-750 (1998) · Zbl 0936.90024
[28] Hartmann, S.; Briskorn, D., A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207, 1-14 (2010) · Zbl 1205.90123
[29] Herroelen, W.; De Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: A survey of recent developments, Computers & Operations Research, 25, 279-302 (1998) · Zbl 1040.90525
[30] Herroelen, W.; Leus, R., Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research, 165, 289-306 (2005) · Zbl 1066.90050
[31] Huang, W.; Ding, L., Project-scheduling problem with random time-dependent activity duration times, IEEE Transactions on Engineering Management, 58, 377-387 (2011)
[32] Kacem, I.; Hammadi, S.; Borne, P., Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews, 32, 1-13 (2002)
[33] Kolisch, R.; Padman, R., An integrated survey of deterministic project scheduling, Omega, 49, 249-272 (2001)
[34] Kolisch, R.; Sprecher, A., PSPLIB - A project scheduling problem library, European Journal of Operational Research, 96, 205-216 (1996) · Zbl 0947.90587
[35] Lamas, P.; Demeulemeester, E., A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations, Journal of Scheduling, 1-20 (2014)
[36] Lei, D., Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling, Applied Soft Computing, 12, 2237-2245 (2012)
[37] Malcolm, D.; Roseboom, J.; Clark, C.; Fazar, W., Application of a technique for research and development program evaluation, Operations Research, 7, 646-669 (1959) · Zbl 1255.90070
[38] Mei, Y.; Li, X.; Yao, X., Cooperative co-evolution with route distance grouping for large-scale capacitated arc routing problems, IEEE Transactions on Evolutionary Computation, 18, 435-449 (2014)
[39] Möhring, R., Minimizing costs of resource requirement in project networks subject to a fixed completion, Operations Research, 31, 89-119 (1984) · Zbl 0531.90049
[40] Möhring, R., Scheduling under uncertainty: Optimizing against a randomizing adversary, (Jansen, K.; Khuller, S. (2000), Springer-Verlag), 15-26 · Zbl 0976.90038
[41] Möhring, R., Scheduling under uncertainty: Bounding the makespan distribution, Lecture Notes in Computer Science, 2122, 79-97 (2001) · Zbl 1015.90046
[42] Mori, M.; Tseng, C., A genetic algorithm for multi-mode resource constrained project scheduling problem, European Journal of Operational Research, 100, 134-141 (1997) · Zbl 0947.90589
[43] Murata, T.; Ishibuchi, H.; Tanaka, H., Genetic algorithms for flowshop scheduling problems, Computers and Industrial Engineering, 30, 1061-1071 (1996)
[44] Murata, T.; Ishibuchi, H.; Tanaka, H., Multi-objective genetic algorithm and its applications to flowshop scheduling, Computers and Industrial Engineering, 30, 957-968 (1996)
[45] Nguyen, S.; Zhang, M.; Johnston, M.; Tan, K. C., Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming, IEEE Transactions on Evolutionary Computation, 18, 193-208 (2014)
[46] Ngwenyama, O.; Guergachi, A.; McLaren, T., Using the learning curve to maximize it productivity: A decision analysis model for timing software upgrades, International Journal of Production Economics, 105, 524-535 (2007)
[47] China Satellite Navigation Office, Report on the development of beidou navigation satellite system (version 2.0), Technical Report (2012), China Satellite Navigation Office.
[48] Potter, M. A.; Jong, K. A.D., Cooperative coevolution: An architecture for evolving coadapted subcomponents, Evolutionary Computation, 8, 1-29 (2000)
[49] Radermacher, F., Cost-dependent essential systems of ES-strategies for stochastic scheduling problems, Methods of Operations Research, 42, 17-31 (1981) · Zbl 0459.90035
[50] Rand, G. K., Critical chain: The theory of constraints applied to project management, International Journal of Project Management, 18, 173-177 (2000)
[51] Ranjbar, M.; De Reyck, B.; Kianfar, F., A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling, European Journal of Operational Research, 193, 35-48 (2009) · Zbl 1152.90464
[52] Ren, J.; Harman, M.; Penta, M. D., Cooperative co-evolutionary optimization of software project staff assignments and job scheduling, Lecture Notes in Computer Science, 6956, 127-141 (2011)
[53] Shadrokh, S.; Kianfar, F., A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty, European Journal of Operational Research, 181, 86-101 (2007) · Zbl 1121.90062
[54] Stork, F., Stochastic resource-constrained project scheduling (2001), Technische Universität Berlin., (Ph.D. thesis).
[55] Talbot, F. B., Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case, Management Science, 28, 1197-1210 (1982) · Zbl 0493.90042
[56] Tan, K. C.; Yang, Y. J.; Goh, C. K., A distributed cooperative coevolutionary algorithm for multiobjective optimization, IEEE Transactions on Evolutionary Computation, 10, 527-549 (2006)
[57] Tsai, Y. W.; Gemmil, D. D., Using tabu search to schedule activities of stochastic resource-constrained projects, European Journal of Operational Research, 111, 129-141 (1998) · Zbl 0948.90072
[58] Van de Vonder, S.; Demeulemeester, E.; Herroelen, W., A classification of predictive-reactive project scheduling procedures, Journal of Scheduling, 10, 195-207 (2007) · Zbl 1168.90474
[59] Van de Vonder, S.; Demeulemeester, E.; Herroelen, W., Proactive heuristic procedures for robust project scheduling: An experimental analysis, European Journal of Operational Research, 189, 723-733 (2008) · Zbl 1146.90430
[60] Wang, J. B.; Ng, C. T.; Cheng, T. C.E.; Liu, L. L., Single-machine scheduling with a time-dependent learning effect, International Journal of Production Economics, 111, 802-811 (2008)
[61] Wang, J. B.; Wang, J. J., Research on scheduling with job-dependent learning effect and convex resource-dependent processing times, International Journal of Production Research, 53, 5826-5836 (2015)
[62] Xiong, J.; Liu, J.; Chen, Y.; Abbass, H. A., A knowledge-based evolutionary multi-objective approach for stochastic extended resource investment project scheduling problems, IEEE Transactions on Evolutionary Computation, 18, 742-763 (2014)
[63] Xiong, J.; Xing, L.; Chen, Y., Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns, International Journal of Production Economics, 141, 112-126 (2013)
[64] Yin, Y.; Liu, M.; Hao, J.; Zhou, M., Single-machine scheduling with job-position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 42, 192-200 (2012)
[65] Zhang, Q.; Li, H., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11, 712-731 (2007)
[66] Zhao, W.; Alam, S.; Abbass, H. A., MOCCA-II: A multi-objective co-operative co-evolutionary algorithm, Applied Soft Computing, 23, 407-416 (2014)
[67] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 257-271 (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.