به حداقل رساندن هزینه وزنی دیرکرد در منبع در برنامه ریزی پروژه Resource Tardiness Weighted Cost Minimization in Project Scheduling

In this paper, we study a project scheduling problem that is called resource constrained project scheduling problem under minimization of total weighted resource tardiness penalty cost (RCPSP-TWRTPC). In this problem, the project is subject to renewable resources, each renewable resource is available for limited time periods during the project life cycle, and keeping the resource for each extra period results in some tardiness penalty cost. We introduce a branch and bound algorithm to solve the problem exactly and use several bounding, fathoming, and dominance rules in our algorithm to shorten the enumeration process. We point out parameters affecting the RCPSP-TWRTPC degree of difficulty, generate extensive sets of sample instances for the problem, and perform comprehensive experimental analysis using the customized algorithm and also CPLEX solver. We analyze the algorithm behavior with respect to the changes in instances degree of difficulty and compare its performance for different cases with the CPLEX solver. The results reveal algorithm efficiency ۱٫ Introduction Resource constrained project scheduling problems are widely studied in the open literature. Various criteria are studied in these problems. Project makespan minimization is one of the most studied objectives which is aimed in the resource constrained project scheduling problem (RCPSP). Resource tardiness minimization is another objective that has been much less studied in the literature. This objective is studied in the current paper. It differs from makespan minimization, since it tries to schedule those activities earlier for which the due dates of the required resources are earlier, even though this may elongate the project makespan. The optimal schedule in this case can change by simply changing the due dates of the resources. But in makespan minimization, the due dates of the resources are not taken into account. Resource tardiness minimization is a pervasive objective in the practical cases of the project scheduling. In many projects, resources are available for limited periods of the project life cycle and keeping them available after the related periods is subject to some tardiness costs. Renewable resources that are rented from outside the project or the ones that are common between various projects are usually subject to this condition. For example, in construction projects, heavy machines such as tower cranes or bulldozers are usually subject to this condition.These resources may also have ready times; that is, they may not be ready at the beginning of the project. Resource tardiness cost minimization is a preferred objective in scheduling of these projects. In this paper we study an extension of the RCPSP problem that is called resource constrained project scheduling problem under minimization of total weighted resource tardiness penalty cost (RCPSP-TWRTPC) [1]. In this problem the project is subject to renewable resources. Each renewable resource is available for limited time periods during the project life cycle and keeping the resource for each extra period results in some tardiness penalty cost. The objective is to minimize the total resource tardiness penalty cost. We introduce a branch and bound algorithm to solve the problem exactly. The branching structure in this algorithm is similar to the precedence tree approach, which is a basic approach to solve the RCPSP problem [2]. We use several bounding, fathoming, and dominance rules in our algorithm to shorten the enumeration process. The algorithm performance is numerically analyzed. The results reveal algorithm efficiency. The rest of this paper is organized as follows. In the next section, the related literature is reviewed; in Section 3 the RCPSP-TWRTPC problem and in Section 4 the branch and bound algorithm to solve the problem are described in detail. Section 5 is dedicated to the experimental analysis and finally, Section 6 contains a few concluding remarks.