A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems

  • Published: 01 January 2017
  • 90C59

  • Inspired by the representation designed for floorplanning problems, in this paper, we proposed a new representation, namely the moving block sequence (MBS), for resource investment project scheduling problems (RIPSPs). Since each activity of a project in RIPSPs has fixed duration and resource demand, we consider an activity as a rectangle block whose width is equal to the duration of the activity and height the resource needed by the activity. Four move modes are designed for activities, by using which the activity can move to the appropriate position. Therefore, the new representation of the project of RIPSPs consists of two parts: an activity list and a move mode list. By initializing the move modes randomly for each activity and moving it appropriately, the activity list can be decoded into valid solutions of RIPSPs. Since the decoding method of MBS guarantees that after moved, each activity is scheduled in the left-most and bottom-most position within a coordinate, which means that each activity in the corresponding project is arranged as early as possible when the precedence constraints and resource demands are satisfied. In addition, the multiagent evolutionary algorithm (MAEA) is employed to incorporate with the newly designed MBS representation in solving RIPSPs. With the intrinsic properties of MBS in mind, four behaviors, namely the crossover, mutation, competition, and self-learning operators are designed for agents in MAEA. To test the performance of our algorithm, 450 problem instances are used and the experimental results demonstrate the good performance of the proposed representation.

    Citation: Xiaoxiao Yuan, Jing Liu, Xingxing Hao. 2017: A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems, Big Data and Information Analytics, 2(1): 39-58. doi: 10.3934/bdia.2017007

    Related Papers:

  • Inspired by the representation designed for floorplanning problems, in this paper, we proposed a new representation, namely the moving block sequence (MBS), for resource investment project scheduling problems (RIPSPs). Since each activity of a project in RIPSPs has fixed duration and resource demand, we consider an activity as a rectangle block whose width is equal to the duration of the activity and height the resource needed by the activity. Four move modes are designed for activities, by using which the activity can move to the appropriate position. Therefore, the new representation of the project of RIPSPs consists of two parts: an activity list and a move mode list. By initializing the move modes randomly for each activity and moving it appropriately, the activity list can be decoded into valid solutions of RIPSPs. Since the decoding method of MBS guarantees that after moved, each activity is scheduled in the left-most and bottom-most position within a coordinate, which means that each activity in the corresponding project is arranged as early as possible when the precedence constraints and resource demands are satisfied. In addition, the multiagent evolutionary algorithm (MAEA) is employed to incorporate with the newly designed MBS representation in solving RIPSPs. With the intrinsic properties of MBS in mind, four behaviors, namely the crossover, mutation, competition, and self-learning operators are designed for agents in MAEA. To test the performance of our algorithm, 450 problem instances are used and the experimental results demonstrate the good performance of the proposed representation.



    加载中
    [1] Abbass H. A., Bender A., Dam H., Baker S., Whitacre J. M., Sarker R. A. (2008) Computational scenario-based capability planning. in Genetic and Evolutionary Computation Conference (GECCO), ACM, Atlanta, Georgia 1437-1444. doi: 10.1145/1389095.1389378
    [2] Brucker P., Drexl A., Möhring R., Neumann K., Pesch E. (1999) Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112: 3-41. doi: 10.1016/S0377-2217(98)00204-5
    [3] Bui L. T., Barlow M., Abbass H. A. (2009) A multi-objective risk-based framework for mission capability planning. New Mathematics and Natural Computation 5: 459-485. doi: 10.1142/S1793005709001428
    [4] Chicano F., Luna F., Nebro A. J., Alba E. (2011) Using multi-objective metaheuristics to solve the software project scheduling problem. in GECCO'11 Proceedings of the 13th annual conference on Genetic and evolutionary computation, ACM, Dublin, Ireland 1915-1922. doi: 10.1145/2001576.2001833
    [5] Cho S.-H., Eppinger S. D. (2005) A simulation-based process model for managing complex design projects. IEEE Trans. Engineering Management 52: 316-328. doi: 10.1109/TEM.2005.850722
    [6] Debels D., Reyck B. D., Leus R., Vanhoucke M. (2006) A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research 169: 638-653, Feature Cluster on Scatter Search Methods for Optimization. doi: 10.1016/j.ejor.2004.08.020
    [7] Demeulemeester E. (1995) Minimizing resource availability costs in time-limited project networks. Management Science 41: 1590-1598. doi: 10.1287/mnsc.41.10.1590
    [8] Depenbrock B., Balint T., Sheehy J. (2015) Leveraging design principles to optimize technology portfolio prioritization. in 2015 IEEE Aerospace Conference 1-10. doi: 10.1109/AERO.2015.7119203
    [9] Drexl A., Kimms A. (2001) Optimization guided lower and upper bounds for the resource investment problem. The Journal of the Operational Research Society 52: 340-351. doi: 10.1057/palgrave.jors.2601099
    [10] Hindi K. S., Yang H., Fleszar K. (2002) An evolutionary algorithm for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation 6: 512-518. doi: 10.1109/TEVC.2002.804914
    [11] Kolisch R. (1996) Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research 90: 320-333. doi: 10.1016/0377-2217(95)00357-6
    [12] Kolisch R., Hartmann S. (1999) Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. Project Scheduling 147-178. doi: 10.1007/978-1-4615-5533-9_7
    [13] Kolisch R., Hartmann S. (2006) Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research 174: 23-37. doi: 10.1016/j.ejor.2005.01.065
    [14] Kolisch R., Sprecher A., Drexl A. (1995) Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science 41: 1693-1703. doi: 10.1287/mnsc.41.10.1693
    [15] Liu J., Zhong W., Jiao L. (2010) A multiagent evolutionary algorithm for combinatorial optimization problems. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 40: 229-240.
    [16] Liu J., Zhong W., Jiao L., Li X. (2008) Moving block sequence and organizational evolutionary algorithm for general floorplanning with arbitrarily shaped rectilinear blocks. IEEE Transactions on Evolutionary Computation 12: 630-646.
    [17] Liu J., Zhong W., Jiao L. (2006) A multiagent evolutionary algorithm for constraint satisfaction problems. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 36: 54-73.
    [18] Minku L. L., Sudholt D., Yao X. (2012) Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design. in GECCO'12 Proceedings of the 14th annual conference on Genetic and evolutionary computation, ACM, Philadelphia, Pennsylvania USA 1221-1228. doi: 10.1145/2330163.2330332
    [19] Möhring R. H. (1984) Minimizing costs of resource requirements in project networks subject to a fixed completion time. Operational Research 32: 89-120.
    [20] Nübel H. (2001) The resource renting problem subject to temporal constraints. OR-Spektrum 23: 359-381. doi: 10.1007/PL00013357
    [21] C. Qian, Y. Yu and Z. -H. Zhou, Variable solution structure can be helpful in evolutionary optimization Science China Information Sciences, 58 (2015), 112105, 17 pp.

    10.1007/s11432-015-5382-y

    MR3416545

    [22] Reyck B. D., Leus R. (2008) R&d project scheduling when activities may fail. IIE Transactions 40: 367-384. doi: 10.1080/07408170701413944
    [23] Schultz S. R., Atzmon J. (2014) A simulation based heuristic approach to a resource investment problem (rip). in Proceedings of the Winter Simulation Conference 3411-3422. doi: 10.1109/WSC.2014.7020174
    [24] Shadrokh S., Kianfar F. (2007) A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. European Journal of Operational Research 181: 86-101. doi: 10.1016/j.ejor.2006.03.056
    [25] Xiong J., Liu J., Chen Y., Abbass H. A. (2014) A knowledge-based evolutionary multiobjective approach for stochastic extended resource investment project scheduling problems. IEEE Transactions on Evolutionary Computation 18: 742-763.
    [26] Xiong J., wei Yang K., Liu J., song Zhao Q., Chen Y.wu. (2012) A two-stage preference-based evolutionary multi-objective approach for capability planning problems. Knowledge-Based Systems 31: 128-139. doi: 10.1016/j.knosys.2012.02.003
    [27] Zhong W., Liu J., Xue M., Jiao L. (2004) A multiagent genetic algorithm for global numerical optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 34: 1128-1141.
  • Reader Comments
  • © 2017 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3219) PDF downloads(512) Cited by(1)

Article outline

Figures and Tables

Figures(6)  /  Tables(5)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog