Improved and Competitive Algorithms for Large Scale Multiple Resource-Constrained Project-Scheduling Problems

摘要

Project scheduling using several resource constraints has been considered frequently by scholars in literatures, but when the dimensions of the problem is getting bigger those solution methods have not high efficiency. The objective of this paper is to propose a branch and bound algorithm and also an enhanced and competitive genetic algorithm to solve the problem of project scheduling with large scale and multiple resource-constrained. The aim of the model is to minimize the project's completion time which is the objective of all employees. The proposed genetic algorithm in comparison with other meta-heuristic algorithms in the literature has been improved in order to solve larger scale problems easier and with less error. Also the branch and bound algorithm has the ability to solve the large scale problems in a short time using an appropriate upper and lower bound. In this algorithm, an upper bound heuristic that solves the problem with subtle error is proposed. This method is being used to faster prune the answer tree. Also a lower bound based on the solution of a Linear Programming (LP) model has been proposed that has high computational speed as well as tight that makes the solution of large scale problems possible. Computational results are also reported for the most known benchmark problems taken from the operational research literature. These results show that the improved GA in this paper is capable of solving the majority of the problems with less error than other metaheuristic methods. Especially in problems with 120 activities, this algorithm on average has 10% less error than the best existing metaheuristic method. Also the proposed B&B algorithm is capable of solving problems with more than 50 activities in a short time, while the existing algorithms could solve the problems with up to 50 activities so far.