برنامه ریزی چندحالته مبتنی بر بهینه سازی کلونی مورچه ها تحت محدودیت منابع تجدیدپذیر و تجدیدناپذیر
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|7876||2013||8 صفحه PDF||سفارش دهید||6538 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Automation in Construction, Available online 20 June 2013
An ant colony optimization (ACO)-based methodology for solving the multi-mode resource-constrained project scheduling problem (MRCPSP) considering both renewable and nonrenewable resources is presented. With regard to the MRCPSP solution consisting of activity sequencing and mode selection, two levels of pheromones are proposed to guide search in the ACO algorithm. Correspondingly, two types of heuristic information and probabilities as well as related calculation algorithms are introduced. Nonrenewable resource-constraint and elitist-rank strategy are taken into account in updating the pheromones. The flowchart of the proposed ACO algorithm is described, where a serial schedule generation scheme is incorporated to transform an ACO solution into a feasible schedule. The parameter-selection and the resultant performance of the proposed ACO methodology are investigated through a series of computational experiments. It is expected to provide an effective alternative methodology for solving the MRCPSP by utilizing the ACO theory.
In a construction process, available amounts of renewable and nonrenewable resources may be limited due to cost or other factors. Therefore the resource-constrained project scheduling problem (RCPSP) that has been intensively addressed in the manufacturing field has also been studied in the construction field. In the classical RCPSP, each activity has a single execution mode, that is, the resource requirements and associated duration for an activity are fixed. However, in the practical circumstance when limited resources are shared by multiple activities and the real-time amounts of available resources are thus flexible, some activities may have multiple execution modes to be selected, each mode having different resource amounts corresponding to different durations for each activity. Multiple selections of execution modes are considered to reduce delay of activities and idle times of resources in consideration of real-time amounts of resources. It is shown that the study on the multi-mode resource-constrained project scheduling problem (MRCPSP) is important and has been gradually paid attention in the construction field. The methodologies that have been developed for solving the MRCPSP include the exact and heuristic or meta-heuristic approaches. The exact methods include the exact enumeration schemes , a depth-first branch and bound procedure , as well as the dynamic programming approaches . In addition, the enumeration scheme  for the single-mode was extended to the multi-mode case . Finally, a branch-and-bound algorithm  was developed based on the exact procedure . Sprecher and Drexl  suggested to use their branch and bound algorithms as heuristic procedures by imposing a time limit. Other heuristic methods for solving the MRCPSP include the biased random sampling approach , the single-pass and a multi-pass approach , the local search procedure , the one based on total floats , and the branch-and-cut procedure . The meta-heuristic methods for solving the MRCPSP include the simulated annealing schemes , the genetic algorithm (GA) methods ,  and  and the particle swarm optimization methods  and . In this study an ant colony optimization (ACO) algorithm, another meta-heuristic method, is proposed to solve the MRCPSP with the renewable and nonrenewable resources. Based on the theory of ACO and the feature of the MRCPSP, the mechanism of the ACO algorithm is proposed. Two types of pheromones with regard to sequence and mode selection of activities are proposed. Similarly, two types of heuristics and probabilities as well as their computation algorithms for each type of pheromone are respectively introduced. Each ant-constructed solution should be checked against the nonrenewable resource infeasibility and will be handled by adjusting the mode-combination. Then the flowchart of the ACO algorithm for solving the MRCPSP is presented. A series of computational experiments are carried out to investigate the performance of the ACO-based methodology for solving the MRCPSP.
نتیجه گیری انگلیسی
The multi-mode resource-constrained project scheduling problem (MRCPSP) considering both renewable and nonrenewable resources is often faced in planning construction projects. While some meta-heuristic methods including GA, SA and PSO have been applied to solve the MRCPSP, this paper presents another method for solving the MRCPSP based on the ACO theory and the characteristic of the MRCPSP. The mechanism of the ACO algorithm is proposed, in which two levels of pheromones are considered with regard to the solution in terms of sequence and mode selection of the activities. Correspondingly, the heuristic information and probability for each type of the pheromone and their computation algorithm are presented, where the existed heuristic rules respectively for the sequence and mode selection of the activities in the MRCPSP can be utilized. Elitist-rank strategy and nonrenewable resource-constraint are incorporated into the updating procedure of the pheromones. A detailed flowchart of the ACO algorithm is constructed, where a SSGS is adopted to transform an ACO solution to a feasible schedule. Through a series of computational experiments, the parameter-selection and the performance of the proposed ACO methodology have been investigated by testing various parameter-combinations and comparing with other meta-heuristic methods for solving the MRCPSP. The study is expected to provide an effective alternative methodology for solving the MRCPSP in consideration of renewable and nonrenewable resources, hoping beneficial to both researchers and practitioners in analyzing and planning construction projects. Of course, further studies such as consideration of multiple objectives for the MRCPSP are needed. Meanwhile, investigation and improvement on the computational effort for solving the MRCPSP using the proposed ACO method need to be addressed.