Solving the project scheduling problem with resource constraints by means of the irregular community optimization algorithm

Master's thesis in the field­ Industrial Engineering - Social Economic Systems  

August 1391  

Abstract

The issue of project scheduling with limited resources is one of the most famous issues raised in operations research and optimization. In this problem, each project consists of a number of activities, plus there are a number of resources with limited capacities. In addition to the fact that activities have priority over each other for execution, they also have limitations in the use of resources. The goal is to minimize the project completion time in such a way that priority and resource constraints are satisfied. A new irregular community optimization (ASO) algorithm is designed to solve the problem. After choosing an initial population randomly, we reach new solutions by choosing the motion policy based on the current location of each member or the motion policy based on the personal past locations of each member or the motion policy based on the location of other members of the human society or the motion policy based on the combination law. To set the parameters of the algorithm, we use the Taguchi method. In the following, the aforementioned algorithm has been implemented and tested and adjusted for different examples of the problem. The implementation of this algorithm on basic problems shows its efficiency compared to other existing algorithms.

Key words: project scheduling, irregular community optimization algorithm, project scheduling problem with limited resources.

Chapter 1 Concepts and principles of project scheduling

Introduction

The antiquity of project management goes back to at least 4500 years ago, regardless of the knowledge of project management [1], The builders of Egyptian pyramids and Mayan temples in Central America are often considered as the first project managers in the world [1]. The emergence of project management as a science began with World War I, so that in 1917, Henry L. Gantt [2] invented the famous Gantt chart [3]. After 1950, other famous project management techniques such as the critical path method [4] and was developed The science of project management has been one of the most important and practical topics, especially in the past decades. With the advancement of science and the more complex structures of projects defined in different scientific and experimental sectors, project management is constantly emerging as an integral part of the project as a whole. In today's world, with the increase in the competitive environment, it is very important to deliver goods or services with the desired quality on time while respecting various restrictions such as labor, capital, etc. Due to the saving of time, resources and money from project management, the interest in this field is increasing exponentially all over the world. Among the various components of project management, project scheduling [5] has given itself a special place due to its importance and role at the level of macro-management planning of various projects. From the practical side by improving project timing  which is a part of project management, the profit of companies, especially companies that do production and sales at the same time (production to consumption), increases significantly. The practical applications of project scheduling can be mentioned in the fields of software development, planning in transportation organizations and civil works and many other fields. In addition to the practical aspect, project timing is also very important from the theoretical and research aspect, and in recent years, many researches have been conducted in this field. Since many well-known optimization problems are a special case of project scheduling problems, this category is an attractive research field for those interested in operations research, for example, the workshop scheduling problem [6] (jssp), which is one of the most famous hybrid optimization problems, which is a special case of resource-constrained scheduling problems in which the problem resources are only machines.

According to the standard  PMBOK 2008  [7] Project management includes 42 processes, and project scheduling is only one of these processes.. Project scheduling is defined as determining the time sequence to perform a series of interdependent activities that make up the project. The meaning of activity dependency is the existence of priority relationships in their performance, which means that the performance of one activity may be dependent on the performance of one or more other activities, in which case it is said that the project has priority restrictions. Determining this schedule can be done under one goal or several specific goals. In addition to the precedence constraints that exist in all projects between activities, another type of constraints called resource constraints may also exist in the project. Project scheduling problems with only precedence constraints are known as project scheduling problems without resource constraints. In project scheduling problems, if there is resource limitation in addition to priority limitation, it is referred to as project scheduling problem with resource limitation [8]  (RCSPSP) are known. The first project scheduling models and methods designed for large scale (more than a hundred activities) date back to the late 1950s. One of the most famous of these methods is the critical path method, which was designed by Kelly [9] in 1961 for projects that have activities with definite and definite times. Other famous methods in project scheduling include the Project Evaluation and Review Technique [10] (PERT) method, which was invented by Malcolm [11] in 1956 and was created for projects that have activities with uncertain and probable times. The method of evaluation technique and graphic review[12] in 1967 by Pritzker[13] and Hopp[14]  It was invented in which  Project activities are contingent. The primary methods and models of project scheduling, which were mentioned as three important methods, were designed for projects that only have priority restrictions between activities, while in the real world, one of the most important problems is project scheduling with limited resources. Since the late 1960s, project scheduling models were developed in which both precedence constraints and resource constraints were considered simultaneously. Solving these types of problems was very difficult compared to the previous models, so the mentioned methods were not effective for solving these types of problems,  In this type of new problems, the problem solving time increased exponentially with the increase of activities, and as a result, in large problems (more than a hundred activities), due to the increase in the search space, the use of exact methods was not cost-effective in terms of time, because these types of problems, especially in large dimensions, are part of NP-hard optimization problems [15]  were considered Resource-constrained project scheduling problem in classical mode (RCPSP) is the simplest type of resource-constrained project scheduling problem, which does not have any exact method to solve it in large dimensions (more than a hundred activities). Blazevich[16]  proved that the PCPSP problem as a generalization of the JSSP problem is an NP-hard problem so that the time required to find the optimal solution by the best exact methods for networks containing more than thirty activities is very high [2]. As a result, researchers to solve the RCPSP problem in large dimensions by innovative methods[17]  and meta-heuristics[18], because these methods do not need to traverse the entire search space and can be used to reach the near-optimal solution in a reasonable time. Therefore, in this thesis, we try to use the new meta-heuristic algorithm for optimization of irregular society (ASO) [19]  which was created in 2011 by Ahmadi Javed [20] [3], for the first time to use it to solve the project scheduling problem with limited resources in the classical mode and compare its results with the best known algorithms that have been used before. 1-1) Project scheduling components The components of a project scheduling problem are summarized in three components  which include: activities, resources and priority relationships. In the following, we will briefly examine each of these components. Before continuing the discussion in this section, we introduce Table 1-1 as a standard table of signs used in this thesis.

Abstract

The resource-constrained project scheduling problem is the most famous problem in operation research and optimization.

The RCPSP involves a single project comprising of a set of non-dummy activities. A non-preemptive duration exists for each activity. Moreover, some renewable resources exist and each resource has a constant capacity. The objective of RCPSP is to minimize the project make span.