The Resource-Constrained Project Scheduling Problem (RCPSP) is a NP-hard problem in information engineering. The activities of a project have to be scheduled for satisfying all the precedence and resource constraints. We presented a heuristic algorithm (EDAS) to deal with this problem which employed an estimation of distribution algorithm (known as EDA) and improved the local search capacity with a simplex search. In this algorithm, the EDA firstly searched the solution space and generated activity lists to provide the initial population; then, the EDA selected the sample solutions to build a probability distribution model. The new individual was generated by sampling this model. The simplex search was used to enhance the local search capacity of the EDA. Compared with state-of-the-art algorithms available in the literature, we showed the effectiveness of this approach empirically on the standard benchmark problems of size J60 and J120 from PSPLIB.
PDF Abstract XML References Citation
How to cite this article
The Resource-Constrained Project Scheduling Problem (RCPSP) (Hartmann and Briskorn 2010) is a classical NP-hard problem in scheduling. The problem is widely applicable in project management, construction engineering, software development and production scheduling. The objective is to schedule the activities of a project so as to minimize the project make-span, subject to precedence and resource constraints. This problem has been well researched for over four decades. Previous studies have proposed several meta-heuristics which have been successfully applied to solve large scale problems with better robustness and higher calculating speed. Chen (2010) developed a mixed binary integer programming model to optimally solve this kind of NP-hard problems. Xie (2009) proposed a serial scheduling and parallel scheduling algorithm which firstly formulated the problem to a nonlinearity programming problem and then transformed it into an integer programming problem based on the piece linear rate-distortion model. Ziarati et al. (2011) investigated the application of bee algorithms RCPSP. In the study of Chen (2011), the justification technique was combined with PSO as the proposed Justification Particle Swarm Optimization (JPSO) in solving RCPSP. Zhu et al. (2010) presented an effective Forward and Reverse Schedule Generation (FRSG) method with a novel complete local search to find the solution with the best objective value. Benedict and Vasudevan (2008) proposed an Improved Tabu Search Algorithm for the project scheduling problems. In our previous studies, we proposed an efficient algorithm ACOSS, combined a local search strategy, Ant Colony Optimization (ACO) and a Scatter Search (SS) in an iterative process for solving RCPSP (Chen et al., 2010).
Different from the previous studies, we aim at showing the feasibility and effectiveness of the estimation of distribution algorithm for the RCPSP. Estimation of Distribution Algorithms (EDA) (Larranaga and Lozano, 2002) are evolutionary algorithms based on estimation of and sampling from probabilistic models, have been successfully applied to the combinatorial optimization problems (Campelo, Guimaraes et al., 2009; Eddaly et al., 2009; Jarboui et al., 2009; Naeem and Lee, 2009; Luo et al., 2010; Meiguins et al., 2010; Rodrigues and Yamashita, 2010; Wang et al., 2010c; Xu et al., 2010; Zhong et al., 2010; Zhang and Li, 2011). Campelo et al. (2009) introduced an approach for the design of electromagnetic devices based on the use of estimation of distribution algorithms coupled with approximation-based local search around the most promising solutions. Eddaly, Jarboui et al. (2009) propose an Estimation of Distribution Algorithm for solving a flow-shop scheduling problem with buffer constraints. Rodrigues and Yamashita (2010) used the EDA algorithm for minimizing resource availability costs in project scheduling. In the traditional evolutionary computation, new candidate solutions are often generated by combining and modifying existing solutions in a stochastic way. The underlying probability distribution of new solutions over the space of possible solutions is usually not explicitly specified. In the EDA, the representation of the population is replaced with a probability distribution over the choices available at each position in the vector that represents a population member. So a population may be approximated with a probability distribution and new candidate solutions can be obtained by sampling this distribution. This algorithm may have several advantages, such as, avoiding premature convergence and being a more compact representation.
But, as a global search algorithm, EDA does not perform well for the large-scale problems with a slow convergence speed. Its known that an effective algorithm not only can explore the solution space sufficiently and also can find the elites by local search. After the analysis of the RCPSP problems, this study improves the local search capacity of the EDAS algorithm with a simplex search. The simplex method (Klee and Minty et al., 1970) is a popular algorithm for numerically solving linear programming problems. It can be viewed as a family of combinatorial local search algorithms on the boundary of a solution space (Cosio et al., 2010; Li et al., 2010; Osgood et al., 2010; Song et al., 2010; Wu et al., 2010; Xu et al., 2010). The search moves from one point of the solution space to a neighboring one with a better objective value, according to a chosen rule. Today, the simplex method is still widely used and remains important in practice, particularly in combinatorial optimization and local search.
In this study, we will describe how to integrate the EDA and simplex approach. Our empirical test showed that our hybrid approach performed well on the standard benchmark problems of size J60 and J120 from PSPLIB.
THE RCPSP MODEL
The Resource Constrained Project Scheduling Problem (RCPSP) is stated as follows. For the project A, n+2 activities I = 0,1,2,...,n,n+1 and r renewable resources are given. A constant amount of Rk units of resource k is available in each time unit. The duration of an activity i is given by di. During this time period, a constant amount of rik units of resource k is occupied by the activity i. The dummy activities 0 and n+1 represent the beginning and the end of the project, where d0 = dn+1 = 0 and r0k = rn+1k. Parameter di, rik and Rk are assumed to be non-negative integer values. The activities are interrelated by two types of constraints:(1) precedence constraints prevent activity i from being started before all its predecessor activities Pi have been completed and (2) the sum of the resource requirements for resource k in anytime period cannot exceed Rk. The optimized objective of the RCPSP is to find precedence and resource feasible completion times for all activities such that the make-span of the project is minimized.
Let the completion time of activity i be denoted as Di, then the completion times of schedule S are denoted as D1, D2,..., Dn. The conceptual model of the RCPSP can be described as follows:
The objective function given by Eq. 1 minimizes the make-span of the schedule. Equation 2 enforces the precedence constraints between activities, while Eq. 3 enforces the resource limitation constraint, where A(t) = i|Di-di≤t<Di, i.e., the set of activities being processed (active) at time t. Finally, Eq. 4 describes the constraint of the decision variables.
THE EDAS ALGORITHM
The main flowchart of EDAS algorithm: In this study, we integrate the estimation of distribution algorithms and the simplex method to construct the Estimation of Distribution Algorithms with Simplex method (EDAS) for solving the RCPSP problems. Figure 1 shows the main flowchart of the EDAS. In the initial stage, the parameters and population is initialized. The tournament selection is employed to obtain the selected solutions. Then the EDA explicitly extracts global statistical information from the selected solutions by (often called parents) and build a posterior probability distribution model of promising solutions, based on Gaussian model with diagonal covariance matrix (GM/DCM) (Larranaga and Lozano, 2002; Wang et al., 2010a,b). New solutions are sampled from the model thus built and fully or in part replace the old population.
|Fig. 1:||Flowchart of EDAS|
In addition, the simplex method is used to search local optima in each iteration and the limitation of EDA such as poor local search ability and premature is largely enhanced. The SM searches the local neighborhood of the current optimal feasible solution to improve the velocity of convergence.
The representation and decoding procedure for the EDAS algorithm: The representation and decoding procedure for RCPSP plays an important role in algorithm performance. We herein employ the random key representation (Shi et al., 2010), a solution was represented by a random sequence and denote sn as the number of activities in the sub-problem S:
In random key representation, schedule generation schemes (SGS) are the core decoding procedures for the RCPSP (Kolisch and Hartmann, 1999). Two different SGSs are available in the literature: (1) the serial SGS that performs activity-incrementation and (2) the parallel SGS that performs time-incrementation. Considering the advantages and disadvantages of both schemes, we use a random real number, rSGS(0≤rSGS≤1) to select the SGS with which to construct the schedule, as defined by:
The sample solution selection method for the EDAS algorithm: It is important to select the sample solution for applying the EDA. We employ the tournament selection as a countermeasure. The tournament selection randomly selects two individual in a population and the individual with better fitness will be the sample solution. Repeat the process until the number of the sample solutions meets the requirements. In this paper, the number of the sample solutions is only half of that of the population. We denote NP as the number of the population, so the number of the sample solutions is NP/2.
The probability distribution model for the EDAS algorithm: This step is to build a probability distribution model. Since the distribution of categorical variables is Gauss distribution or similar Gauss distribution in the realistic situation, so we employ Gaussian model with diagonal covariance matrix (GM/DCM) to build a probability distribution model. GM/DCM considers the correlation between random variables and uses every element of the matrix to represent the covariance among different components of a random vector. This method describes the correlations among the different design variables more reasonably and these correlations are applied to guide the further search.
Each design variable obeys the normal distribution, so the joint probability density function of the sample solution (n dimensions random vector = (x1, x2, ,..., xn) is:
We denote C as covariance matrix of n dimensions random vector, |C| as the determinant of covariance matrix and C-1 as the inverse matrices of C. We can estimate the mean μ and covariance matrix C by Maximum Likelihood Estimate (MLE) (Laurence and Chromy, 2010; Yin et al., 2011):
The mean μ and covariance matrix C need to be re-calculated in every iteration step.
The sampling method for the EDAS algorithm: For generating the new individual, the EDA here is implemented for sampling the joint probability density function which is employed for describing the probability distribution model. As for each of the random variables, sampling method is used to generate random numbers. The vector formed by these random numbers, will be a new individual. Repeat this procedure until the whole new population is completed. In the GM/DCM, each dimension of the design variables obeys the normal distributions, xj∼N(μj, σj). This paper employs Box-Muller formula as the sampling method:
In Eq. 9, r1 and r2 are random numbers between 0 and 1 while random number rnorm obeys the normal distribution, N(0,1). And based on Eq. 10, the sample point xj is determined which obeys the normal distribution, xj∼N(μj,σj). By this way, the complete solution is obtained.
The local search strategy using simplex search: The simplex search is very suitable for nonlinear function optimization without any gradient information and coding operation. The process is composed of three basic steps are reflection, compression and expansion. The iterative processes are follows:
|Step 1:||Initialize the compressibility λ, the expansion coefficient β and the tolerance ε|
|Step 2:||Generate randomly n+1 points, x0, x1,..., xn to form a simplex|
|Step 3:||Calculate the values of function f(xi), i = 0,1,...,n to get the best point xh, the worst point xl. We denote the fitness of them as follow:|
|Step 4:||Calculate the centre point xc of x0,..., xh+1 except the point xh,|
and the reflection point xr, xr = 2xc-xh
|Step 5:||If fr = f(xr)≥fh, compress the pre-processed data, xs = xh+λ(xr-zh). Then calculate fs = f(xs) and go to Step 7 ; if fr<fh, go to Step 6|
|Step 6:||Carry out the expansion, xe = xh+μ(xr-xh) and calculate fe = f(xe). If fe≤fr, implement the following assignments xs = xe and fs = fe; else xs = xr and fs= fr|
|Step 7:||If fs<fh, substitute xs for fh and that fs for fh. Put the new point xs with the other n points to form a new simplex. Retrieve the best point xh and the worst point xl, then go to Step 4 ; if fs≥fh, go to Step 8|
|Step 8:||If fh-fl<ε.|fl|, end the process and set x* = xl and f* = fl; else shorten the step size and follow the formula xi = (xi+xl)/2, i = 0,1,...,n, then go to Step 3, continue the calculation|
We applied the EDAS to the standard instance sets J60 (480 instances each with 60 activities) and J120 (600 instances each with 120 activities) (Kolisch and Sprecher, 1997). These sets are available in the well known PSPLIB along with the optimum, or best known values that have been obtained by various authors over the years. In J60 and J120 the optimal make-spans for some instances are not known and only upper bounds (current best solutions) and lower bounds are provided. For a fair machine-independent comparison, we limited the number of generated and evaluated schedules in EDAS to 1000, 5000 and 50,000, respectively. EDAS was implemented in JAVA 1.6 and all the experiments were performed on a PC with 1.86 GHz CPU and 2 GB RAM running the Windows XP operating system.
In the preliminary experiments, we employed a trial-and-error strategy to obtain suitable control parameter values for each algorithm. We settled on the following control parameters: the number of the population, NP = 100 and the number of sub-problems, S = 4.
Table 1 and 2 gave the performances of EDAS and several RCPSP heuristics from the literature with 1000, 5000 and 50,000 evaluated schedules. This study compared EDAS with GAPS (Mendes et al., 2009), GA-DBH (Debels and Vanhoucke, 2007), GA-hybrid-FBI (Valls et al., 2003) and GA-FBI (Valls et al., 2005).
Table 1 listed the lower bound results for instances with 60 activities. The EDAS ranked 4th for 1000 schedules and both 2nd for 5000 and 50,000 schedules, respectively. In this situation, the performance of the GA-FBI method is the worst of the five kinds of algorithms. The GA-DBH showed better results than the EDAS which meant that the GA-DBH is very suitable for project scheduling with 60 activities.
|Table 1:||Average deviation (%) from critical path lower bound-ProGen set J60|
|Table 2:||Average deviation (%) from critical path lower bound-ProGen set J120|
Table 2 listed the results for J120, where the EDAS algorithm ranked 3rd for 1000 schedules. As for 5000 schedules, the EDAS ranked 1st which was equal to the GA-DBH algorithm. The EDAS ranked 1st for 50,000 schedules showed that EDAS can produce better solutions for the large-scale problems J60 and J120. That is to say, the EDAS algorithm can solve the large-scale RCPSP problems effectively.
The reason for the improved performance is that EDAS combines the advantages of the GM/DCM and the simplex local search method. The GM/DCM describes the correlations among the different design variables more reasonably and the correlations are applied to guide the further search. The simplex method is used to search local optima in each iteration to fill the gaps of the EDA such as poor local search ability and the lower velocity of convergence.
In this study, we proposed a heuristic algorithm combining the Estimation of Distribution Algorithm (EDA) and the simplex local search strategy to solve resource-constrained project scheduling. The computational results of the EDAS algorithm were compared with the state-of-the-art heuristics on the standard instance sets and from the PSPLIB. The experimental results indicated that, EDAS performed well compared with other heuristic algorithms for the large-scale RCPSP problems. This study also showed that the EDAS is a promising method for solving the RCPSP. Further studies will focus on enhancing the applicability and efficiency of the proposed EDAS algorithm for various complex real-world scheduling problems.
This work was supported by National Natural Science Foundation of P.R. Chaina (Grant No. 50975033, 50975039).
- Cosio, F.A., J.A.M. Flores and M.A.P. Castaneda, 2010. Use of simplex search in active shape models for improved boundary segmentation. Pattern Recognition Lett., 31: 806-817.
- Campelo, F., F.G. Guimaraes, J.A. Ramirez and H. Igarashi, 2009. Hybrid estimation of distribution algorithm using local function approximations. Trans. Magnetics, 45: 1558-1561.
- Chen, R.M., 2011. Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem. Expert Syst. Appl., 38: 7102-7111.
- Chen, W., Y.J. Shi, H.F. Teng, X.P. Lan and L.C. Hu, 2010. An efficient hybrid algorithm for resource-constrained project scheduling. Inform. Sci., 180: 1031-1039.
- Debels, D. and M. Vanhoucke, 2007. A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Operations Res., 55: 457-469.
- Eddaly, M., B. Jarboui, P. Siarry and A. Rebai, 2009. An estimation of distribution algorithm for flowshop scheduling with limited buffers. Nat. Intell. Scheduling Planning Packing Problems, 250: 89-110.
- Hartmann, S. and D. Briskorn, 2010. A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Operational Res., 207: 1-14.
- Jarboui, B., M. Eddaly, P. Siarry and A. Rebai, 2009. An estimation of distribution algorithm for minimizing the makespan in blocking flowshop scheduling problems. Comput. Intell. Flow Shop Job Shop Scheduling, 230: 151-167.
- Kolisch, R. and S. Hartmann, 1999. Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis. In: Project Scheduling: Recent Models, Algorithms and Applications, Weglarz, J., (Ed.). Kluwer Academic Publishers, Berlin, pp: 147-178.
- Kolisch, R. and A. Sprecher, 1997. PSPLIB-A project scheduling problem: OR Software-ORSEP operations research software exchange program. Eur. J. Operational Res., 96: 205-216.
- Laurence, T.A. and B.A. Chromy, 2010. Efficient maximum likelihood estimator fitting of histograms. Nat. Methods, 7: 338-339.
- Li, Z., D. Zheng and H. Hou, 2010. A hybrid particle swarm optimization algorithm based on nonlinear simplex method and tabu search. Adv. Neural Networks, 6063: 126-135.
- Luo, C.Y., B. Lu, M.Y. Chen and C.Y. Zhang, 2010. Hybrid multiobjective particle swarm optimization and estimation of distribution algorithm. Chongqing Daxue Xuebao, 33: 31-36.
- Naeem, M. and D.C. Lee, 2009. Estimation of distribution algorithm for scheduling in uplink multiuser wireless communication system. Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling, April 2- March 30, Nashville, TN, pp: 36-41.
- Osgood, T.J., Y. Huang and K. Young, 2010. Minimisation of alignment error between a camera and a laser range finder using Nelder-Mead simplex direct search. Proceedings of the 4th Intelligent Vehicles Symposium IEEE, June 21-24, San Diego, CA, pp: 779-786.
- Rodrigues, S.B. and D.S. Yamashita, 2010. An exact algorithm for minimizing resource availability costs in project scheduling. Eur. J. Operat. Res., 206: 562-568.
- Shi, Y., F. Qu, W. Chen and B. Li, 2010. An artificial bee colony with random key for resource-constrained project scheduling. Life Syst. Modeling Intell. Comput., 6329: 148-157.
- Song, S., S. Liang, L. Kong and J. Cheng, 2010. Improved particle swarm cooperative optimization algorithm based on chaos and simplex method. Proceedings of the 2nd International Workshop on Education Technology and Computer Science, March 6-7, Wuhan, pp: 45-48.
- Valls, V., F. Ballestin and S. Quintanilla, 2005. Justification and RCPSP: A technique that pays. Eur. J. Oper. Res., 165: 375-386.
- Wang, X.S., Y.H. Cheng and H. Ming-Lin, 2010. Estimation of distribution algorithm based on bacterial foraging and its application in predictive control. Dianzi Xuebao (Acta Electron. Sin.), 38: 333-339.
- Xu, R., J. Zhang, O. Liu and R. Huang, 2010. An estimation of distribution algorithm based portfolio selection approach. Proceedings of the International Conference on Technologies and Applications of Artificial Intelligence, Nov. 18-20, Hsinchu City, pp: 305-313.
- Wang, L., Y. Xu and L. Li, 2010. Parameter identification of chaotic systems by hybrid Nelder-Mead simplex search and differential evolution algorithm. Expert Syst. Appl., 38: 3238-3245.
- Zhang, Y. and X. Li, 2011. Estimation of distribution algorithm for permutation flow shops with total flowtime minimization. Comput. Ind. Eng., 60: 706-718.
- Zhong, J., J. Zhang and Z. Fan, 2010. MP-EDA: A robust estimation of distribution algorithm with multiple probabilistic models for global continuous optimization. Simulated Evol. Learning, 6457: 85-94.
- Zhu, J., X. Li, Q. Hao and W. Shen, 2010. A new approach for resource-constrained multi-project scheduling. Proceedings of the Construction Research Congress, May 8-10, Banff, Alberta, pp: 1084-1093.
- Ziarati, K., R. Akbari and V. Zeighami, 2011. On the performance of bee algorithms for resource-constrained project scheduling problem. Applied Soft Comput., 11: 3720-3733.