Multi-mode resource constrained multi-project scheduling and resource portfolio problem

This paper introduces a multi-project problem environment which involves multiple projects with assigned due dates; activities that have alternative resource usage modes; a resource dedication policy that does not allow sharing of resources among projects throughout the planning horizon; and a total budget. Three issues arise when investigating this multi-project environment. First, the total budget should be distributed among different resource types to determine the general resource capacities, which correspond to the total amount for each renewable resource to be dedicated to the projects. With the general resource capacities at hand, the next issue is to determine the amounts of resources to be dedicated to the individual projects. The dedication of resources reduces the scheduling of the projects’ activities to a multi-mode resource constrained project scheduling problem (MRCPSP) for each individual project. Finally, the last issue is the efficient solution of the resulting MRCPSPs. In this paper, this multi-project environment is modeled in an integrated fashion and designated as the resource portfolio problem. A two-phase and a monolithic genetic algorithm are proposed as two solution approaches, each of which employs a new improvement move designated as the combinatorial auction for resource portfolio and the combinatorial auction for resource dedication. A computational study using test problems demonstrated the effectiveness of the solution approach proposed.     

A survey of variants and extensions of the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) consists of activities that must be scheduled subject to precedence and resource constraints such that the makespan is minimized. It has become a well-known standard problem in the context of project scheduling which has attracted numerous researchers who developed both exact and heuristic scheduling procedures. However, it is a rather basic model with assumptions that are too restrictive for many practical applications. Consequently, various extensions of the basic RCPSP have been developed. This paper gives an overview over these extensions. The extensions are classified according to the structure of the RCPSP. We summarize generalizations of the activity concept, of the precedence relations and of the resource constraints. Alternative objectives and approaches for scheduling multiple projects are discussed as well. In addition to popular variants and extensions such as multiple modes, minimal and maximal time lags, and net present value-based objectives, the paper also provides a survey of many less known concepts.     

基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化

承包商的现金流动态均衡对不确定条件下项目的顺利实施有重要影响。作者研究基于随机活动工期的现金流动态均衡前摄性及反应性项目调度问题,目标是在随机活动工期条件下,为承包商生成现金流均衡基准进度,并根据执行过程中的实际情况,动态地对其进行反应性调整。首先,通过建立前摄性调度优化模型生成基准进度,并提出两个反应性调度策略对其进行调整。其次,为以上诸模型的求解设计了模拟退火和禁忌搜索相结合的混合算法tabu-SA。最后,针对前摄性调度模型,在随机生成的算例集合上对算法进行测试,并进行大规模仿真实验。研究结果可以为随机活动工期下承包商保持现金流动态均衡、确保项目顺利实施,提供定量化决策支持。     

Uncertainty Modelling in Software Development Projects (With Case Study)

A project scheduling model tailored specifically for software development projects is proposed in this study. The model incorporates uncertainties related to activity durations and network topology. The first type of uncertainty exists due to error-prone coding which might result in elongated task durations caused by validation and debugging sessions. Furthermore, in practice, macro-activities represent groups of sub-tasks in order to simplify the planning and monitoring of the project. Due to the aggregation, it is more difficult to be precise on the duration of a macro-activity.The uncertainty related to the network topology is due to common database design issues or program modules shared among parallel tasks in the project network. These tasks become associated with each other through uncertain Start-to-Start (SS) precedence relationships. On the other hand, SS lags may also be the outcome of technological precedence relationships among pairs of activities. However, the imprecision underlying the work content of a predecessor activity leads to uncertain SS lags.Software development projects are human-intensive projects and hence, the duration of a task depends on the skill of the person assigned to the job as well as his/her learning rate. Thus, a task may be realized by alternative staff members which results in different expected task durations. Hence, a realistic model proposed for software development projects should incorporate staff assignment features under the uncertainties discussed above. In this study, we develop a mathematical model for software development projects and propose heuristic solution methods to be used by the project co-ordinator in preparing the project plan. The heuristic algorithms developed here are tested on real data provided by a consulting firm undertaking software development projects from manufacturing companies in Turkey.     

