دانلود رایگان ترجمه مقاله الگوریتم اصلاح شده PSO برای به حداقل رساندن هزینه های کل منابع در MRCPSP (نشریه هینداوی 2012)

یک الگوریتم PSO اصلاح شده برای به حداقل رساندن کل هزینه های منابع در MRCPSP

A Modified PSO Algorithm for Minimizing the Total Costs of Resources in MRCPSP

We introduce a multimode resource-constrained project scheduling problem with finish-to-start precedence relations among project activities, considering renewable and nonrenewable resource costs. We assume that renewable resources are rented and are not available in all periods of time of the project. In other words, there is a mandated ready date as well as a due date for each renewable resource type so that no resource is used before its ready date. However, the resources are permitted to be used after their due dates by paying penalty costs. The objective is to minimize the total costs of both renewable and nonrenewable resource usage. This problem is called multimode resource-constrained project scheduling problem with minimization of total weighted resource tardiness penalty cost MRCPSP-TWRTPC, where, for each activity, both renewable and nonrenewable resource requirements depend on activity mode. For this problem, we present a metaheuristic algorithm based on a modified Particle Swarm Optimization PSO approach introduced by Tchomte and Gourgand which uses a modified rule for the displacement ´ of particles. We present a prioritization rule for activities and several improvement and local search methods. Experimental results reveal the effectiveness and efficiency of the proposed algorithm for the problem in question.

1 Introduction

The resource-constrained project scheduling problem RCPSP is the scheduling of project activities subject to precedence relations as well as renewable resource constraints with the objective of minimizing the makespan of the project. Each nonpreemptive activity in RCPSP can be done in a single mode. For more information on RCPSP and solution methods, we refer to Demeulemeester and Herroelen 1. In the multimode RCPSP MRCPSP, a set of allowable modes can be defined for each activity which is characterized by a constant duration and associated resource requirements. In this paper we consider MRCPSP with the objective of minimizing total costs of all resources. Two types of resources, renewable and nonrenewable, are considered. Nonrenewable resource cost of an activity is a function of its resource requirements, determined by its modes. The limited renewable resources are rented and each renewable resource is available in a predetermined sequential time period specified by its ready time and due date and is not available before the ready time. However, each renewable resource can be used after its due date with tardiness penalty cost. As the cost of renting for each renewable resource is fixed, there is no need to incorporate it into the objective function and only tardiness penalty cost is considered for each renewable resource. The MRCPSP under minimization of total costs of resources RCPSP-TWRTPC is an applicable problem and a modified version of the MRCPSP in which all assumptions and constraints of the MRCPSP are held, but the objective function is different. We assume that there are a few renewable resources such as very expert human resources with high skill levels, particular types of cranes, and tunnel boring machines that should be leased from other companies providing these types of resources. Since these limited renewable resources are employed in other projects, there is a dictated ready date as well as a due date for each of them such that no resource can be accessible before its ready date, but these resources are allowed to be used after their due dates by paying penalty cost, depending on the resource type. Also, we suppose that there are a few nonrenewable resources like budget, materials, energy, or other resources which are consumed during the project.

Ranjbar et al. 2 studied this problem with single mode for each activity and availability of one unit for each type of renewable resource, without considering nonrenewable resources. They called this problem resource-constrained project scheduling problem, minimization of total weighted resource tardiness penalty cost RCPSP-TWRTPC, which is an extended form of resource-constrained project scheduling problem RCPSP. They developed a metaheuristic-based GRASP algorithm together with a branch and bound procedure to solve the problem.