مساله تراز کردن منبع با منابع متعدد با استفاده از الگوریتم ژنتیک تطبیقی
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
8092 | 2013 | 12 صفحه PDF |

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Automation in Construction, Volume 29, January 2013, Pages 161–172
چکیده انگلیسی
Resource management ensures that a project is completed on time and at cost, and that its quality is as previously defined; nevertheless, resources are scarce and their use in the activities of the project leads to conflicts in the schedule. Resource leveling problems consider how to make the resource consumption as efficient as possible. This paper presents an Adaptive Genetic Algorithm for the Resource Leveling Problem, and its novelty lies in using the Weibull distribution to establish an estimation of the global optimum as a termination condition. The extension of the project deadline with a penalty is allowed, avoiding the increase in the project criticality. The algorithm is tested with the Project Scheduling Problem Library PSPLIB. The proposed algorithm is implemented using VBA for Excel 2010 to provide a flexible and powerful decision support system that enables practitioners to choose between different feasible solutions to a problem in realistic environments.
مقدمه انگلیسی
Project management is the process of the coordination and integration of activities in an efficient and effective manner using limited resources. It consists of linking resources to their respective deliverables and assembling them into the whole project [1]. Resource management is an intrinsic element of project management [2], [3] and [4]; resource management ensures that the project is completed on time and at cost and that the quality is as previously defined [5], [6] and [7]. This is even more necessary for project-based companies such as contractors [3], [8] and [9]. In fact, project scheduling problems are one of the most important problems that practitioners deal with in scheduling, especially when they need to achieve the most efficient resource consumption without increasing the prescribed makespan of the project. However, because resources are scarce, the use of resources in the activities of the project leads to conflicts in the schedule [10]. Project scheduling problems comprise not only resource-constrained problems but also Resource Leveling Problems, among others [11]. These two kinds of problem consider resource consumption in two different ways: in the former it is seen as a constraint, and in the latter the problem is to make it as efficient as possible. Even though these two approaches may seem similar, they are conceptually different. Both have been widely studied by researchers and applied by practitioners, although these two groups are unaware of the differences between the approaches and the serious limitations imposed by the heuristics used in the commercial software. These two problems are defined as non-deterministic polynomial-time hard (NP-hard) problems [12]. The first approach is a regular problem known as the Resource Constrained Project Scheduling Problem; its objective is to reduce the makespan without exceeding the constraints of resource availability [13] and [12]. The second, known as the Resource Leveling Problem (from now on, RLP) is a non-regular problem; its objective is to achieve the most efficient resource consumption without increasing the prescribed makespan of the project [14] and [12]. The two problems can be combined together as a multi-objective optimization problem, but there is always one main objective (usually the makespan); the other objective (usually the efficient resource consumption) is secondary. Nevertheless, conventional analytical and heuristic methods are neither flexible nor productive when solving the RLP [15]. Some reasons for this inefficiency are, on the one hand, that exact procedures simplify the real problems so are not useful at offering optimal solutions with acceptable computational effort [16] and, on the other hand, that heuristics offer solutions which are far from optimal, so that it is necessary to apply metaheuristic algorithms to complex and realistic projects [17]. Recently, important approaches have been made by researchers to improve the efficiency of resource consumption, proposing different heuristics which are applicable to small projects; simple examples try to show the merits of a particular algorithm, without establishing clear criteria for a performance comparison between the different algorithms [18]. Following this line of work, Liao et al. [11] proposed some ideas to advance the RLP in realistic environments; these authors made several proposals for the development or the improvement of the RLP. Regarding resource allocation, these authors proposed the use of a decision support system to assist project managers, as well as the development of benchmarking tests for performance assessment and comparison [11]. Concerning resource leveling, they suggested the use of multiple resources allowing the extension of the project deadline with a penalty [11]. We take these proposals as challenges to be overcome in this paper, contributing a little to the corpus of knowledge in this field. Therefore, in this paper we present an Adaptive Genetic Algorithm (AGA) for the RLP with multiple resources allowing the extension of the project deadline with a penalty; for this purpose, we use the Weibull distribution as a termination condition, establishing an estimation of the global optimum. The proposed algorithm is tested with the standard “project scheduling problem library” (PSPLIB) [18], presenting a complete set of benchmarking tests. A decision support system is also used in order to implement this algorithm. Without loss of generality, we consider the classical resource leveling objective function: the total squared utilization cost for a given schedule. The remainder of this paper is organized as follows. Section 2 provides the classification and formulation of the RLP. Section 3 details the different solving procedures: exact, heuristic, and metaheuristic algorithms with the new use of the Weibull distribution as a termination condition. Section 4 describes the algorithm proposed for the RLP with multiple resources. Computational results and the benchmarking test are explained in Section 5. Finally, conclusions are drawn.
نتیجه گیری انگلیسی
The Resource Leveling Problem (RLP) is a non-regular problem whose objective is to achieve a resource consumption which is the most efficient possible, without increasing the prescribed makespan of the project. Conventional analytical and heuristic methods are neither flexible nor productive when solving the RLP. Exact procedures are not useful for offering optimal solutions with acceptable computational effort; and, on the other hand, heuristics offer solutions which are far from the optimal so that it is necessary to apply metaheuristic algorithms for complex and real projects in realistic environments. In this paper: 1. We describe the complete state of the art of the RLP, proposing different binary and integer mathematical formulations and incorporating modifications and improvements on previous contributions. 2. We propose an Adaptive Genetic Algorithm (AGA) for the RLP with multiple resources allowing the extension of the project deadline with a penalty. 3. We propose the use of the three-parameter Weibull distribution as a termination condition for the metaheuristic, with location parameter γor the Weibull Bound (WB) as an estimation of the global optimum. The previous contributions have been tested with the standard “project scheduling problem library” (PSPLIB), presenting a complete set of benchmarking tests solved with only the most usual and common parameters to provide clear criteria for comparison between the different algorithms. To prove the merits of the proposed algorithm, the results we obtained have been compared with the most common heuristic procedures and with a more efficient forward–backward scheduling scheme. The proposed AGA is always better than the heuristics, especially for the most difficult problems with 120 jobs. The proposed AGA for the RLP has been implemented with VBA for Excel 2010 to provide a flexible and powerful decision support system that enables practitioners to choose between different feasible solutions to a problem, and that is in addition easily adjustable to the constraints and particular needs of a project in a realistic environment. This contribution is a tool that can be applied in a direct and simple way by practitioners; besides, it can serve as a starting point for specialists in order to develop user-friendly and practical computer applications to provide realistic and good solutions for production and project management. The use of the Weibull distribution was applied following a heuristic process. Its improvement is proposed as a future research field, searching for a bound (ε > 0) in such a way that the inequality |γn − γ| ≤ ε, ∀ n ≥ N0 holds for all sample sizes n greater than a given size N0; the exact parameter would therefore be in the interval γn − ε ≤ γ ≤ γn + ε. Another important area for future research is the consideration of the graph density as a new variable in the computational test, to determine its influence on the optimization and the correlation between the other variables