A bi-objective hierarchical program scheduling problem and its solution based on NSGA-III

In enterprise project management systems, a program at the tactical level coordinates and manages multiple projects at the operational level. There are close relationships between multiple projects in a program, which are typically manifested as shared resources and precedence relationships. Most research efforts have concentrated on the resource sharing by projects, while the precedence relationships between projects have yet to be comprehensively investigated. In this paper, a bi-objective hierarchical resource-constrained program scheduling problem proposed, where both resource sharing and precedence relationships between projects are considered in a distributed environment. The problem contains two different sub-problems at the operational level and the tactical level, and they are modeled in the same way as two bi-objective multi-mode scheduling problems. Shared resources are allocated from the tactical level to the operational level, and once they are allocated to a project, they can only be re-allocated to other projects once the current project is finished. Subsequently, a two-phase algorithm based on NSGA-III is developed. The algorithm runs at the operational level and the tactical level in turn. According to the Pareto fronts of projects that are submitted from the operational level, the bi-objective program planning at the tactical level is conducted under the constraints of precedence relationships and shared resources. The results of computational simulations demonstrate the satisfactory performance of the improved algorithm. By coordinating the local optimization of projects and the global optimization of the program in a hierarchical framework, the method proposed in this paper provides an effective integrated scheduling method for decision-makers at various levels of a program.

     

Branch-and-price approach for the multi-skill project scheduling problem

This work introduces a procedure to solve the multi-skill project scheduling problem (MSPSP) (Néron and Baptista, International symposium on combinatorial, optimization (CO’2002), 2002). The MSPSP mixes both the classical resource constrained project scheduling problem and the multi-purpose machine model. The aim is to find a schedule that minimizes the completion time (makespan) of a project, composed of a set of activities. In addition, precedence relations and resources constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Practical applications include the construction of buildings, as well as production and software development planning. We present a column generation approach embedded within a branch-and-price (B&P) procedure that considers a given activity and time-based decomposition approach. Obtained results show that the proposed B&P procedure is able to reach optimal solutions for several small and medium sized instances in an acceptable computational time. Furthermore, some previously open instances were optimally solved.     

Activity consolidation to improve responsiveness

There is a long history of modeling projects to meet time and cost objectives. Most of these models look at adjusting the level of resources available to the project in order to crash the time required to complete certain activities. These models usually take the activities and the graph structure of the project as given and fixed, but in practice there is often significant discretion in how activities are defined. This is especially important when there are information flows and time delays associated with the hand-off between an activity and its successor. This paper models the choice of how to meet the time and cost objectives through combining multiple activities into one while maintaining the original activity precedence relationships. A mixed-integer linear programming model is developed for the problem, and an implicit enumeration and a tabu search heuristic are tested with a suite of problem examples.     

Selecting optimal selling format of a product in B2C online auctions with boundedly rational customers

The advancement of Internet technology has enabled new formats for selling products in the B2C online auctions. At present, on the major online auction sites, there exist three popular selling formats, namely, the posted price, pure auction and buy-price auction formats. It is an important decision problem for a firm to select the most profitable format to sell its products through the Internet. The customer behavior is of course a crucial element of the decision process. To the best of our knowledge, most models available today assume that customers are perfectly rational. To better understand the decision process, in this paper, we incorporate the concept of bounded rationality into consideration. We first present a “behavior choice function” to characterize the behavior of the customers with bounded rationality. Then corresponding to each selling format, we construct a revenue model based on the bounded rationality for analysis. Finally, we conduct some elaborate computational experiments to investigate the performance of each revenue model for developing new managerial insights. Our computational results clearly demonstrate how the bounded rationality of customer behavior affects the choice of a preferable selling format for a B2C firm in an online auction.     

A zero-one model for project portfolio selection and scheduling

A zero-one integer linear programming model is proposed for selecting and scheduling an optimal project portfolio, based on the organisation's objectives and constraints such as resource limitations and interdependence among projects. The model handles some of the issues that frequently arise in real world applications but are not addressed by previously suggested models, such as situations in which the amount of available and consumed resources varies in different periods. It also allows for interactive adjustment following the optimisation process, to provide decision makers a method for controlling portfolio selection, based on criteria that may be difficult to elicit directly. It is critical for such a system to provide fast evaluation of alternatives the decision makers may want to examine, and this requirement is addressed. The proposed model not only suggests projects that should be incorporated in the optimal portfolio, but it also determines the starting period for each project. Scheduling considerations can have a major impact on the combination of projects that can be incorporated in the portfolio, and may allow the addition of certain projects to the portfolio that could not have been selected otherwise. An example problem is described and solved with the proposed model, and some areas for future research are discussed.     

A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations

We present an optimal solution procedure for the resource-constrained project scheduling problem (RCPSP) with generalized precedence relations (RCPSP-GPR) with the objective of minimizing the project makespan. The RCPSPGPR extends the RCPSP to arbitrary minimal and maximal time lags between the starting and completion times of activities. The proposed procedure is suited for solving a general class of project scheduling problems and allows for arbitrary precedence constraints, activity ready times and deadlines, multiple renewable resource constraints with time-varying resource requirements and availabilities, several types of permissible and mandatory activity overlaps and multiple projects. It can be extended to other regular and non-regular measures of performance. Essentially, the procedure is a depth-first branch-and-bound algorithm in which the nodes in the search tree represent the original project network extended with extra precedence relations to resolve a number of resource conflicts. These conflicts are resolved using the concept of minimal delaying modes, which is an extension of the notion of minimal delaying alternatives for the RCPSP. Several bounds and dominance rules are used to fathom large portions of the search tree. Extensive computational experience is reported.     

Reverse auction with buyer-supplier negotiation using bi-level distributed programming

This study presents a framework for solving a sealed-bid, multi-issue, and multi-sourcing reverse auction problem in which negotiation takes place between the buyer and the suppliers during the bidding process. The problem is formulated as a bi-level distributed programming model in which the buyer is the upper level decision maker, while suppliers at the lower level make decisions independent of each other. The negotiation process between the buyer and the suppliers is facilitated via the iterative exchange of decision information between the upper and lower levels of the model. The outcome of the sealed-bid auction is determined using an algorithm designed to establish the optimum quantity allocation and delivery time at the upper level and the corresponding optimized production plans at the lower level. The feasibility of the proposed approach is demonstrated via an illustrative example.     

基于相对熵的区间Pythagorean模糊多属性AQM决策方法及其应用

针对决策信息为区间Pythagorean模糊数,属性权重不完全确定的多属性决策问题,提出了一种基于相对熵的AQM决策方法。首先,提出区间Pythagorean模糊数的相对熵,计算了各方案与区间Pythagorean模糊正理想方案和负理想方案间的相对熵,据此构建了基于方案相对满意度最大的非线性规划属性权重确定模型;其次,针对每个属性,利用新的区间Pythagorean模糊数得分函数计算方案的0-1优先关系矩阵,依据AQM方法对所有0-1优先关系矩阵进行融合得到合成0-1优先关系矩阵,并确定了方案的综合度,由此获得方案的排序。最后,以软件开发项目的选取为实例说明了该方法的可行性和有效性。     

A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling

We develop a heuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require one or more constrained renewable resources. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements, as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. We use a scatter search algorithm to tackle this problem, using path relinking methodology as a solution combination method. Computational results on randomly generated problem sets are compared with the best available results indicating the efficiency of the proposed algorithm.     

A Two Stage Search Heuristic for Scheduling Payments in Projects

