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:

    [1] Ioannis D. Schizas, Vasileios Maroulas, Guohua Ren . Regularized kernel matrix decomposition for thermal video multi-object detection and tracking. Big Data and Information Analytics, 2018, 3(2): 1-23. doi: 10.3934/bdia.2018004
    [2] Weidong Bao, Wenhua Xiao, Haoran Ji, Chao Chen, Xiaomin Zhu, Jianhong Wu . Towards big data processing in clouds: An online cost-minimization approach. Big Data and Information Analytics, 2016, 1(1): 15-29. doi: 10.3934/bdia.2016.1.15
    [3] Marco Tosato, Jianhong Wu . An application of PART to the Football Manager data for players clusters analyses to inform club team formation. Big Data and Information Analytics, 2018, 3(1): 43-54. doi: 10.3934/bdia.2018002
    [4] Jinyuan Zhang, Aimin Zhou, Guixu Zhang, Hu Zhang . A clustering based mate selection for evolutionary optimization. Big Data and Information Analytics, 2017, 2(1): 77-85. doi: 10.3934/bdia.2017010
    [5] Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong . An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data and Information Analytics, 2017, 2(1): 23-37. doi: 10.3934/bdia.2017006
    [6] Bill Huajian Yang . Modeling path-dependent state transitions by a recurrent neural network. Big Data and Information Analytics, 2022, 7(0): 1-12. doi: 10.3934/bdia.2022001
    [7] Guojun Gan, Qiujun Lan, Shiyang Sima . Scalable Clustering by Truncated Fuzzy c-means. Big Data and Information Analytics, 2016, 1(2): 247-259. doi: 10.3934/bdia.2016007
    [8] Xiaoying Chen, Chong Zhang, Zonglin Shi, Weidong Xiao . Spatio-temporal Keywords Queries in HBase. Big Data and Information Analytics, 2016, 1(1): 81-91. doi: 10.3934/bdia.2016.1.81
    [9] Dongyang Yang, Wei Xu . Statistical modeling on human microbiome sequencing data. Big Data and Information Analytics, 2019, 4(1): 1-12. doi: 10.3934/bdia.2019001
    [10] M Supriya, AJ Deepa . Machine learning approach on healthcare big data: a review. Big Data and Information Analytics, 2020, 5(1): 58-75. doi: 10.3934/bdia.2020005
  • 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. Introduction

    The project scheduling problems (PSPs) are very general issues in the area of planning [1,3,26], management [22], engineering [4,18], and designing [5]. To solve PSPs, the objectives may be minimizing the cost, total makespan or due date performance [25]. The resource investment project scheduling problem (RIPSP) is a variation of PSPs with no limitation on the resource capacity, and the objective is to minimize total resource costs with a due date.

    In recent years, RIPSPs have attracted increasing attentions. Möhring in [19] discussed minimizing costs of resource requirements with a fixed completion duration in the early years. He considered this problem as the problem of scarce time and proved that this problem is NP-hard. Demeulemeester [7] presented another exact algorithm for resource investment problems and considered this problem as the resource availability cost problem (RACP). Drexl et al. in [9] discussed the lower and upper bounds using Lagrangian relaxation and column generation methods. An extension of resource investment problems that included time dependent renting costs for resources and the maximum and minimum time lags was studied by Nübelin [20], which was labeled as the resource renting problem (RRP), and a depth first branch and bound algorithm was proposed. Brucker et al. [2] gave a comprehensive survey of problems of scarce time, scarce resources, and other PSPs. Leveraging design principles to optimize technology portfolio prioritization was studied by Depenbrock et al. [8] and a simulation based heuristic approach for handling RIP was presented in [23].

    The genetic algorithm (GA) has been used to solve RIPSPs by Shadrokh et al. in [24], in which, a valid activity sequence and four available resource capacities generated between the lower and upper bounds were initialized as an individual. Then, the algorithm started with the initial individuals and optimized the makespan as well as the four available resource capacities. Serial schedule generation scheme (SGS) is used to obtain the makespan. And they changed the four available resource capacities one by one in the procedure of finding optimal solutions. In the fitness function, they jointed both the makespan and the four available resource capacities with two reasonable penalty values together.

    Recently, Xiong et al. in [25] proposed an evolutionary multi-objective approach for stochastic extended resource investment project scheduling problems (SERIPSPs) which is a new version of RIPSPs. They employed scenarios to capture the space of possibilities and proposed a robustness measure for the solutions when uncertainties like duration perturbation, resource breakdown, and precedence alteration interact. Finally, the SERIPSPs have been formulated as multiobjective optimization problems with the objectives as makespan, cost, and robustness. The experiments show that their approach is effective in solving SERIPSPs.

    The representation is a very important component in solving RIPSPs, which determines the size and topology of the searching space. Among all literature we mentioned above in solving RIPSPs or their variations, the representation used for the projects consists of two parts: the activity sequence and the resource capacity list. The SGS used to transform activity sequences to precedence feasible schedules is either serial schedule generation scheme (SSS) or parallel schedule generation scheme (PSS) [11,12,13]. The SSS can always generate an active schedule and guarantee that each active schedule corresponds to an appropriate activity sequence [11], but it has the disadvantage that the same schedule may be mapped from more than one activity sequence [6], which means that the size of encoding space is greater than the active schedules [10]. As for the PSS, it can always generate a feasible schedule if does exist. However, it suffers from the weakness that the schedule it generates might not be the optimal schedule [11].

    In [16], a new representation, namely moving block sequence (MBS), has been proposed to solve the floorplanning problem which is a basic step in the physical design of very large scale integration (VLSI). Liu et al. in [16] analyzed the strength of MBS thoroughly and obtained the conclusion that the four moving modes of MBS are useful and the MBS is a successful extension of the bottom-left (BL) and bottom-left-fill (BLF) method, which are classical approaches in the field of cutting and packing, and the computational complexity for decoding the MBS to a floorplan is between linear and quadratic in considering the number of blocks. Through numerous experiments they declared that the MBS is very useful for extending the applications of evolutionary algorithms (EAs) in the area of floorplanning. Thus, with the intrinsic properties of RIPSPs in mind and inspired by the MBS, we come up with the idea that considering an activity as a rectangle block whose width is equal to the activity duration and height the resource needed by the activity. For each activity, there are four types of move modes which are similar to [16]. Therefore, we can encode the projects into the representation that consist of two parts: the activity list and move mode list. Then, the activity list is decoded into an active schedule according to the corresponding move modes.

    From [16] we can know that by using MBS representation in RIPSPs, the computational complexity of decoding an activity list into an active schedule is between linear and quadratic in terms of the activity number, and the decoding process guarantees that the activity will be arranged as early as possible when the precedence constraints are satisfied. With the decoding method, we do not need to initial the available resource capacities within a lower and upper bounds as proposed in [24] and then optimize them step by step. We just need to calculate the maximum width and height of the placed activities at the end of decoding. And according to the obtained results, a directional mutation operator is designed. Moreover, the decoding method and the MBS representation can be applied to any EAs in the area of PSPs. Theoretical analyses that conducted in [21] show that the representation of solution is important for the effectiveness of evolutionary algorithms.

    Many previous works show that the multiagent evolutionary algorithm (MAEA) has great potential in solving NP-hard problems [15,17,27]. In this paper, we integrate MAEA with MBS to solve RIPSPs and the proposed approach is labeled as MBSMAEA-RIPSP. Four behaviors, namely crossover, mutation, competition, and self-learning operator, are designed for the agents in considering the environment they live. To test the performance of MBSMAEA-RIPSP, the experiments are conducted on Möhring instances and three generated test sets J10, J14 and J20. By comparing with other EAs that have been employed to deal with the same test sets, the experimental results demonstrate that the MBSMAEA-RIPSP can obtain better performance.

    The remaining parts of the paper are organized as follows. Section 2 gives the definition RIPSPs. Section 3 describes the MBS representation for RIPSPs. Section 4 presents the algorithm for transforming an MBS to a schedule. Section 5 introduces MBSMAEA-RIPSP in detail, including the definition of agents, design of operators and the general framework of MBSMAEA-RIPSP. Section 6 shows the experimental results. Finally, conclusions are given in Section 7.


    2. RIPSPs

    In a RIPSP [24], the project is represented as a directed activity-on-node (AON) network G shown in FIGURE 1. In an AON network, each node denotes an activity and the arrow line represents the precedence relationship between two activities i.e. if there is an arrow line from activity v to w, then v precedes w, which means activity w cannot start before v is finished. Thus, v is the predecessor of w and w is the successor of v. Note that one activity may have more than one predecessor and successor as well. For each activity i, let Pi represent the set of predecessors of it, and Si the set of successors. The network G contains n non-dummy activities with two dummy activities labeled as 0 and n+1, which are the initial and terminal activities respectively. K = {1, 2, , ρ} is a set of ρ renewable resource(s). Each activity i (i = 0, 1, , n+1) has a fixed duration Di and requires rik units of renewable resource k (kK) during its duration. For two dummy activities, we have D0 = Dn = 0 and r0,k = rn+1,k = 0, k K. The objective of RIPSPs is to determine the start time of activity i, Si, (i = 0, 1, , n+1), and the available resource capacity Rk (k K), such that the precedence relations of activities are satisfied and the total cost of all resources and tardiness penalty is minimized. A constant cost of Cd for each unit of time delay from a due date T is incurred and Ck is a resource cost for each unit of available capacity. Let xi,t be 1 if activity i starts at time t and 0 otherwise, then we have Si = t=0Tt×xi,t. The mathematical model of RIPSPs can be described as follows,

    min{k=1ρCkRk+Cd×max{0,Sn+1T}} (1)
    s.t.t=0Tt×xi,tDj+t=0Tt×xj,t,  jPi,i=1,2,,n+1 (2)
    i=1nu=tDi+1tri,k×xi,uRk,  t=0,,T,k{1,2,,ρ} (3)
    t=0Txi,t=1,  i=1,2,,n+1 (4)
    x1,0=1 (5)
    xi,t{0,1},  i=1,2,,n+1,t=0,1,,T (6)
    Rk0,  kK={1,2,,ρ} (7)
    Figure 1. An example of precedence graph.

    where objective (1) is to minimize the total cost of a project. Constraints (2) is the precedence relation between each pair of activities (i,j), where j immediately precedes i. And (3) limits the total resource usage within each period to the available amount. Constraints (4) and (5) make sure that each activity i can only have one start time. (6) and (7) are the range of certain variables.


    3. Moving block sequence representation for RIPSPs

    In a RIPSP, there are n activities need to be scheduled. To solve RIPSPs with the idea of MBS designed for floorplanning problems, we need to first transform each activity into a hard rectangular block. It is well-known that in RIPSP, each activity has a fixed duration and demands for several renewable resources. Therefore, the fixed duration of an activity can be regarded as the width of a hard rectangular block and the maximum resource demand as the height of the block. After transforming all activities to blocks, the block will be placed in the first quadrant shown as FIGURE 2, in which the X-axis stands for the time and the Y-axis is the resource. In addition, to locate the position of a block in the coordinate, two variables xlb and ylb, which corresponds to the abscissa and ordinate of the lower left corner of the block respectively, are necessary to be defined. Assume Bi, (i = 0, 1, ……, n+1), where B0 and Bn+1 are two dummy blocks, denotes the blocks that correspond to the n-activity project, the information structure of block Bi is defined as follows,

    Figure 2. An example of precedence graph.

    struct Bi

    {

    (xlb, ylb): coordinate of the left-bottom corner of block Bi;

    width: width of block Bi;

    height: height of block Bi.

    }

    where B0.width = Bn+1.width = 0 and B0.height = Bn+1.height = 0.

    Each block starts from an initial position and moves in the first quadrant until it reaches an appropriate position. Four initial positions labeled as 0 to 3 shown in FIGURE 2 are designed and the corresponding move rules will be described in the following context.

    In FIGURE 2, (BoxRX, BoxTY) is the coordinate of the right-top corner of the shaded rectangle. And the coordinate of the left-bottom corner of shaded rectangle is always (0, 0). Suppose that i-1 blocks have been placed in the shaded rectangle. For the ith block Bpi in the block list, the four move rules corresponding to the four initial positions are described as follows,

    Move rule 0: the coordinates of initial positions (Bpi.xlb, Bpi.ylb) are set to (max_t, BoxTY), where max_t is the maximum finish time among all predecessors of activity i. From the initial position, the block can only move downward until no downward movement is possible.

    Move rule 1: the coordinates of initial positions (Bpi.xlb, Bpi.ylb) are set to (BoxRX, 0). Then this block can only move leftward until no leftward movement is possible.

    Move rule 2: the coordinates of initial positions (Bpi.xlb, Bpi.ylb) are set to (BoxRX-Bpi.width, BoxTY). Then this block can repeatedly move downward and leftward. Giving priority to downward movement so that this block can only moves leftward if no downward movement is possible. But sometimes the initial positions above may violate precedence relationship constraints. If that happens, then we need to adjust the initial position to (max_t, BoxTY) and it can only move downward until no downward movement is possible.

    Move rule 3: the coordinates of initial position (Bpi.xlb, Bpi.ylb) are set to (BoxRX, emphBoxTY-Bpi.ylb). Then this block can repeatedly move leftward and downward. Giving priority to left movement so that this block can only move downward if no left movement is possible.

    Given the activity list and the move mode list, an MBS can be defined as follows, Definition 3.1. An MBS has two vectors, namely a block list and a move mode list.

    MBS=((Bp0,Bp1,,Bpn,Bpn+1),(M0,M1,,Mn,Mn+1))F (8)

    where the first part is the corresponding block list that consists of a valid permutation of n non-dummy blocks which satisfies precedence constraints, and two dummy blocks Bp0 and Bpn+1 which correspond to block B0 and Bn+1, respectively. The second part denotes the move mode list which is randomly initialized between 0 and 3. F represents the encoding space, namely, the search space.

    Theorem 3.2. The size of search space F for activities satisfies 4n|S|n!4n.

    Proof. From Definition 3.1 we can know that one MBS consists of a list of activities and a list of move mode. In reality, the activity list is a permutation of all activities, thus, if we consider an extreme condition that for each non-dummy activity there is one and only one predecessor and one successor activity, which means only one possible permutation exists, the lower bound of the size of search space is equal to 1×4n, in which 4n is the number of combination of move modes. For another extreme case, if the precedence relationship among activities are not taken into consideration, the number of combination of activities is n! and integrate with the effect of move mode, the upper bound is obtained equals to n!4n. However, in actual RIPSPs these two extreme conditions can barely happen, for there exist intricate precedence constraints among activities and many types of resource constraints for each activity. Therefore, the size of search space is much larger than the lower bound and much smaller than the upper bound, simultaneously.

    To generate a valid block list of an MBS which satisfies precedence constraints, the Algorithm 2 described in [10] which enumerates all the topological orders of a network G is employed.


    4. Algorithm transforming an MBS to a schedule

    The location relationships between blocks need to be considered when moving them. We know that each hard rectangular block has four edges, namely top, bottom, left, and right edge. According to the designed four move rules, all blocks need to be moved leftward or downward. The problem of finding the reasonable left-most or the bottom-most of a block is changed to that of judging the relative position between two edges. Liu et al. [16] designed suitable structures e//X and e//Y to record the positions of edges that parallel to X-axis and Y-axis, respectively. In MBSMAEA-RIPSP, we also employ the structures of e//X and e//Y to record edge information, with which we can easily judge if a block can further move or not. The description of e//X and e//Y are as follows,

    struct e//X

    {

    xl: X-coordinate of the left point;

    xr: X-coordinate of the right point;

    y: Y-coordinate of the bottom edge.

    }

    struct e//Y

    {

    x: X-coordinate of the edge;

    yb: Y-coordinate of the bottom point;

    yt: Y-coordinate of the top point.

    }

    If a block is projected to the X-axis vertically or to the Y-axis horizontally, the blocks in the projection area will affect the bottom-most or the left-most position where this block can move to. Thus, two types of overlap relations are defined in Definition 4.1, and FIGURE 3 shows all kinds of top-overlaps and right-overlaps, in which the shadow areas are the projection of block A.

    Figure 3. The types of overlaps. (a) All kinds of top-overlaps, (b) all kinds of right-overlaps.

    Definition 4.1. Let a//X and b//X be two edges parallel to the X-axis. If a//X and b//X satisfy (9), a//X top-overlaps b//X; otherwise, a//X un-top-overlaps b//X. Let a//Y and b//Y be two edges parallel to the Y-axis. If a//Y and b//Y satisfy (10), a//Y right-overlaps b//Y; otherwise, a//Y un-right-overlaps b//Y.

    (a//X(y)b//X(y)) and (a//X(xr)>b//X(xl)) and (a//Y(xl)<b//X(xr)) (9)
    (a//Y(x)b//Y(x)) and (a//Y(yt)>b//Y(yb)) and (a//Y(yb)<b//Y(yt)) (10)

    Assume that CoverRightX and CoverTopY stand for the left-most and the bottom-most positions where blocks can move to, respectively, i.e., CoverRightX is the X-coordinate of the left-most position where a block can move leftward and CoverTopY is the Y-coordinate of the bottom-most position where a block can move downward. With the intrinsic properties of hard rectangular blocks and the precedence constraints among activities in mind, the appropriate position where a block can move to is given as follows.

    When moving leftward, there are two conditions to stop block A. The first condition is the left edge of block A right-overlaps the right edge of block B, as can be seen in FIGURE 3(b). We mark the position as CoverRightXi; the second condition is that the X-coordinate of the left edge of block A is equal to max_t, where max_t is the maximum finish time of the predecessors of activity A. According to the above cases, CoverRightXmax(CoverRightXi,max_t), where max(m,n) returns the maximum between m and n. Finding the bottom-most position CoverBottomY is analogous to CoverRightX, except that the precedence constraints can be omitted.

    When block A top-overlaps block D, there may exist some other continuous blocks have the same Y-coordinate with block D, as shown in FIGURE 4. The minimum X-coordinates of the left edges of those blocks is labeled as CoverLeftX. In the same way we can get the CoverTopY. If CoverLeftX > CoverRightX and CoverLeftX -CoverRightX A.duration, the downward movement of A is feasible after moved leftward, otherwise, block A cannot move downward furthermore, i.e. it will stop at CoverRightX. Similarly, if CoverTopY > CoverBottomY and CoverTopY -CoverBottomY A.height, the leftward movement of A is feasible after moved downward, otherwise, block A will stop at CoverBottomY.

    Figure 4. Relative positions of CoverLeftX and CoverRightX. (a) and (b) are the cases without violating precedence constraints. (c) and (d) are the cases violating precedence constraints.

    In general, almost every block will move repeatedly leftward and downward until reach the stopping criterion. For example, the blocks that have the initial position 3 will move leftward firstly to the CoverRightX, then performing the judgment that whether the blocks can move downward or not. If the blocks can further move, then the corresponding movement will be conducted until they are placed in the appropriate positions. For the blocks that have other initial positions, similar procedures are conduceted.

    FIGURE 4(a) and (b) are two cases without precedence constraints, in which block A moves left until right-overlaps block B. FIGURE 4(c) and (d) are cases considering the precedence constraints, where C is a predecessor of block A, thus block A will stop when reaches the right edge of block C.

    BtoT//X and LtoR//Y denote two ordered sets of edges which are parallel to the X-axis and Y-axis, respectively. They are designed to record the top edges from bottom to top and the right edges from left to right of the blocks that have been placed. Algorithm 1 describes the algorithm of transforming an MBS from an initial block list and a corresponding move mode list to a schedule and FIGURE 5 shows the overall process clearly. All blocks will be placed and moved in the first quadrant. Since Bp0 and Bpn+1 are two dummy blocks, they are omitted during the transforming procedure and Bp1 is placed directly at the most left-bottom corner of the first quadrant, then Bpi, i [2, n] will be moved iteratively according to the move mode list at the first quadrant in the order they occur in block list.

    Figure 5. The decoding process.

    In Algorithm 1, when all blocks have been placed in the first quadrant, BoxRX is the total makespan of the project. From above we know that the maximum resource demand of every activity is regarded as the height of the related block, therefore, the BoxTY is not the actual resource capacity that needed by the project. Thus, there is a need to calculate the actual resource capacity Rk (k K).

    Algorithm 1 Transforming an MBS to a schedule
    Input: MBS: An MBS in solution space F;
    Output: f(MBS): The fitness of the MBS;
    1: (Bp0.xlb,Bp0.ylb)(0,0); /*Bp0 is a dummy block.*/
    2: (Bp1.xlb,Bp1.ylb)(0,0); /*Put Bp1 at the left-bottom corner of the first quadrant.*/
    3: (BoxRX,BoxTY)(Bp1.width,Bp1.height);
    4: Add the top edge of Bp1 into BtoT//X;
    5: Add the right edge of Bp1 into LtoR//Y;
    6: for (i=2,i<n,i++) do
    7:   if Mi=0 then /*Only move downward.*/
    8:     (Bpi.xlb,Bpi.ylb)(max_t,BoxTY);
    9:     Calculate CoverTopY for Bpi from BtoT//X;
    10:     Bpi.ylbCoverTopY;
    11:   else if Mi=1 then /*Only move leftward.*/
    12:     (Bpi.xlb,Bpi.ylb)(BoxRX,0);
    13:     Calculate CoverRightX for Bpi from LtoR//Y;
    14:     Bpi.xlbCoverRightX
    15:   else if Mi=2 then /*Two cases are considered according to whether violating precedence constraints or not.*/
    16:      if max_t(BoxRXBpi.width) then /*Violating precedence constraints, move downward only.*/
    17:       (Bpi.xlb,Bpi.ylb)(max_t,BoxTY);
    18:       Similar to case 0;
    19:      else /*Do not violate precedence constraints, repeat downward and leftward movement.*/
    20:       (Bpi.xlb,Bpi.ylb)(BoxRXBpi.width,BoxTY);
    21:       CanMovetrue;
    22:       while (CanMove=true) do
    23:        Calculate CoverTopY for Bpi from BtoT//X;
    24:        Bpi.ylbCoverTopY;
    25:        Calculate CoverRightX for Bpi from LtoR//Y;
    26:        Calculate CoverLeftX for Bpi;
    27:        if (CoverRightXCoverLeftX) or ((CoverRightX<CoverLeftX) and ((CoverLeftXCoverRightX)<Bpi.width)) then
    28:         Bpi.xlbCoverRightX;
    29:         CanMovefalse
    30:        else
    31:         Bpi.xlbCoverLeftXBpi.width;
    32:         CanMovetrue
    33:        end if
    34:       end while
    35:      end if
    36:   else if Mi=3 then /*Repeat leftward and downward movement.*/
    37:     (Bpi.xlb,Bpi.ylb)(BoxRX,max(0,BoxTYBpi.height));
    38:     CanMovetrue;
    39:     while (CanMove=true) do
    40:      Calculate CoverRightX for Bpi from LtoR//Y;
    41:      Bpi.xlbCoverRightX;
    42:      Calculate CoverTopY for Bpi from BtoT//X;
    43:      Bpi.ylbCoverTopY;
    44:      if Bpi.xlb=max_t then
    45:        break;
    46:      else
    47:        Calculate CoverBottomY for Bpi;
    48:      end if
    49:      if(CoverBottomYCoverTopY) or ((CoverBottomY>CoverTopY) and ((CoverBottomYCoverTopY)<Bpi.height)) then
    50:        Bpi.ylbCoverTopY;
    51:        CanMovefalse;
    52:      else
    53:        Bpi.ylbCoverBottomYBpi.height;
    54:        CanMovetrue;
    55:      end if
    56:     end while
    57:    end if
    58:    Update (BoxRT,BoxTY);
    59:    Add the top edge of Bpi into BtoT//X, and keep the order of BtoT//X;
    60:    Add the right edge of Bpi into LtoR//Y, and and keep the order of LtoR//Y;
    61: end for
    62: Calculate available resource capacity Rk for each kind of resource;
    63: Calculate f(MBS);

    In the proposed MBSMAEA-RIPSP, the idea of Effective Activity (EA) and the set of all EA for resource k, AEAk that described in [24] are employed to find the available resource capacity Rk (k K). For an MBS and resource k, activity j is defined to be an EA in AEAk, if this activity or parts of it, is scheduled during time intervals [Si, Si + Di], i.e., width interval [Bpi.xlb, Bpi.xlb + Bpi.width] on X-axis. In this way, we find each AEAki for each activity i. Before finding the maximum amount of resource k, we need to eliminate the activities with precedence constraints in each AEAki. After that, we add up resource usage for each activity in an AEAki and label it as Qki. Then the maximum Qki is the available resource capacity Rk.

    Taking into account the makespan and available resource capacity Rk (k K), the value of fitness of MBS can be defined as follows,

    f(MBS)=k=1ρCkRk+Cd×max{0,Sn+1T} (11)

    In FIGURE 5, parts one to four stand for the four designed move rules. The values of (BoxRT, BoxTY), BtoT//X and LtoR//Y are updated in part five after schedule of a new block in the block list. After all blocks have been placed in the appropriate positions, the fitness of the MBS will be calculated in the end part.


    5. MBSMAEA-RIPSP

    Since many previous works show that the MAEA has great potential in solving complex problems [15,17,27], we integrated the MBS with MAEA to solve the RIPSPs, which is labeled as MBSMAEA-RIPSP.


    5.1. Agents based on MBS

    With the intrinsic properties of the MBS and RIPSPs in mind, the agent in MBSMAEA-RIPSP is defined as follows,

    Definition 5.1. An agent, labeled as I, represents a candidate solution in the search space F, and is encoded using two integer vectors:

    I=MBS=((Bp0,Bp1,,Bpn,Bpn+1),(M0,M1,,Mn,Mn+1))  IF (12)

    For each agent I, we can get a makespan and an available resource capacity for each kind of resource. The energy of I is equal to the negative value of its associated objective function value, namely Energy(I)=f(I). The purpose of I is to increase its energy as much as possible by the behaviors it can take.

    As described in [15,17,27], all agents in MBSMAEA-RIPSP live in a lattice-like environment, which is called the agent lattice. Each agent is fixed on a lattice point and can only interact with its neighbors. The agent lattice can be represented as FIGURE 6. In this paper, we define the size of agent lattice as Rsize×Csize. Each agent has eight neighbors. Suppose that agent I locates at (i,j), then the sets of eight neighborhood domains are described as follows. For example, in FIGURE 6, the agent in position (2, 2) is connected to its eight neighbors with imaginary lines.

    neighbors(I)={(i,j),(i,j),(i,j),(i,j),(i,j),(i,j),(i,j),(i,j)} (13)
    Figure 6. The agent lattice of MBSMAEA-RIPSP.

    where

    i={i1i1Rsizei=1,  j={j1j1Csizej=1i={i+1iRsize1i=Rsize,  j={j+1jCsize1j=Csize (14)

    5.2. Operators for agents

    In MBSMAEA-RIPSP, four operators are employed to explore the search space. In addition to the crossover and mutation operators, the competition and self-learning operators are designed for agents to gain more energy.


    5.2.1. Crossover

    In MBSMAEA-RIPSP, two-point crossover based on MBS representation is designed. Assume this operator conduct on two parents p1 and p2, where p2 is the agent that with the largest energy among the neighbors of p1. Since there are precedence constraints among activities, one of the significant properties of the crossover operator should be maintaining the precedence constraints, in other words, the children produced by crossover operator should be feasible. Therefore, the two-point crossover operator introduced by Hindi et al. in [10] is employed to the activity list. As for the move mode list, the general two-point crossover operator is utilized.


    5.2.2. Mutation

    The mutation operator is designed to reintroduce diversity to the population. It is conducted both on the activity list and the move mode list. For the part of the activity list, the classical mutation operation introduced in [10] is employed, in which an activity is moved randomly between the position of its last predecessor and first successor according to the temporary order of the activity list. Thus the newly generated activity list is still feasible.

    As mentioned before that all activities move in the first quadrant and the objective of RIPSPs is to minimize the summation of the project makespan and the resource capacity. Moreover, the position that an activity will be placed can be partially decided by the move modes. Therefore, according to whether the makespan of a project exceed the due date or not, a direction-based mutation operator is designed for the move mode list. If the project makespan is larger than the due date, then our goal is to increase the upper bounds of resources, i.e., the available resource capacities Rk (kK), while decreasing the makespan. Otherwise, our goal is to increase the makespan while decreasing the upper bound of resource. The details of the mutation operator designed for the move mode list are given in Algorithm 2.

    Algorithm 2 Mutation operator for move mode list
    Input: I: An agent;
    Output: I: The agent after performing the mutation operator;
    1: if makespan(I)>T then
    2:   Choose an activity v at random from 1 to n;
    3:   Find Pv and Sv;
    4:   for (i=0;i<n+1;i++) do
    5:      if s[i]Pv then
    6:        Set the move mode of activity s[i] in agent I to 0;
    7:      else if s[i]Sv then
    8:        Set the move mode of activity s[i] in agent I to 2;
    9:      end if
    10:   end for
    11: else
    12:   Choose an activity w at random from 1 to n;
    13:   Find Pw and Sw;
    14:   for (i=0;i<n+1;i++) do
    15:     if s[i]Pw or s[i]Sw then
    16:       Set the move mode of activity s[i] in agent I to 3;
    17:      end if
    18:   end for
    19: end if
    20: Transform the agent I to a schedule;

    In Algorithm 2, if the makespan of the project exceed the due date, the decreasing of the total makespan is desired. Thus, the move modes of the predecessors and the successors of the randomly chosen activity v are set to 0 and 2 respectively, which means that the initial positions of these activities preferred to be in the top edge of the placed blocks, and according to the related move rules, these activities will be placed within BoxRX, which guarantees the decreasing of the total makespan. Otherwise, the move modes of predecessors and successors of activity w are set to 3, in which the positions of these activities are initialized to the left edge of the placed blocks, which guarantees the decreasing of the available resource capacities.


    5.2.3. Competition

    For an agent I on the agent lattice, an eight-neighbor competition operator is designed. The comparison between I and its strongest neighbor I, which has the maximum energy among all eight neighbors, is conducted. If Energy(I)>Energy(I), I is a winner and it can survive on the agent lattice, otherwise, it is a loser and will be occupied by agent I. After the competition operator is conducted, agents that with low energy are replaced by better agents, which generally speaking will increase the total energy of the whole population. Moreover, by replacing the low-energy agents, more opportunities can be given to the better agents, which to some extent can schedule the computational efforts more appropriately.


    5.2.4. Self-Learning

    It is well-known that the incorporation with local search can accelerate the convergence speed of EAs. Therefore, the self-learning operator is designed as a local search to further increase the energy of an agent. From above we can know that the mutation operator is self-adaptive to some extent, thus it is employed in self-learning operator to generate alternative agents.

    In self-learning operator, the designed mutation operator will be conducted iteratively for SelfLTime times. After each iteration, if the energy of the newly generated agent is larger than the old one, then the old agent will be replaced by the newly generated one; otherwise, no operation will be conducted. Therefore, after performing the self-learning operator on an agent, its energy will be increased as much as possible. In order to reduce the computational cost, the self-learning operator is only performed on the best agent in each generation. The details of self-learning operator are given in Algorithm 3.

    Algorithm 3 Self-learning operator
    Input: I: Agent I;
            SelfLTime: The maximum number of iterations;
    Output: Agent I;
    1: for (i=0;i<SelfLTime;i++) do
    2:    I Mutation(I);
    3:    if Energy(I)>Energy(I) then
    4:       II;
    5:    end if
    6: end for

    5.3. Implementation of MBSMAEA-RIPSP

    In MBSMAEA-RIPSP, the population is initialized firstly, in which the algorithm described in [10] is employed in the initialization of the activity lists and the move mode for every activity is randomly initialized from 0 to 3. Then, the designed decoding algorithm that detailed in Algorithm 1 is used to generate the feasible schedules and the energy is calculated for every agent. The competition operator is conducted on every agent according to probability Pcom, after which the agents that with low energy are occupied by their strongest neighbors, as a consequence of increasing the total energy of the whole population. Afterwards, the crossover and mutation operator are performed for every agent with probability Pcro and Pmut, respectively. At the end of each generation, the self-learning operator is conducted on the best agent of the current generation with probability Psel. The whole evolution process will stop until reach the stopping criteria. The details of the MBSMAEA-RIPSP are described as Algorithm 4.

    Algorithm 4 MBSMAEA-RIPSP
    Input: G: An AON network;
             Pcro: Crossover probability;
             Pmut: Mutation probability;
             Pcom: Competition probability;
             Psel: Self-learning probability;
             Rsize and Csize: The number of rows and columns of the agent lattice;
             MaxGen: The maximum number of generations;
    Output: The best agent found;
    1: Initialize the agent lattice;
    2: For each agent, calculate f(I);
    3: repeat
    4:   for i=1,2,,Rsize,j=1,2,,Csize do
    5:     Conduct competition operator on agent I(i,j) with probability Pcom;
    6:   end for
    7:   for i=1,2,,Rsize,j=1,2,,Csize do
    8:     Conduct crossover operator on agent I(i,j) with probability Pcro;
    9:   end for
    10:  for i=1,2,,Rsize,j=1,2,,Csize do
    11:    Conduct mutation operator on agent I(i,j) with probability Pcro;
    12:  end for
    13:  if U(0,1)<Psel then
    14:    Conduct the self-learning operator on the best agent in the current generation;
    15:  end if
    16: until (reach the stopping criteria)

    6. Experiments and results

    In this section, Möhring instances [19] and the generated instances J10, J14, J20, which are generated by ProGen software [14], are used to test the performance of MBSMAEA-RIPSP. Möhring instances are a small bridge construction project, consisting of 18 activities and 4 kinds of resources. For each kind of resource, a per unit availability cost is defined, which is 1 or 3. Therefore, the combinations of unit availability costs for the four resource types are 16. The cost combination is labeled as C1/C2/C3/C4. Note that 1/1/1/1 is the same as 3/3/3/3, so the total number of combination is 15.

    For the generated instances J10, J14 and J20, there are 10, 14 and 20 non-dummy activities, respectively, and 4 kinds of renewable resources for every instance. Activity durations and resource requirements of the 4 types of resources are obtained using a discrete uniform distribution within [1,10]. The project networks have three non-dummy start activities and three non-dummy finish activities. The network complexity NC is set to 1.5, the resource factor RF is 1 and resource strength RS is set to 0.2. The maximum number of predecessors/successors is three. Original resource availabilities of single mode resource constraint project scheduling problem (SMRCPSP), which are generated by ProGen, are used as the unit cost of the corresponding resource type. The tardiness cost, Cd, is considered as 1/4 of the sum of the unit cost of the resources. Each network contains 20 instances.

    T is the due date of a project and T=θ×EFT, where EFT is the earliest finish time of the project having infinite resource capacities, and θ{1.0, 1.1, 1.2, 1.3, 1.4, 1.5}. Therefore, there are totally 15×6=90 test sets for Möhring instances and 20×6=120 test sets for J12, J16 and J22, respectively. The total number of instances is 90+120+120+120=450.


    6.1. Experiments on Möhring instances

    For Möhring instances, there are totally 90 instances. 20 independent experiments are conducted for each instance with the 1000 times of fitness evaluation as the stooping criterion. The size of agent lattice is set to Rsize=4, Csize=4, and Pcro=0.95, Pmut=0.85, Pcom=1.0, Psel=0.5, SelfLTime=12. The percentages of the number of finding the optimal solutions in all replications for each instance are shown in TABLE 1. The percentage value will be 1 if the MBSMAEA-RIPSP can find the optimal solution for all 20 times; otherwise, it will be smaller than 1.

    Table 1. The Percentages of Finding Optimal Solutions for MBSMAEA-RIPSP on Möhring Instances with 1000 Evaluations.
    C1/C2/C3/C4θ=1.0θ=1.1θ=1.2θ=1.3θ=1.4θ=1.5
    1/1/1/11.001.001.001.000.0670.033
    3/1/1/11.000.900.900.800.1330.067
    1/3/1/11.001.001.000.800.7000.333
    1/1/3/11.001.001.001.000.9500.067
    1/1/1/31.001.001.000.601.000.067
    3/3/1/11.000.500.800.800.000.333
    3/1/3/11.001.000.900.850.600.333
    3/1/1/31.000.750.950.750.5330.067
    1/3/3/11.001.001.001.000.700.033
    1/3/1/31.001.001.001.000.800.00
    1/1/3/31.001.001.001.000.600.00
    3/3/3/11.001.000.901.000.3330.20
    3/3/1/31.000.451.000.750.1330.033
    3/1/3/31.001.000.950.850.1670.067
    1/3/3/31.001.001.001.000.700.067
     | Show Table
    DownLoad: CSV

    From TABLE 1 we can know that for all 90 Möhring instances, there are 43 instances with the percentage values equal to 1, which means that the proposed MBSMAEA-RIPSP can solve these instances easily. And, there are 25 instances with the percentage values various from 0.5 to 0.95 and 19 instances with the values below 0.5, which means for these instances the MBSMAEA-RIPSP can find the optimal solutions with certain probabilities. However, the rest three instances are relatively difficult that the proposed MBSMAEA-RIPSP cannot find optima in all replications. In one word, the MBSMAEA-RIPSP is able to solve most of the Möhring instances.

    In order to further verify the performance of MBSMAEA-RIPSP, the comparison between MBSMAEA-RIPSP and the GA designed by Shadrokh etal. in [14] is conducted. According to [14], the numbers of generation are recorded for both two algorithms once the optimal solution is found for each instance. The parameter settings of MBSMAEA-RIPSP are identical to the aforementioned experiment. The results are shown in TABLE 2, in which the bold numbers represent the smaller values of the number of generations and MBS represents the MBSMAEA-RIPSP for convenience. From TABLE 2 we can know that there are 40 instances that the proposed MBSMAEA-RIPSP finds the optimal solutions using less generations, which means it is more effective; 24 instances that two algorithms have the same values of generations, and 26 instances the MBSMAEA-RIPSP needs more generations than GA to find the optimal solutions. Overall, for most Möhring instances the proposed MBSMAEA-RIPSP performs better than GA.

    Table 2. The Comparison of Numbers of Generation to Reach to the Optimal Solutions between MBSMAEA-RIPSP and GA for Möhring Test Sets.
    C1/C2/C3/C4θ=1.0θ=1.1θ=1.2θ=1.3θ=1.4θ=1.5
    MBSGAMBSGAMBSGAMBSGAMBSGAMBSGA
    1/1/1/111121116621141
    3/1/1/111611212720271
    1/3/1/1121331411243131
    1/1/3/11111111112343
    1/1/1/31111132112145
    3/3/1/11112812125171
    3/1/3/11111121181189
    3/1/1/31212162198102
    1/3/3/11111182111523
    1/3/1/31112111186201
    1/1/3/313131212537121
    3/3/3/111121212914131
    3/3/1/31141113288221
    3/1/3/3121211121311845
    1/3/3/3121213311934923
     | Show Table
    DownLoad: CSV

    6.2. Experiments on J10, J14, and J20 instances

    For J10, J14, and J20 test sets, we generated and tested 20 instances for each group, and the due date T is still set to T=θ×EFT, where θ{1.0, 1.1, 1.2, 1.3, 1.4, 1.5}. Therefore, totally 3×20×6=360 problems were solved. The self-learning probability Psel is set to 0.5 and the other parameter settings of MBSMAEA-RIPSP for J10, J14 and J20 are shown in TABLE 3, which are selected empirically. The stopping criteria is either the optimal solution is found or the predetermined maximum number of generation is reached. The percentages of finding the optimal solutions for each group with different θ values "Opt.%", the percentage of the average deviation "Dev.%", and the number of fitness evaluations "Eva." are shown in TABLE 4. The comparisons between MBSMAEA-RIPSP and GA are shown in TABLE 5, in which the bold numbers mean the better performance in the specific measurement and MBS represents the MBSMAEA-RIPSP for convenience. From TABLE 5 we can see that for all three test sets, MBSMAEA-RIPSP has larger values of "Opt.%" than GA, which means the proposed method has better performance. In terms of "Dev.%", the MBSMAEA-RIPSP outperforms GA only in J20 test set and for J10 and J14, GA has smaller values. Overall, the MBSMAEA-RIPSP has better performance than GA.

    Table 3. Parameter Settings for J10, J14 and J20 Test Sets.
    Test Set#AgentMaxGenExcuteNumSelfLTimePcroPmutPcom
    J1020×201010120.950.850.9
    J1420×20108120.950.851.0
    J2020×19108120.950.851.0
     | Show Table
    DownLoad: CSV
    Table 4. Experimental Results of MBSMAEA-RIPSP for J10, J14 and J20 Test Sets.
    θJ10J14J20
    Opt.%Dev.%Eva.Opt.%Dev.%Eva.Opt.%Dev.%Eva.
    1.040.06.8896698876.50.7970371932.54.91267135
    1.141.03.4006722563.01.0457498135.05.43357327
    1.255.02.5922582143.1252.5851768333.04.92587273
    1.351.52.4822617049.3752.2975736943.02.61737188
    1.456.02.8036606547.51.9321677143.02.00797279
    1.568.51.8743449655.01.8272746543.01.97287154
     | Show Table
    DownLoad: CSV
    Table 5. Comparisons between MBSMAEA-RIPSP and GA for J10, J14 and J20 Test Sets.
    Test SetOpt.%Dev.%
    MBSGAMBSGA
    J1052.0048.203.34040.23
    J1455.7540.001.74740.32
    J2038.2533.333.64454.68
     | Show Table
    DownLoad: CSV

    7. Conclusion

    In this paper, a new MBS representation is first designed to deal with PSPs, and an MAEA based on MBS representation is proposed to solve the single-mode RIPSPs. The decoding method guarantees to generate feasible schedules based on the MBS representation. Therefore both the newly designed representation and the decoding method can be applied to other EAs that designed to solve PSPs.

    In experiments, 450 test instances are used to test the performance of the proposed MBSMAEA-RIPSP. TABLE Ⅰ and indicate that the proposed method can solve almost all of the Möhring instances and has better performance than GA in terms of the efficiency for finding the optimal solutions. Moreover, the generated test sets J10, J14 and J20 are employed to further verify the ability of MBSMAEA-RIPSP and the experimental results indicate the outperformance of the proposed method.

    RIPSP is just one general issue of PSPs and the newly designed MBS representation and the corresponding decoding method can be extended to other PSPs. Therefore, the extending of MBS representation and the decoding method for solving other variations of PSPs will be our future work.


    Acknowledgments

    This work is partially supported by the Outstanding Young Scholar Program of National Natural Science Foundation of China (NSFC) under Grant 61522311, the General Program of NSFC under Grant 61773300, the Overseas, Hong Kong & Macao Scholars Collaborated Research Program of NSFC under Grant 61528205, and the Key Program of Fundamental Research Project of Natural Science of Shaanxi Province, China under Grant 2017JZ017.


    [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.
  • This article has been cited by:

    1. Patrick Gerhards, The multi-mode resource investment problem: a benchmark library and a computational study of lower and upper bounds, 2020, 42, 0171-6468, 901, 10.1007/s00291-020-00595-9
  • 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(4220) PDF downloads(514) Cited by(1)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog