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
[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.
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 MBS
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 MBS
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 P
(1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
where objective (1) is to minimize the total cost of a project. Constraints (2) is the precedence relation between each pair of activities
In a RIPSP, there are
struct B
{
(x
width: width of block B
height: height of block B
}
where B
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, (Box
Move rule 0: the coordinates of initial positions (B
Move rule 1: the coordinates of initial positions (B
Move rule 2: the coordinates of initial positions (B
Move rule 3: the coordinates of initial position (B
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.
(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 B
Theorem 3.2. The size of search space
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
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.
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
struct e
{
x
x
y: Y-coordinate of the bottom edge.
}
struct e
{
x: X-coordinate of the edge;
y
y
}
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.
Definition 4.1. Let a
(9) |
(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 CoverRightX
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
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
In Algorithm 1, when all blocks have been placed in the first quadrant, Box
Algorithm 1 Transforming an MBS to a schedule |
Input: MBS: An MBS in solution space F; |
Output: |
1: |
2: |
3: |
4: Add the top edge of |
5: Add the right edge of |
6: for |
7: if |
8: |
9: Calculate |
10: |
11: else if |
12: |
13: Calculate |
14: |
15: else if |
16: if |
17: |
18: Similar to case 0; |
19: else /*Do not violate precedence constraints, repeat downward and leftward movement.*/ |
20: |
21: |
22: while ( |
23: Calculate |
24: |
25: Calculate |
26: Calculate |
27: if ( |
28: |
29: |
30: else |
31: |
32: |
33: end if |
34: end while |
35: end if |
36: else if |
37: |
38: |
39: while ( |
40: Calculate |
41: |
42: Calculate |
43: |
44: if |
45: break; |
46: else |
47: Calculate |
48: end if |
49: if( |
50: |
51: |
52: else |
53: |
54: |
55: end if |
56: end while |
57: end if |
58: Update |
59: Add the top edge of |
60: Add the right edge of |
61: end for |
62: Calculate available resource capacity |
63: Calculate |
In the proposed MBS
Taking into account the makespan and available resource capacity R
(11) |
In FIGURE 5, parts one to four stand for the four designed move rules. The values of (Box
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 MBS
With the intrinsic properties of the MBS and RIPSPs in mind, the agent in MBS
Definition 5.1. An agent, labeled as
(12) |
For each agent
As described in [15,17,27], all agents in MBS
(13) |
where
(14) |
In MBS
In MBS
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
Algorithm 2 Mutation operator for move mode list |
Input: |
Output: |
1: if makespan |
2: Choose an activity |
3: Find |
4: for |
5: if |
6: Set the move mode of activity |
7: else if |
8: Set the move mode of activity |
9: end if |
10: end for |
11: else |
12: Choose an activity |
13: Find |
14: for |
15: if |
16: Set the move mode of activity |
17: end if |
18: end for |
19: end if |
20: Transform the agent |
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
For an agent
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
Algorithm 3 Self-learning operator |
Input: |
|
Output: Agent |
1: for |
2: |
3: if |
4: |
5: end if |
6: end for |
In MBS
Algorithm 4 MBS |
Input: |
|
|
|
|
|
MaxGen: The maximum number of generations; |
Output: The best agent found; |
1: Initialize the agent lattice; |
2: For each agent, calculate |
3: repeat |
4: for |
5: Conduct competition operator on agent |
6: end for |
7: for |
8: Conduct crossover operator on agent |
9: end for |
10: for |
11: Conduct mutation operator on agent |
12: end for |
13: if |
14: Conduct the self-learning operator on the best agent in the current generation; |
15: end if |
16: until (reach the stopping criteria) |
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 MBS
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
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
1/1/1/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.067 | 0.033 |
3/1/1/1 | 1.00 | 0.90 | 0.90 | 0.80 | 0.133 | 0.067 |
1/3/1/1 | 1.00 | 1.00 | 1.00 | 0.80 | 0.700 | 0.333 |
1/1/3/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.950 | 0.067 |
1/1/1/3 | 1.00 | 1.00 | 1.00 | 0.60 | 1.00 | 0.067 |
3/3/1/1 | 1.00 | 0.50 | 0.80 | 0.80 | 0.00 | 0.333 |
3/1/3/1 | 1.00 | 1.00 | 0.90 | 0.85 | 0.60 | 0.333 |
3/1/1/3 | 1.00 | 0.75 | 0.95 | 0.75 | 0.533 | 0.067 |
1/3/3/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.70 | 0.033 |
1/3/1/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.80 | 0.00 |
1/1/3/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.60 | 0.00 |
3/3/3/1 | 1.00 | 1.00 | 0.90 | 1.00 | 0.333 | 0.20 |
3/3/1/3 | 1.00 | 0.45 | 1.00 | 0.75 | 0.133 | 0.033 |
3/1/3/3 | 1.00 | 1.00 | 0.95 | 0.85 | 0.167 | 0.067 |
1/3/3/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.70 | 0.067 |
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 MBS
In order to further verify the performance of MBS
MBS | GA | MBS | GA | MBS | GA | MBS | GA | MBS | GA | MBS | GA | |
1/1/1/1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 6 | 6 | 21 | 14 | 1 |
3/1/1/1 | 1 | 1 | 6 | 1 | 1 | 2 | 1 | 2 | 7 | 20 | 27 | 1 |
1/3/1/1 | 1 | 2 | 1 | 33 | 1 | 4 | 1 | 1 | 2 | 43 | 13 | 1 |
1/1/3/1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 23 | 4 | 3 |
1/1/1/3 | 1 | 1 | 1 | 1 | 1 | 3 | 2 | 1 | 12 | 1 | 4 | 5 |
3/3/1/1 | 1 | 1 | 1 | 28 | 1 | 2 | 1 | 2 | 5 | 1 | 7 | 1 |
3/1/3/1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 8 | 11 | 8 | 9 |
3/1/1/3 | 1 | 2 | 1 | 2 | 1 | 6 | 2 | 1 | 9 | 8 | 10 | 2 |
1/3/3/1 | 1 | 1 | 1 | 1 | 1 | 8 | 2 | 1 | 1 | 15 | 2 | 3 |
1/3/1/3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 8 | 6 | 20 | 1 |
1/1/3/3 | 1 | 3 | 1 | 3 | 1 | 2 | 1 | 2 | 5 | 37 | 12 | 1 |
3/3/3/1 | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | 9 | 14 | 13 | 1 |
3/3/1/3 | 1 | 1 | 4 | 1 | 1 | 1 | 3 | 2 | 8 | 8 | 22 | 1 |
3/1/3/3 | 1 | 2 | 1 | 21 | 1 | 1 | 2 | 1 | 31 | 18 | 4 | 5 |
1/3/3/3 | 1 | 2 | 1 | 2 | 1 | 3 | 3 | 1 | 19 | 3 | 49 | 23 |
For J10, J14, and J20 test sets, we generated and tested 20 instances for each group, and the due date
Test Set | #Agent | MaxGen | ExcuteNum | ||||
J10 | 10 | 10 | 12 | 0.95 | 0.85 | 0.9 | |
J14 | 10 | 8 | 12 | 0.95 | 0.85 | 1.0 | |
J20 | 10 | 8 | 12 | 0.95 | 0.85 | 1.0 |
J10 | J14 | J20 | |||||||
Opt.% | Dev.% | Eva. | Opt.% | Dev.% | Eva. | Opt.% | Dev.% | Eva. | |
1.0 | 40.0 | 6.8896 | 6988 | 76.5 | 0.7970 | 3719 | 32.5 | 4.9126 | 7135 |
1.1 | 41.0 | 3.4006 | 7225 | 63.0 | 1.0457 | 4981 | 35.0 | 5.4335 | 7327 |
1.2 | 55.0 | 2.5922 | 5821 | 43.125 | 2.5851 | 7683 | 33.0 | 4.9258 | 7273 |
1.3 | 51.5 | 2.4822 | 6170 | 49.375 | 2.2975 | 7369 | 43.0 | 2.6173 | 7188 |
1.4 | 56.0 | 2.8036 | 6065 | 47.5 | 1.9321 | 6771 | 43.0 | 2.0079 | 7279 |
1.5 | 68.5 | 1.8743 | 4496 | 55.0 | 1.8272 | 7465 | 43.0 | 1.9728 | 7154 |
Test Set | Opt.% | Dev.% | ||
MBS | GA | MBS | GA | |
J10 | 52.00 | 48.20 | 3.3404 | 0.23 |
J14 | 55.75 | 40.00 | 1.7474 | 0.32 |
J20 | 38.25 | 33.33 | 3.6445 | 4.68 |
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 MBS
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.
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. |
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 |
1/1/1/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.067 | 0.033 |
3/1/1/1 | 1.00 | 0.90 | 0.90 | 0.80 | 0.133 | 0.067 |
1/3/1/1 | 1.00 | 1.00 | 1.00 | 0.80 | 0.700 | 0.333 |
1/1/3/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.950 | 0.067 |
1/1/1/3 | 1.00 | 1.00 | 1.00 | 0.60 | 1.00 | 0.067 |
3/3/1/1 | 1.00 | 0.50 | 0.80 | 0.80 | 0.00 | 0.333 |
3/1/3/1 | 1.00 | 1.00 | 0.90 | 0.85 | 0.60 | 0.333 |
3/1/1/3 | 1.00 | 0.75 | 0.95 | 0.75 | 0.533 | 0.067 |
1/3/3/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.70 | 0.033 |
1/3/1/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.80 | 0.00 |
1/1/3/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.60 | 0.00 |
3/3/3/1 | 1.00 | 1.00 | 0.90 | 1.00 | 0.333 | 0.20 |
3/3/1/3 | 1.00 | 0.45 | 1.00 | 0.75 | 0.133 | 0.033 |
3/1/3/3 | 1.00 | 1.00 | 0.95 | 0.85 | 0.167 | 0.067 |
1/3/3/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.70 | 0.067 |
MBS | GA | MBS | GA | MBS | GA | MBS | GA | MBS | GA | MBS | GA | |
1/1/1/1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 6 | 6 | 21 | 14 | 1 |
3/1/1/1 | 1 | 1 | 6 | 1 | 1 | 2 | 1 | 2 | 7 | 20 | 27 | 1 |
1/3/1/1 | 1 | 2 | 1 | 33 | 1 | 4 | 1 | 1 | 2 | 43 | 13 | 1 |
1/1/3/1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 23 | 4 | 3 |
1/1/1/3 | 1 | 1 | 1 | 1 | 1 | 3 | 2 | 1 | 12 | 1 | 4 | 5 |
3/3/1/1 | 1 | 1 | 1 | 28 | 1 | 2 | 1 | 2 | 5 | 1 | 7 | 1 |
3/1/3/1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 8 | 11 | 8 | 9 |
3/1/1/3 | 1 | 2 | 1 | 2 | 1 | 6 | 2 | 1 | 9 | 8 | 10 | 2 |
1/3/3/1 | 1 | 1 | 1 | 1 | 1 | 8 | 2 | 1 | 1 | 15 | 2 | 3 |
1/3/1/3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 8 | 6 | 20 | 1 |
1/1/3/3 | 1 | 3 | 1 | 3 | 1 | 2 | 1 | 2 | 5 | 37 | 12 | 1 |
3/3/3/1 | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | 9 | 14 | 13 | 1 |
3/3/1/3 | 1 | 1 | 4 | 1 | 1 | 1 | 3 | 2 | 8 | 8 | 22 | 1 |
3/1/3/3 | 1 | 2 | 1 | 21 | 1 | 1 | 2 | 1 | 31 | 18 | 4 | 5 |
1/3/3/3 | 1 | 2 | 1 | 2 | 1 | 3 | 3 | 1 | 19 | 3 | 49 | 23 |
Test Set | #Agent | MaxGen | ExcuteNum | ||||
J10 | 10 | 10 | 12 | 0.95 | 0.85 | 0.9 | |
J14 | 10 | 8 | 12 | 0.95 | 0.85 | 1.0 | |
J20 | 10 | 8 | 12 | 0.95 | 0.85 | 1.0 |
J10 | J14 | J20 | |||||||
Opt.% | Dev.% | Eva. | Opt.% | Dev.% | Eva. | Opt.% | Dev.% | Eva. | |
1.0 | 40.0 | 6.8896 | 6988 | 76.5 | 0.7970 | 3719 | 32.5 | 4.9126 | 7135 |
1.1 | 41.0 | 3.4006 | 7225 | 63.0 | 1.0457 | 4981 | 35.0 | 5.4335 | 7327 |
1.2 | 55.0 | 2.5922 | 5821 | 43.125 | 2.5851 | 7683 | 33.0 | 4.9258 | 7273 |
1.3 | 51.5 | 2.4822 | 6170 | 49.375 | 2.2975 | 7369 | 43.0 | 2.6173 | 7188 |
1.4 | 56.0 | 2.8036 | 6065 | 47.5 | 1.9321 | 6771 | 43.0 | 2.0079 | 7279 |
1.5 | 68.5 | 1.8743 | 4496 | 55.0 | 1.8272 | 7465 | 43.0 | 1.9728 | 7154 |
Test Set | Opt.% | Dev.% | ||
MBS | GA | MBS | GA | |
J10 | 52.00 | 48.20 | 3.3404 | 0.23 |
J14 | 55.75 | 40.00 | 1.7474 | 0.32 |
J20 | 38.25 | 33.33 | 3.6445 | 4.68 |
1/1/1/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.067 | 0.033 |
3/1/1/1 | 1.00 | 0.90 | 0.90 | 0.80 | 0.133 | 0.067 |
1/3/1/1 | 1.00 | 1.00 | 1.00 | 0.80 | 0.700 | 0.333 |
1/1/3/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.950 | 0.067 |
1/1/1/3 | 1.00 | 1.00 | 1.00 | 0.60 | 1.00 | 0.067 |
3/3/1/1 | 1.00 | 0.50 | 0.80 | 0.80 | 0.00 | 0.333 |
3/1/3/1 | 1.00 | 1.00 | 0.90 | 0.85 | 0.60 | 0.333 |
3/1/1/3 | 1.00 | 0.75 | 0.95 | 0.75 | 0.533 | 0.067 |
1/3/3/1 | 1.00 | 1.00 | 1.00 | 1.00 | 0.70 | 0.033 |
1/3/1/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.80 | 0.00 |
1/1/3/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.60 | 0.00 |
3/3/3/1 | 1.00 | 1.00 | 0.90 | 1.00 | 0.333 | 0.20 |
3/3/1/3 | 1.00 | 0.45 | 1.00 | 0.75 | 0.133 | 0.033 |
3/1/3/3 | 1.00 | 1.00 | 0.95 | 0.85 | 0.167 | 0.067 |
1/3/3/3 | 1.00 | 1.00 | 1.00 | 1.00 | 0.70 | 0.067 |
MBS | GA | MBS | GA | MBS | GA | MBS | GA | MBS | GA | MBS | GA | |
1/1/1/1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 6 | 6 | 21 | 14 | 1 |
3/1/1/1 | 1 | 1 | 6 | 1 | 1 | 2 | 1 | 2 | 7 | 20 | 27 | 1 |
1/3/1/1 | 1 | 2 | 1 | 33 | 1 | 4 | 1 | 1 | 2 | 43 | 13 | 1 |
1/1/3/1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 23 | 4 | 3 |
1/1/1/3 | 1 | 1 | 1 | 1 | 1 | 3 | 2 | 1 | 12 | 1 | 4 | 5 |
3/3/1/1 | 1 | 1 | 1 | 28 | 1 | 2 | 1 | 2 | 5 | 1 | 7 | 1 |
3/1/3/1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 8 | 11 | 8 | 9 |
3/1/1/3 | 1 | 2 | 1 | 2 | 1 | 6 | 2 | 1 | 9 | 8 | 10 | 2 |
1/3/3/1 | 1 | 1 | 1 | 1 | 1 | 8 | 2 | 1 | 1 | 15 | 2 | 3 |
1/3/1/3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 8 | 6 | 20 | 1 |
1/1/3/3 | 1 | 3 | 1 | 3 | 1 | 2 | 1 | 2 | 5 | 37 | 12 | 1 |
3/3/3/1 | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | 9 | 14 | 13 | 1 |
3/3/1/3 | 1 | 1 | 4 | 1 | 1 | 1 | 3 | 2 | 8 | 8 | 22 | 1 |
3/1/3/3 | 1 | 2 | 1 | 21 | 1 | 1 | 2 | 1 | 31 | 18 | 4 | 5 |
1/3/3/3 | 1 | 2 | 1 | 2 | 1 | 3 | 3 | 1 | 19 | 3 | 49 | 23 |
Test Set | #Agent | MaxGen | ExcuteNum | ||||
J10 | 10 | 10 | 12 | 0.95 | 0.85 | 0.9 | |
J14 | 10 | 8 | 12 | 0.95 | 0.85 | 1.0 | |
J20 | 10 | 8 | 12 | 0.95 | 0.85 | 1.0 |
J10 | J14 | J20 | |||||||
Opt.% | Dev.% | Eva. | Opt.% | Dev.% | Eva. | Opt.% | Dev.% | Eva. | |
1.0 | 40.0 | 6.8896 | 6988 | 76.5 | 0.7970 | 3719 | 32.5 | 4.9126 | 7135 |
1.1 | 41.0 | 3.4006 | 7225 | 63.0 | 1.0457 | 4981 | 35.0 | 5.4335 | 7327 |
1.2 | 55.0 | 2.5922 | 5821 | 43.125 | 2.5851 | 7683 | 33.0 | 4.9258 | 7273 |
1.3 | 51.5 | 2.4822 | 6170 | 49.375 | 2.2975 | 7369 | 43.0 | 2.6173 | 7188 |
1.4 | 56.0 | 2.8036 | 6065 | 47.5 | 1.9321 | 6771 | 43.0 | 2.0079 | 7279 |
1.5 | 68.5 | 1.8743 | 4496 | 55.0 | 1.8272 | 7465 | 43.0 | 1.9728 | 7154 |
Test Set | Opt.% | Dev.% | ||
MBS | GA | MBS | GA | |
J10 | 52.00 | 48.20 | 3.3404 | 0.23 |
J14 | 55.75 | 40.00 | 1.7474 | 0.32 |
J20 | 38.25 | 33.33 | 3.6445 | 4.68 |