When the Net Present Value (NPV) of a project is used as a measure of its financial performance, effective management of cash flows over the duration of the project is critical for improved profitability. Progress payments are a major component of project cash flows. In many project environments, the contractor can negotiate payment terms. Payments are typically tied to completion of project activities and therefore have significant impact on the schedule of activities and the timing of the payments. In this paper, we consider the problem of simultaneously determining the amount, timing and location of progress payments in projects to maximize NPV. Due to the combinatorial nature of the problem, heuristics are a practical approach to solving the problem. We propose a two-stage heuristic where simulated annealing is used in the first stage to determine a set of payments. In the second stage, activities are rescheduled to improve project NPV. We compare the performance of this general purpose heuristic with other problem-dependent heuristics from the literature. Our results indicate that the simulated annealing heuristic significantly outperforms the parameter-based heuristics. Although rescheduling in the second stage improves NPV, increases are relatively small in magnitude. While the specific parameters settings suggested by the simulated annealing heuristic in this study may have limited generalizability at this time due to the narrow range of problems tested, our analysis suggests that a pure simulated annealing approach is a very attractive alternative for obtaining good heuristic solutions to the complex problem of scheduling payments in projects.     

A model and approach to the challenge posed by optimal power systems planning

Currently, there is a need to plan and analyze the electric power transmission system in greater detail and over larger geographic areas. Existing models approach the problem from different perspectives. Each model addresses different aspects of and has different approximations to the optimal planning process. In order to scope out the huge challenge of optimal transmission planning, this paper presents a new modeling approach for inter-regional planning and investment in a competitive environment. This modeling approach incorporates the detailed generator, topology and operational aspects found in production cost planning models into a larger framework that can find optimal sets of transmission expansion projects. The framework proposed here can be used in an auction to award investment contracts or as a part of a more general policy analysis. The solution yields the set of transmission projects that have the highest expected benefits, while also representing generic generation expansions under the same objective. The model is a two-stage, mixed-integer, multi-period, N-1-reliable model with investment, unit commitment, and transmission switching. The combination of combinatorial, stochastic and operational elements means this model may be computationally intractable without judicious modelling aggregations or approximations to reduce its size and complexity. Nevertheless we show via a dual problem that analysing the economics and sensitivity of the solution is computationally more straightforward.     

Decision-making on prioritization of projects in higher education institutions using the analytic network process approach

The prioritization of projects in higher education institutions is a complex decision-making problem. In this paper we deal with two scenarios within Higher Education Institutions. The first scenario is a need to prepare an action plan for activities that will result in the implementation of a portfolio of projects at the institutional level. The second scenario is making a decision on whether to start a new project application, and if so, which project to choose in a situation where project teams have several project ideas and limited resources. The purpose of the paper is to show how to include corporate strategy in the decision-making process and use the Analytic Network Process as a multiple criteria decision-making methodology which can be used in solving project selection problems.     

Project Scheduling with Multiple Modes: A Genetic Algorithm

In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan.     

Scheduling projects with variable-intensity activities: The case of dynamic earliness and tardiness costs

This paper addresses the problem of resource-constrained multi-project scheduling with variable-intensity activities. Four dynamic models, based on four types of precedence relations are presented to minimize dynamic earliness and tardiness of project activities. The first two models are designed to cope with start-to-end precedence relations via unit step functions and specially constructed penalty functions respectively. Conditions are derived for the case when an optimal solution of the second model with relaxed start-to-end precedence relations is the global optimal solution of the first model. The third and the fourth models are dealing with overlapping precedence relations based on a milestone approach and on start-to-start precedence relations with lags respectively. The relationship between the four models is studied and a lower bound on the objective function is proposed. An efficient time-decomposition approach is adopted for solving the last three models. This approach is used to guide an effective search for the solution of the first model.     

Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling

In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included.     

人数与任务数不相等的指派问题

本提出人数与任务数不相等的指派问题应当视为一个多目标决策问题，首先要求指派给各人的任务数目两两之间相差不能超过1，其次要求所需总时间最少；并且给出了该问题的求解方法。