+6,
.UDNRZ3RODQG0D\
Projects Portfolio Prototyping Grzegorz Bocewicz, Wojciech MuszyĔ ski, Robert Wójcik, and Zbigniew Banaszak
Wroclaw University of Technology, Wroclaw, Poland
[email protected]
Abstract — Decision makers, choosing the right project portfolio, face the problem of making optimal decision that meets an organisation’s objectives and priorities in uncertain situation under given constraints with various sources of knowledge often semi-structured or ill structured. Proposed approach provides the framework allowing one to take into account both: distinct (pointed), and imprecise (fuzzy) data, in a unified way. The illustrative examples regarding of project management evaluation in the context of the investment efficiency, the financial liquidity, and robustness to disturbances caused by time constrained resources availability are enclosed. Keywords — constraints programming, logic-algebraic method, fuzzy set, project management, knowledge engineering
I. INTRODUCTION
T
HE project portfolio selection is the main objective of the project management, and aims at equilibrium between company’s capabilities and customers’ requirements. Consider a company executing a given project portfolio still has some capability to undertake a new project. The routine activity involved in selecting a portfolio of projects usually concerns of some standard questions, such as: - Is it possible to undertake a new project under given (constrained in time) resources availability while guaranteeing disturbance-free execution of the already executed projects? - What is the completion time of considered project portfolio? - Does the planned project portfolio execution meet assumed financial liquidity in a given period of time? - What values of what variables guarantee the project portfolio will complete with assumed values of a given set of performance indexes? In general, project management is aimed at determining an equilibrium solution providing a good compromise between company’s needs and preferences (including financial benefits, intangible benefits, availability of resources, risk level, and so on), and customers requirements (specified by the time of implementation and budget of the relevant production orders, purchasing and installing new equipment, building a new workshop or its modernization, and so on). In other words, project portfolio prototyping came down to searching for alternative ways of resources allocation, ensuring safety of taking actions. The problems regarding of the limited resources allocation
1-4244-1543-8/08/$25.00 ©2008 IEEE
(usually following from the company’s limited resources and customers requirements) belong to a class of NP-hard problems. The standard methods, based on mathematical programming concepts (leading to the combinatorial explosion of the space of potential solutions) are not efficient. In turn, heuristic paradigms based approaches, e.g., taboo search, simulated annealing, and genetic algorithm, provide just suboptimal solutions. It should be noted however, that in both above-mentioned cases it is assumed the searched space consists admissible solutions. In many cases, such guarantee does not hold, e.g. a class of timetabling problems. Of course, in many real-life problems focusing on equilibrium between possessed by an enterprise capability and requirements imposed by work orders considered such guarantee dose not exist. It means there is no guarantee the time consuming searching process will end with any valid result. The idea standing behind of the approach proposed assumes the system considered can be represented in terms of a Knowledge Base (KB) [3], [8]. Taking into account a concept of constraints propagation and variables distribution following from the constraint programming languages it is easy to note that any KB can be represented in a standard form of so called, Constraint Satisfaction Problem (CSP) [5],[12]. So, the main problem regarding of the guarantee the solution there exists can be seen as a problem of the KB consistency checking, that in turn can be seen as the solution of the relevant CSP. It is assumed that KB is specified in terms of so-called logic-algebraic method (LAM) [7], which allows one to specify problems through a set of logic propositions. That gives possibility to determine the sufficient conditions guaranteeing existence of solutions for decision problems considered. Moreover, the proposed approach provides the framework allowing one to take into account both: distinct (pointed) and imprecise (fuzzy) data, in unified way. In case the data introduced is specified by a membership function its representation can be discretized and replaced by an ordered set of discrete values. It means, instead of standard fuzzy-set-like operations [10], [6], [8], [9] a set of constraints (described by elementary CSPs) is considered. In such approach both: distinct and imprecise data as well as linking them relation are treated in a unified form of a discrete CSP. Moreover, implementation of multi-criteria decision making (compounding different task as scheduling, batching, allocation, routing, and so on) directly follows from the nature of constraint programming (CP) paradigm (constraints propagation and variables distribution). This paper is organized as follows. Assumptions concerning the considered class of systems and the main
problem of the paper are formulated in the Section II. The considered decision problem consists in determination of a pair (a number of human resources, a number of financial resources) guaranteeing a given project portfolio will complete in arbitrarily assumed period of time. In the Section III the introduction to the logic-algebraic method is provided, and then its implementation to the knowledge generation and a decision problem resolution is presented. The Section IV introduces to the concept of a constraint satisfaction problem, and then to its implementation to a knowledge base specification. An illustrative example of the approach provided to the project portfolio prototyping and approach to imprecise data handling is shown in the Section V. Finally, the last section is devoted to conclusions. II. PROBLEM FORMULATION Given a set of projects P = {P1, P2, P3, …, Pq}. Each project Pi is described by a digraph (so called an activity network) Gi determining ordered set of operations Gi(Ei,Bi), where: Ei = {E11, E12, …, E1,ki} – a set of vertexes representing particular operations involved in the project Pi, ki – the number of the project’s Pi operations, Bi = {B11, B12, …, B1,ki} – a set of arcs describing an order of operations, ki – the number of project’s Pi operations. Given are two (in general case might be more) kinds of resources: M (financial resource), R (human resource). Quantities RG and MG signify a number of actually possessed resources, M and R, respectively. To each vertex Ei,j a pair of required resources (m,r) is assigned. Therefore, m and r describe requirements (caused by execution of a particular operation) addressed to resources M and R, respectively. Duration of particular operations is described in the form of sequence: Ti = (ti,1, ti,2, …, ti,ki); where: Ti – sequence of duration of the i-th project operation. Resources requirements for operations involved in the i-th project are presented in form of sequences Mi and Ri, respectively: Mi = (mi,1, mi,2, …, mi,,ki), where: mi,j – the requirement for the resource M imposed by j-th operation of the i-th project. Ri = (ri,1, ri,2, …, ri,ki), where: ri,j – the requirement for the resource R imposed by the j-th operation of the i-th project. Additionally, the auxiliary sequences xi, Myi, Ryi are also defined: xi = (xi,1, xi,2, …, xi,ki) where: xi,j – execution time of the j-th operation in the i-th project Myi = (myi,1, myi,2, …, myi,ki) where: myi,j – the number of the first resource, from M type resources, employed by the j-th operation in the i-th project. Ryi = (ryi,1, ryi,2, …, ryi,ki) where: ryi,j – the number of the first resources, from R type resources, employed by the jth operation, in the i-th project. Taking into account the assumptions provided, the problem considered can be stated as follows: Given a set of projects and the arbitrary chosen values of RG and MG.
Does a given project portfolio can be completed in an arbitrary given time H? If so, what is the Gantt’s diagram of its schedule? Since the problem is NP-hard, hence a trial-and-error approach applied to its solution leads to combinatorial explosion of the space of potential solutions. Moreover, in general case there is no guarantee the space searched consists of any admissible solution. Therefore, the sufficient conditions guaranteeing at least one admissible solution there exists are of crucial importance. In the case considered let us assume the sufficient conditions have a form of pairs: (RG, MG),where RG and MG are minimal values for which the required value of the considered performance index holds, (in case considered project portfolio accomplishing deadline H can be seen as such an index). In other words, a pair (RG, MG), ensuring existence of admissible solution is sought. Therefore, the relevant question we are facing with has the following form: Does there exist such a pair (RG, MG), guaranteeing a given project portfolio completion during the assumed deadline H? The response to the question results in a schedule guaranteeing the limited resources allocation during assumed period of time, i.e., the rules resolving conflicts arising among actions competing for the access to the limited resources. Of course, since in general case the number of considered types of resources can be greater than two, hence the sufficient conditions can be composed of more than two variables. III. KNOWLEDGE BASE It is assumed that the knowledge base KB describing a system (e.g. a firm) is presented in the form of the sets C, W, Y, that define the domains of some system properties c, y, w (at the qualitative level). The variables c describing the input properties of the system are called the input variables, the variables y describing the output properties of the system are called the output variables, and the variables w are called the auxiliary variables. The knowledge specifying the properties of the system under consideration is described in the form of the set of facts F(c,w,y). The facts F(c,w,y) are propositions encompassing, the relationships (i.e., constraints) occurring between individual variables c,w,y. Exemplary notation for fact: „Limited budget (c1) cause extension of duties falls to one employee (y1). In this case one should search for additional source of finance (for example sponsors) (w1) or change policy of recouvrement (w2)” can be described as follows: F1(c,w,y): c1 y1; F2(c,w,y): y1 (w1 w2) Of course, in general case the facts might be presented in various forms of logic propositions, relations, algebraic formulas, and so on. The triples (c,w,y) for which all facts F(c,w,y) are true, are presented in the form of the relation Re. Therefore, the representation of the knowledge base is defined as follows (1): KB =
(1)
