03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

ARTICLE IN PRESS

Int. J. Production Economics 96 (2005) 175–187

A bi-objective model for robust resource-constrained project scheduling

M.A. Al-Fawzana,*, Mohamed Haouarib

a

King Abdulaziz City for Science and Technology, P.O. Box 6086, Riyadh 11442, Saudi Arabia b Ecole Polytechnique de Tunisie, BP 743, 2078 La Marsa, Tunisia Received 5 March 2003; accepted 1 April 2004 Available online 20 July 2004

Abstract A common problem which arises in project management is the fact that the planned schedule is often disrupted by several uncontrollable factors like additional time that might be required for rework and correction of detected defects. As a result, project managers are often unable to meet the promised completion dates. It is therefore vital to take into account such possible disruptions and their potential negative consequences at the project schedule design stage. In this paper, we address the issue of designing a project schedule which is not only short in time, but also less vulnerable to disruptions due to reworks and other undesirable conditions. To that aim, we introduce the concept of schedule robustness and we develop a bi-objective resource-constrained project scheduling model. We consider the objectives of robustness maximization along with makespan minimization. We develop a tabu search algorithm in order to generate an approximate set of ef?cient solutions. Several variants of the algorithm are tested and compared on a large set of benchmark problems. r 2004 Elsevier B.V. All rights reserved.

Keywords: Resource-constrained project scheduling; Robust scheduling; Multi-objective combinatorial optimization; Tabu search

1. Introduction Project scheduling deals with the allocation of scarce resources to a set of interrelated activities that are usually directed toward some major output and require a signi?cant period of time to perform. Since the early days of operations research, project scheduling has attracted an ever growing attention. This interest is largely motivated by its great practical importance in diverse

*Corresponding author. Fax: +996-1-481-3991. E-mail address: mfawzan@kacst.edu.sa (M.A. Al-Fawzan).

industries for designing new production processes, developing new products, setting up new facilities, and implementing new information systems, to cite just a few applications. The two well-known network techniques CPM and PERT, were both developed in the late 1950s to determine the minimum completion time of a project in such a way that the precedence relationships among activities are satis?ed. However, in most practical situations the activities of a project require several additional resources. These resources may include manpower, machines, equipment, and capital budget (Blazewicz et al., 1986). Ignoring the

0925-5273/$ - see front matter r 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.ijpe.2004.04.002

ARTICLE IN PRESS

176 M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187

resource constraints may result in an infeasible schedule with several resource con?icts. During the last 20 years, Resource Constrained Project Scheduling Problems (RCPSPs) have generated a great amount of research in the operations research literature. Solving a RCPSP means providing an optimal project schedule that not only satis?es the precedence constraints but also provide a feasible allocation of the required resources (i.e., resolve resource con?icts). Traditionally, two main categories of resource constraints are distinguished:

*

*

Renewable resources: a speci?ed amount of the resource is continuously available during the planning horizon (examples are machines and manpower). Non-renewable resources: a speci?ed amount of the resource is available for the entire planning horizon (an example is the capital budget).

Moreover, in many practical situations, each activity may be performed according to several alternatives called modes. Each mode being characterized by a speci?c time duration and resource consumption. In this paper, we address the single-mode RCPSP with renewable resources. Formally, this problem may be de?ned as follows: a project consists of a set J of n interrelated activities 1; y; n: There are precedence constraints which specify that activity i cannot be performed until all its predecessors Pi have been ?nished. There are K renewable resources. A constant amount of Rk units of resource k is continuously available from time zero onwards. The duration of activity i is pi units of time. During this time period a constant amount of rik units of resource k is occupied. Preemption is not allowed. The objective is to determine starting (or ?nishing) times for the activities in such a way that a performance criterion is optimized, the precedence constraints are satis?ed, and at each unit of time the total resource demand does not exceed the resource availability for each resource type. We will not attempt to review the important RCPSP literature, since very recently, Demeulemeester and Herroelen (2002) edited an excellent

handbook which is entirely devoted to this challenging topic. In addition, Brucker et al. (1999) provide an extensive review of the RCPSP literature, quoting more than 200 relevant papers. They discuss both exact and heuristic recent approaches, and they present a new notation and classi?cation scheme, similar to the one traditionally used in the machine scheduling literature. Herroelen et al. (1998) present an exhaustive survey of exact algorithms (branch and bound procedures) for several variants of the RCPSP. An exhaustive review of heuristic algorithms is presented in Kolisch and Hartmann (1998). Most of these heuristics are extensively evaluated in Hartmann and Kolisch (2000). Finally, Herroelen et al. (1997) present a survey paper exclusively focusing on project scheduling problems with discounted cash ?ows. Moreover, the reader can refer to the comprehensive monograph of Kolisch (1995). However, it is worth noting that the considerable effort devoted hitherto to modeling and solving RCPSP has been almost exclusively focusing on three optimization criteria. The optimization criterion which has been the most extensively considered so far is the makespan ?Cmax ? minimization, which is de?ned as the total time elapsed between the start and the end of the project. A second optimization criterion, which has also been widely used is the net present value (NPV) maximization. This latter criterion is appropriate for capturing the monetary aspects of project management when important levels of cash ?ows (expenditures and/or payments) are present. Finally, the third optimization criterion which has also attracted attention is the cost minimization (CM). This objective includes the case where activities may be performed in several modes resulting in different costs and/or resource consumption. In this paper, we introduce the concept of schedule robustness and we investigate a biobjective resource-constrained project scheduling model. It is worth noting that although project scheduling problems are often inherently multicriteria decision problems, the literature on multiobjective project scheduling is surprisingly scant. Indeed, as far as we know, Slowinski (1989) is the ?rst author who explicitly placed the RCPSP in a

ARTICLE IN PRESS

M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187 177

multi-objective framework. Recently, Hapke et al. (1998) presented a two-stage interactive search procedure aimed at handling a very general class of multiple-criteria project scheduling problem. In addition, Viana and de Sousa (2000) implemented two metaheuristics to solve a multimode RCPSP with three objectives that are minimized: the makespan, the weighted lateness of activities, and the violation of resource constraints (thus, they considered ‘‘soft’’ resource constraints). The rest of the paper is organized as follows. In Section 2, we present a bi-objective model for generating robust schedules for the RCPSP. In Section 3, we present a Tabu Search heuristic for our model. Several variants of the algorithm are compared on a series of benchmark problems. The computational results are reported in Section 4. In the ?nal section, we present our conclusions and discuss future research.

2. A model for robust project scheduling A common drawback to most deterministic project scheduling models is that they assume that the activities will be carried out in ideal conditions and that the proposed schedule could be implemented as planned. However, in practice, several uncontrollable factors may result in delaying the project completion time and increasing the cost. Among these undesirable factors is the imperfect quality in the achievement of some activities, which may cause additional time for rework and correction of the detected defects. It is worth recalling that rework is considered by several authors as the primary cause of project schedule disturbance (Cooper, 1993; Lewis, 1998, p. 265). Other factors which disrupt likewise a project schedule are the delay caused by unreliable deliveries from suppliers and unreliable subcontractors who are unable to meet the promised schedule. Therefore, a challenging issue in project scheduling is the design of a feasible schedule which is not only short but also which could be ideally achieved as intended (or more reasonably, slightly delayed) even if undesirable conditions occur.

In this paper, we address this issue and we propose the development of a resource-constrained project scheduling model with two objectives: makespan minimization and robustness maximization. We de?ne the robustness of a schedule, as its ability to cope with ‘‘small’’ increases in the time duration of some activities that may result from uncontrollable factors (i.e. with a limited effect on the completion time of the project). More precisely, our proposed model aims at constructing schedules that are not only short but also that can be effectively implemented (as planned) without assuming that the activities will be carried out in ideal conditions. Thus, the problem is modeled as a bi-objective combinatorial optimization problem. It is worth noting that our model is in accordance with the expectations of the project planners as surveyed in Icmeli-Tukel and Rom (1997). We propose to measure the robustness of a given schedule as follows. De?ne the free slack si as the amount of time that an activity i ?i ? 1; y; n? can slip without delaying the start of the very next activity and while maintaining resource feasibility. Thus, the robustness of a schedule is de?ned as the total sum of the free slacks. Hence, the robustness of a schedule is understood as its ability to be maintained even in the case of some undesired events in?uencing the realization of particular activities. Formally, the objective of our model, which we call the Bi-objective Resource Constrained Project Scheduling Problem (BRCPSP), is to determine starting times ti for the activities i ? 1; y; n in such a way that:

*

* *

*

at each time t; the total resource demand does not exceed the resource availability for each resource type, the given precedence constraints are satis?ed, the makespan Cmax ? Maxi?1;y;n ?ti ? pi ? is minimized, and P the robustness O ? n si is maximized. i?1

2.1. A motivating example Consider the example given by Icmeli-Tukel and Rom (1997). For convenience, we reproduce in

ARTICLE IN PRESS

178 M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187

Fig. 1 the network graph. The numbers of the nodes are the activity numbers. The two numbers at the top of each node represent the duration (in days) and the resource requirement, respectively. There is one resource type and the availability of that resource is four units per time period. Consider the two schedules S1 and S2 that are depicted in Figs. 2 and 3, respectively. Both of S 1 and S2 have a makespan Cmax ? 7: However, the computed robustness (i.e. the sum of P5 1 slacks and S 2 are 0 and 4, i?2 si ? of S respectively. Now suppose that under unexpected circumstances some of the activities of the project did not meet the customer’s expectations (i.e. speci?cations). Hence, they need additional rework in order to comply with those speci?cations. The additional work for each activity are displayed in Table 1. According to the last changes, both of S 1 and S2 have to be rescheduled as shown in Figs. 4 and 5, respectively. We observe that although S 1 and S2 were expected to have the same makespan, after rework S1 was delayed by 3 days whereas S 2 (which has a largest robustness) was delayed by one day only. Hence, one may reasonably expect that by maximizing the robustness of the schedule it became less sensitive to unexpected delays or any additional work which might be required.

4

Resource

3 2 1

4 5

2 3 4

3

2

1

5

6

7

8

9

10

time

Fig. 2. Graphical representation of S1 :

4

Resource

3 2 1

5 2 3

1 2 3 4 5 6 7 8 9 10

4

time

Fig. 3. graphical representation of S2 :

Table 1 Additional work (days) Activity Additional work 1 1 0 2

2,1 2 4,1 0,0 1 3 3,2 0,0 6

2 3 4 5

Additional work

4

Resource

4 5,2 5

Fig. 1. Example network.

3 2 1

4 3 5 2

1 2 3 4 5 6 7 8 9 10

time

Fig. 4. Graphical representation of S1 with additional work.

ARTICLE IN PRESS

M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187 179

Additional work

4

Resource

3 2 1

5 2 3

1 2 3 4 5 6 7 8 9 10

4

time

Fig. 5. Graphical representation of S2 with additional work.

It is worth noting that alternative approaches, dealing with uncertainty in the realization of activities, are the traditional probabilistic approach, the use of fuzzy numbers (Slowinski and Hapke, 1999), and the Critical Chain Scheduling and Buffer Management (CC/BM) of Goldratt (1997). In particular, this latter has recently emerged as one of the most popular approaches to project management. Basically, CC/BM accounts explicitly for duration uncertainty and focuses on the key tasks and resources (through the reduction or elimination of multitasking). For an in-depth analysis of the strengths and weaknesses of this approach, the reader is referred to Herroelen and Leus (2001). In the following, we present a solution strategy for the BRCPSP.

3. A multi-objective tabu search algorithm for the BRCPSP The last decade witnessed an increasing interest in research dealing with multi-objective combinatorial optimization (MOCO) problems. For a survey, the reader is referred to Ehrgott and Gandibleux (2000). So far, three types of strategies have been proposed to solve MOCO problems: (i) Enumerate the entire set of ef?cient solutions through exact methods like Branch-andBound (B&B) or Dynamic Programming (DP). It is worth recalling that a solution is said to be ef?cient (or non-dominated) if it is impossible to improve it with respect to all of

the objectives without violating any constraint. These exact methods are very scarce in the literature and most of them are designed for speci?c problems. For instance, " the B&B algorithm of Visee et al. (1998) provides the whole set of ef?cient solutions of the bi-objective knapsack problem, and the DP algorithm of Klamroth and Wiecek (2000) generates all the non-dominated solutions of different complex knapsack models. As it is widely known for single objective (NP-hard) combinatorial optimization problems, exact methods can only solve very small sized MOCO problems. In addition, the cardinality of the ef?cient set of solutions usually increases not only with the problem size but also with the number of criteria. (ii) It is also possible to approximate the set of ef?cient (or non-dominated) solutions by means of constructive heuristics (see for instance Chattopadhyay and Momoh, 1999), or metaheuristics such as Genetic Algorithms (Murat and Ishibuchi, 1997), Tabu Search (Ben Abdelaziz et al., 1999), and Simulated Annealing (Ulungu et al., 1999). (iii) The third strategy is to cooperate with the Decision Maker (DM) in order to obtain his preferred solutions. This process is called an interactive method. Interactive methods include either exact methods or heuristic methods since at each step, the procedure has to search for some ef?cient (or nondominated) solutions in order to present them to the DM. This approach is particularly designed for the case where the set of ef?cient solutions is large. Teghem et al. (2000), for example, proposed a simulated annealing based interactive method in order to help a DM to make a choice between the approximate set of ef?cient solutions. This method was experimented on the knapsack and the assignment multi-objective problems. In the sequel, we present an algorithm for the BRCPSP based on the second strategy, and aimed at providing an approximate set of non-dominated schedules. More precisely, we propose the adaptation of the principles of TS to the BRCPSP. Since

ARTICLE IN PRESS

180 M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187

we are concerned with a multi-objective framework, the problem may have more than one solution forming the ef?cient set. The adaptation of TS to this context generates an approximation of this set. Moreover, because of the combinatorial aspect of the BRCPSP, the search must generate both supported and unsupported ef?cient solutions (i.e. those ef?cient solutions that belong to a facet or the relative interior of the polyhedron of feasible solutions, respectively). It is worth noting that TS has been successfully applied by many authors for the solution of the classical single objective RCPSP by Pinson et al. (1994), Lee and Kim (1996), Baar et al. (1999), and Nonobe and Ibaraki (2002). We organize the presentation of our MOTS algorithm by describing successively the schedule representation, the neighborhood structure, the selection scheme, the tabu list attributes and the aspiration criterion. 3.1. Schedule representation A schedule p is represented as an ordered list L ? ?j?1? ; y; j?n? ? of the n activities. For the sake of simplicity, only precedence feasible lists are considered (a list is said to be precedence feasible if for each activity a we have arg?a? > maxbAPa farg?b?g? Given a precedence feasible list L; a corresponding precedence and resource feasible schedule can be built by using a Schedule Generation Scheme (SGS). As pointed out by Kolisch and Hartmann (1998), SGS is the core of most heuristics for the RCPSP. This algorithm starts from scratch and constructs in n steps a feasible schedule, so that at step i ?i ? 1; y; n? activity j?i? is selected and scheduled at the earliest precedence and resource feasible start time. For that purpose, we use the following Forward Recursion Procedure. Notation * Rk ?t? Predj Sje Cje amount of resource k available at time t set of immediate predecessors of activity j earliest start time of activity j earliest completion time of activity j

U f0g

EC ?C?q? ?q?0;n

set of unscheduled activities dummy activity with zero processing time, no resource consumption, and which precedes all the activities fCje : jeUg list of the elements of EC ranked in a non-decreasing order

SGS—forward recursion procedure Initialization: U ? J; EC ? f0g; q ? 0; C?0? ? 0 For i ? 1 to n do Select the activity j ? j?i? Set U ? U\fjg For all tAEC do For k ? 1; y; K do * Compute Rk ?t? e Sj :? MaxiAPredj fCie g Let q be the index with Sje ? C?q? While ?8 tA?Sje ; Sje ? pj ?; * 8k ? 1; y; K; Rk ?t?Xrjk ? is False do q :? q ? 1 Sje :? C?q? End (while) Cje :? Sje ? pj EC ? EC,fCje g; Update C End (for i) This algorithm provides the earliest feasible start and completion times for the given list. The makespan of the project is Cmax ? Maxj?1;y;n fCje g: However, in order to compute the free slacks of the activities, we need to compute the latest feasible completion times Cjl ?j ? 1; y; n?: Hence, the free slack of an activity j is sj ? Cjl ? Cje ?j ? 1; y; n?: At this point, it should be made clear that the latest completion times are computed in such a way that for each activity j ?j ? 1; y; n? the following properties hold: (P1) During the time interval ?Sje ; Cjl ? the K resources are continuously available with an amount Xrjk : (P2) It is possible to complete activity j at time Cjl (but not at time Cjl ? 1? without delaying the start of the very next activity (i.e. each successor could start at its earliest start

ARTICLE IN PRESS

M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187 181

time that was calculated by the forward recursion). Hence, if activity j starts at Sje but, for some uncontrollable factor, actually requires pj ? ej units of time (with 0pej psj ?; instead of the planned pj units of time, then the schedule remains feasible and no successor would be delayed. In order to compute the latest ?nish times, we consider the earliest completion times that were calculated with the forward procedure and we 0 construct an ordered list of the n activities L ? ?u?1? ; u?2? ; y; u?n? ?; where activities are ranked in a non-decreasing order of their earliest completion time (note that this list is different from L?: We use a backward procedure so that at step i ?i ? n; y; 1? activity u?i? is included in the partial schedule and scheduled at the latest precedence and resource feasible completion time while satisfying properties (P1) and (P2). Before providing a formal description of the procedure, we extend the previous notation: Sjl Succj fn ? 1g latest start time of activity j set of immediate successors of activity j dummy activity with zero processing time, no resource consumption, and which is preceded by all the activities fSje : jeUg list of the elements of ES ranked in a non-increasing order

q :? q ? 1 Cjl :? S?q? End (while) Sjl :? Cjl ? pj ES ? ES,fSje g; Update S End (for i) 3.2. Neighborhood structure At a given iteration, let p0 be the current feasible schedule with a corresponding precedence feasible priority list L?p0 ? ? ?j?1? ; y; j?n? ?: We generate N neighbors by randomly selecting N feasible moves (N is a problem parameter which denotes the neighborhood size). A move requires two adjacent activities ?j?k? ; j?k?1? ? to be swapped in the list L?p0 ?: Only precedence feasible moves are considered. More precisely, activities j?k? and j?k?1? are eligible for swapping if the following conditions hold: (C1) activity j?k? is not a predecessor of j?k?1? ?j?k? ePj?k?1? ? and (C2) in the schedule p0 ; activity j?k? starts strictly before activity j?k?1? ?Sje?k? oSje?k?1? ?: Condition (C1) ensures that the new list is precedence feasible. In addition, if condition (C2) is satis?ed then swapping the positions of j?k?1? and j?k? might affect the makespan. Obviously, considering only lists which are compatible with precedence constraints reduce the computational burden, since in the Forward Recursion Procedure the activities are simply scheduled according to the ordering that is speci?ed by the corresponding list. 3.3. Selection strategy A precedence-feasible list of the n activities L0 is built and used to generate an initial schedule. Assume that p0 is the current feasible schedule. For each neighbor schedule pu ?u ? 1; y; N?; compute the makespan ?Cmax ? and the robustness P ? n si ). Let zM ?u? and zR ?u? denote the correi?1 sponding values, respectively. Consider the aggregation function de?ned as zl ?u? ? lzM ?u? ? ?1 ? l?zR ?u?

ES ?S?p? ?p?1;n?1

SGS—backward recursion procedure Initialization: U ? J; ES ? fCmax g; q ? 1; S?1? ? Cmax : For i :? n down to 1 do j ? u?i? Set U ? U\fjg For all tAES do For k ? 1; y; K do * Compute Rk ?t? e Cjl :? MinhASuccj fSh g Let q be the index with Cjl ? S?q? While ?8tA?Sje ; Cjl ?; 8k ? 1; y; K; * Rk ?t?Xrjk ? is False do

ARTICLE IN PRESS

182 M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187

where 0plp1: At a given iteration, we select as a ? new current solution the neighbor schedule pu such that zl ?u? ? ? minu?1;y;N zl ?u?: The weight l plays an important role since it aims to reach a particular supported ef?cient solution and then generate its ef?cient neighborhood, so that the interior of the feasible set is explored in order to get unsupported ef?cient solutions. Since nonsupported, non-dominated points are typically not far from the non-dominated frontier, the generated set is expected to be a good sample of the whole set of ef?cient solutions. In our implementation, we used the set of weights W ? flv ? v=s : v ? 0; 1; y; sg; where s is a non-negative integer parameter denoted hereafter by the number of steps. Therefore, our MOTS algorithm consists in running s ? 1 times a single objective TS, each with a particular value of the weight l: Note that, the particular values of ls and l0 tend to provide the approximate solutions of the minimum makespan and the maximum robustness, respectively. 3.4. Tabu list attributes and aspiration criterion Since a move consists of selecting a feasible pair ?j?k? ; j?k?1? ?; then we store in the tabu list the last performed moves. In order to override the tabu list when there is a good move, we implement the following aspiration criterion: a tabu move is accepted if it produces a solution which outperforms the best solution obtained so far. This comparison is performed with respect to the aggregation function. 3.5. Approximation of the ef?cient set An approximate set AEv of potentially ef?cient solutions of the single objective problem de?ned by the weight lv ?v ? 0; 1; y; s?; is obtained in the following way: the set AEv is initialized with the initial schedule. At each step of the TS, the generated neighborhood is scanned and the set of potentially ef?cient solutions AEv is updated. This operation consists in removing dominated schedules (a schedule px dominates a schedule py if zM ?x?pzM ?y? and zR ?x? > zR ?y? or zM ?x?ozM ?y? and zR ?x?XzR ?y??: If after a ?xed number of iterations ?Itermax ? there is no improvement of AEv

then the algorithm stops. An approximation AE of the ef?cient set E is obtained after dropping the dominated schedules from the union set S v?0;y;s AEv :

3.6. Synthesis of the MOTS algorithm Initialization Construct a precedence-feasible list L0 and generate an initial schedule p0 AE ? |; TL ? | (TL denotes the tabu list) Iterative step For v ? 0 to s do AEv ? fp0 g; lv ? v s Repeat Select randomly N moves (non-tabu moves and/or satisfying the aspiration criterion) Construct the set of neighbors N?p0 ? ? fpu : u ? 1; y; Ng Compute for each pu the makespan zM ?u? and the robustness zR ?u? AEv ? AEv ,N?p0 ? Remove from AEv all dominated schedules ? Select pu such that zlv ?u? ? ? minu?1;y;N ?lv zM ?u? ? ?1 ? lv ?zR ?u?? ? 0 p ? pu Update the tabu list TL Until (Itermax iterations are performed with no improvement of AEv ? AE ? AE,AEv End (for) Remove from AE all dominated schedules

4. Computational experiments 4.1. Test problems We tested our approach on the benchmark problem set j30 generated with PROGEN, which is a problem generator developed by Kolisch et al. (1995). This problem set is speci?cally designed for the RCPSP, and it consists of 480 instances with n ? 30 activities and K ? 4 resources.

ARTICLE IN PRESS

M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187 183

4.2. Parameters selection Our MOTS algorithm allows for different choices of ?ve parameters: the tabu list size TL, the number of iterations before stopping Itermax ; the number of steps s; the neighborhood size N; and the aggregation function. We performed some preliminary experiments and we found no evidence that the variation of the two ?rst factors (namely, TL and Itermax ) plays any signi?cant role. Hence, based on these ?ndings, we ?xed the tabu list size to TL ? 7; and the number of iterations before stopping to Itermax ? 0:5n (where n represents the number of activities). Moreover, we assigned two levels for each of the three remaining factors in the following way:

* *

Table 2 Characteristics of the eight variants Variant V1 V2 V3 V4 V5 V6 V7 V8 Number of steps 10 20 10 20 10 20 10 20 Neighborhood size 0.3 0.3 0.6 0.6 0.3 0.3 0.6 0.6 Aggregation function zl ?:? zl ?:? zl ?:? zl ?:? wl ?:? wl ?:? wl ?:? wl ?:?

*

Number of steps: s ? 10 and 20. Neighborhood size: N ? Jynn; with y ? 0:3 and 0.6 (n is the number of activities). Aggregation function AF : zl ?u? and wl ?u? ? lwM ?u? ? ?1 ? l?wR ?u? where wM ?u?: relative improvement of the makespan ? ?zM ?0? ? zM ?u??=zM ?0? (zM ?0? is the makespan of the current solution). wR ?u?: relative improvement of the robustness ? ?zR ?u? ? zR ?0??=zR ?0? ?zR ?0? is the robustness of the current solution).

Note that when wl ?:? is used as the aggregation function, then at each step, the best neighbor is the ? schedule pu such that wl ?u? ? ? maxu?1;N wl ?u?: The use of wl ?:? is motivated by the observation that very often the robustness is much larger than the makespan, and, as a consequence, it strongly dominates it in the aggregation function zl ?:?: This drawback is avoided by considering only relative improvements. After combining the three factors, eight different variants Vh ?h ? 1; y; 8? are obtained. The characteristics of these variants are displayed in Table 2. 4.3. Performance measure The eight variants were coded in Basic and compiled with the Quick Basic 4.5 compiler. All the computational experiments were carried out on

a Pentium II 350 MHz Personal Computer. In order to analyze the relative performance of the variants, all of the 480 instances of the set j30 were successively solved by the eight variants. For each instance i; we computed the approximate nondominated set AEih and the CPU time tih ; obtained after running the variant Vh ?h ? 1; y; 8?: It is worth noting, that the problem of selecting the best variant has no simple answer. Indeed, in MOCO, and contrary to single objective combinatorial optimization, there is no straightforward basis of comparison of heuristics, and addressing the issue of designing a reliable measure of performance is by itself a challenging problem. In this context, an interesting approach developed by Czyzak and Jaszkiewicz (1998) provides an estimate of the distance of the approximate nondominated set to the exact one (denoted by R?: In the case of the BRCPSP, this latter measure is based on the distance measure d?s; R? between a feasible schedule s and the non-dominated set R and de?ned as d?s; R? ' s m jCmax ? Cmax j jOs ? Om j ? min max ; ; mAR D?Cmax ? D?O? &

?9?

x where Cmax and Ox represent the makespan and the robustness of a given schedule x; respectively, and D?Cmax ? and D?O? represent the range of the makespan and the robustness in the non-dominated set R; respectively (the reader may have noticed that it is implicitly assumed that the nondominated set is not a singleton). Hence, a measure

ARTICLE IN PRESS

184 M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187

of the quality of a given approximate set AEih may be de?ned as X 1 d?s; R?: ?10? d?AEih ; R? ? jAEih j sAAE

ih

This measure offers the advantage of providing a reliable estimate of the proximity of a heuristic set to the non-dominated frontier. However, since in our experiments the exact non-dominated set is unknown, we have to replace in (9) and (10) the exact set R by the approximate set AEi obtained after removing the dominated schedules from the S union set h?1;8 AEih : Unfortunately, the drawback of this measure is that it is not appropriate for the case where the approximate set AEi is a singleton which contains just one approximate ideal point (and in our experiments we found relatively many such cases). An alternative measure of performance, that we used in our experiments, and which was introduced by Ulungu (1993), is based on the following ratio: jAEih -AEi j eih ? : ?11? jAEi j Although this latter ratio is insensitive to the ‘‘closeness’’ to the approximate non-dominated set, it provides a measure of the ‘‘contribution’’ of variant h to the approximate non-dominated set AEi : Consequently, if variant h dominates (is dominated) by the other variants, then eih will be close to 1 (0). Moreover, it can be used in all cases, including the case where AEi is a singleton. Table 3 presents the results obtained with each of the eight variants. For each variant h ?h ? P 1; y; 8? the sum eh ? 480 eih ; as well as the mean i?1 CPU times th in seconds. Table 3 shows that the best performance is obtained with a large number of steps, a large neighborhood size, and the aggregation function wl ?:?:

Table 3 Performance results Variant eh th V1 253.58 12.1 V2 279.93 20.7 V3 269.92 23.0 V4

Not surprisingly, we observe that the CPU time increases (almost linearly) as s and/or y increase. However, statistical testing (namely, the so-called paired comparison design) strongly supports the argument that the aggregation function has no signi?cant impact on the running time. 4.4. Robustness analysis A very desirable algorithmic characteristic of a heuristic is its robustness. This robustness may be de?ned as the ability of the heuristic to generate an approximate solution which is not sensitive to the variation of the seeds. In order to analyze the robustness of our best variant (namely, V8 ?; we selected randomly 50 instances from the set j30: Each instance i was run 10 times with different seeds, while keeping all the parameters ?xed. For each instance i (i ? 1; y; 50?; we denote AEik the approximate non-dominated set generated after run k (k ? 1; y; 10?; and AEi the approximate non-dominated set which results from the union of the sets AEik : Then, we computed the ratio eik using (11) and the mean value ei (computed over the 10 runs). Clearly, the distribution of the series ?ei ? provides a good idea on the robustness of the approach. Hence, a large value of ei (i.e. close to 1) means that, on average, a large percentage of the set of non-dominated schedules ?AEi ? is generated in each run of instance i; regardless of the used seed. On the contrary, a small value of ei (i.e. close to 0) indicates that there is a signi?cant difference between the approximate sets obtained with different seeds. In Fig. 6, we report the results obtained with the ?fty instances (the instances are numbered by increasing ei ?: Fig. 6 indicates that the approach is fairly robust. Indeed, we found that the mean value of the ?ei ? is 0.54.

V5 265.61 12.3

V6 295.66 20.5

V7 289.13 23.6

V8 322.78 40.2

300.34 40.2

ARTICLE IN PRESS

M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187 185

4.5. Analysis of the cardinality of AE It is of primary importance in multi-objective modeling to have an estimate of the cardinality of the approximate set of ef?cient solutions. Indeed, the approach may not be appropriate if the number of suggested ef?cient solutions is extremely large. In this case, an interactive method must be used in order to remove some ef?cient solutions according to the decision maker preferences. However, in our computational experiments, we observe that in most cases jAEj is of moderate size. Indeed, we found that (for the set j30? 120 instances have only one single approximate non-dominated solution. Table 4 provides the empirical distribution of the cardinality of the approximate ef?cient set obtained over the set j30: The mean (maximum) cardinality is 10.69 (30). 4.6. Performance on makespan minimization

search algorithm, each time considering as an optimization criterion the single objective wv ?:? obtained through the aggregation of the relative improvement of makespan and the robustness: ? ? wv ?u? ? v wM ?u? ? 1 ? v wR ?u?; v ? 0; y; s: s s We used this strategy and compared the minimal makespan schedule provided by the MOTS algorithm with the optimal makespan. For that purpose, we ran the variant V8 on the entire set j30 (480 instances). The optimal values are taken from Demeulemeester and Herroelen (1997). We found that 387 instances out of 480 (80.63%) were solved exactly, and that the average percentage deviation from optimal solution is 0.48%. The maximal deviation being 7.89%. We compared our results with those obtained by three specialized algorithms, namely:

*

*

The approximate non-dominated set AE obtained after running the MOTS algorithm can be used to derive a good approximate solution to the (single objective) RCPSP with minimum makespan objective function. For that purpose, it suf?ces to scan the set AE and to select the ? schedule pu with minimum makespan. Hence, the approach consists in running s ? 1 times a tabu

two tabu search algorithms (TS1 and TS2) both developed by Baar et al. (1999) and a genetic algorithm (GA) devised by Hartmann (1998).

1.2 1 0.8

0.6 0.4 0.2 0 0 5 10 15 20 25 30 35 40 45 50

The results of the comparison are presented in Table 5. The results indicate that even though our algorithm is not speci?cally designed for makespan minimization, it compares rather favorably with special purpose algorithms. However, as expected, the mean computing time is comparatively very long for MOTS. This is due to two main reasons. Firstly, running MOTS is equivalent to solving ?s ? 1? times a single objective RCPSP, and secondly, at each iteration the robustness of each neighbor schedule is evaluated, which is time consuming.

(εi)

5. Conclusion

Instances

Fig. 6. Analysis of the robustness. Table 4 Empirical distribution of jAEj for the set j30 jAEj Frequency (%) 1 25.00 2–10 24.80 11–17 26.25 18–21 17.70 22–30 6.25

In this paper, we investigated a bi-objective resource-constrained project scheduling problem. Two objectives were considered: makespan minimization and robustness maximization. The importance of the ?rst objective is obvious in the present context of global competition which compels companies to complete the project in a minimum time. The second objective, which is

ARTICLE IN PRESS

186 M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187

Table 5 Performance of the MOTS algorithm on the makespan minimization TS1 Problems solved to optimality Average deviation (%) Maximal deviation (%) Average CPU time (s)

a b

TS2 389 0.4 6.9 15d

GA Not available 0.54b/0.25c Not available Not available

MOTS 387a/329b/373c 0.48a/1.93b/0.62c 7.89a/19.35b/8.62c 42a/23b/41c

347 0.7 7.5 2d

This result was obtained using the stopping criterion described in Section 3.5. This result was obtained after 1000 evaluations. c This result was obtained after 5000 evaluations. d This time was obtained on a Sun Ultra 2 workstation.

equivalent to the maximization of a sum of free slacks, is a measure of the ability of a schedule to be completed within the promised date even in the case of some undesired events in?uencing the realization of particular activities. A multi-objective tabu search algorithm has been devised for solving the bi-objective resource constrained project scheduling problem. Several variants of the algorithm were compared using statistical design of experiments. The best variant was thoroughly tested on a large sample of 480 benchmark problems and it proved to be robust and to generate in most cases a moderately sized set of ef?cient solutions. Moreover, its performance on the single objective makespan minimization is comparable to special purpose tabu search algorithms. For future research, at least two issues are worth investigating. Firstly, it would be interesting to generalize the present model to include nonrenewable resources as well as multiple execution modes for each activity. Secondly, it appears that the number of ef?cient solutions increases with the number of activities. Thus, an extension which deserves to be investigated is to embed the present work in an interactive strategy which aims to reduce the number of proposed schedules.

References

Baar, T., Brucker, P., Knust, S., 1999. Tabu search algorithms and lower bounds for the resource-constrained project scheduling problem. In: Voss, S., Martello, S., Osman, I.H., Roucairol, C. (Eds.), Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Dordrecht, pp. 1–18. Ben Abdelaziz, F., Krichen, S., Chaouachi, J., 1999. A hybrid heuristic for multiobjective knapsack problems. In: Voss, S., Martello, S., Osman, I.H., Roucairol, C. (Eds.), Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Dordrecht, pp. 205–212. Blazewicz, J., Cellary, W., Slowinski, R., Weglarz, J., 1986. Scheduling under resource constraints–Deterministic models. Annals of Operations Research 7. Brucker, P., Drexl, A., Mohring, R., Neumann, K., Pesch, E., 1999. Resource-constrained project scheduling: Notation, classi?cation, models, and methods. European Journal of Operational Research 112, 3–41. Chattopadhyay, D., Momoh, J., 1999. A multiobjective operations planning model with unit commitment and transmission constraints. IEEE Transactions on Power Systems 14, 1078–1084. Cooper, K.G., 1993. The rework cycle: benchmarks for the project manager. Project Management Journal 24, 17–21. Czyzak, P., Jaszkiewicz, A., 1998. Pareto simulated annealing? A metaheuristic for multiobjective combinatorial optimization. Journal of Multi-Criteria Decision Analysis 7, 34–47. Demeulemeester, E., Herroelen, W., 1997. New benchmark results for the resource-constrained project scheduling problem. Management Science 43, 1485–1492. Demeulemeester, E., Herroelen, W., 2002. Project scheduling: A Research handbook. Kluwer Academic Publishers, Boston. Ehrgott, M., Gandibleux, X., 2000. A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22, 425–460. Goldratt, E.M., 1997. Critical Chain. The North River Press Publishing Corporation, Great Barrington.

Acknowledgements The authors would like to thank two anonymous referees for their valuable suggestions that have led to several improvements.

ARTICLE IN PRESS

M.A. Al-Fawzan, M. Haouari / Int. J. Production Economics 96 (2005) 175–187 Hartmann, S., 1998. A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics 45, 733–750. Hartmann, S., Kolisch, R., 2000. Experimental state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research 127, 394–407. Hapke, M., Jaszkiewicz, A., Slowinski, R., 1998. Interactive analysis of multiple-criteria project scheduling problems. European Journal of Operational Research 107, 315–324. Herroelen, W., Leus, R., 2001. On the merits and pitfalls of critical chain scheduling. Journal of Operations Management 19, 559–577. Herroelen, W.S., Van Dommelen, P., Demeulemeester, E.L., 1997. Project network models with discounted cash ?ows a guided tour through recent developments. European Journal of Operational Research 100, 97–121. Herroelen, W., De Reyck, B., Demeulemeester, E.L., 1998. Resource-constrained project scheduling: A survey of recent developments. Computers and Operations Research 25, 279–302. Icmeli-Tukel, O., Rom, W.O., 1997. Ensuring quality in resource constrained project scheduling. European Journal of Operational Research 103, 483–496. Klamroth, K., Wiecek, M.M., 2000. Dynamic programming approaches to the multiple criteria knapsack problem. Naval Research Logistics 47, 57–76. Kolisch, R., 1995. Project Scheduling Under Resource Constraints, Ef?cient Heuristics for Several Problem Cases. Physica-Verlag, Wurzburg. Kolisch, R., Hartmann, S., 1998. Heuristic algorithms for solving the resource-constrained project scheduling problem: Classi?cation and computational analysis. In: Weglarz, J. (Ed.), Handbook on Recent Advances in Project Scheduling. Kluwer, Dordrecht, to appear. Kolisch, R., Sprecher, A., Drexl, A., 1995. Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science 41 (10), 1693–1703. 187

Lee, J.K., Kim, Y.D., 1996. Search heuristics for resourceconstrained project scheduling. Journal of Operational Research Society 47, 678–689. Lewis, J.P., 1998. Mastering Project Management. McGraw Hill, New York. Murat, T., Ishibuchi, H., 1997. Performance of MOGA for ?ow shop scheduling problems. In: Kuriynis (Ed.), Proceedings of the 14th Conference on Production Research, Osaka Institute of Technology, Japan, pp. 498–501. Nonobe, K., Ibaraki, T., 2002. Formulation and tabu search algorithm for the resource constrained project scheduling problem. In: Ribeiro, C., Hansen, P. (Eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Dordrecht, pp. 557–588. Pinson, E., Prins, C., Rullier, F., 1994. Using tabu search for solving the resource-constrained project scheduling problem. Working paper, Universit" Catholique de l’Ouest, e Angers. Slowinski, R., 1989. Multiobjective project scheduling under multiple-category resource constraints. In: Slowinski, R., Weglarz, J. (Eds.), Advances in Project Scheduling. Elsevier, Amsterdam. Slowinski, R., Hapke, M., 1999. Scheduling Under Fuzziness. Springer, Berlin. Teghem, J., Tuyttens, D., Ulungu, E.L., 2000. An iteractive method for multi-objective combinatorial optimization. Computers and Operations Research 27, 621–634. Ulungu, E.L., 1993. Optimisation combinatoire multicrit! re: e D" termination de l’ensemble des solutions ef?caces et e m" thodes interactives. Ph.D. dissertation Facult! Polyteche e nique de Mons, Belgium. Unpublished. Ulungu, E.L., Teghem, J., Fortemps, P., Tuyttens, D., 1999. MOSA method: A tool for solving MOCO problem. Journal of Multi-Criteria Decision Analysis 8, 221–236. Viana, A., de Sousa, J.P., 2000. Using metaheuristics in multiobjective resource constraints project scheduling. European Journal of Operational Research 120, 359–374. Vis" e, M., Teghem, J., Pirlot, M., Ulungu, E.L., 1998. An e interactive heuristic method for multi-objective knapsack problem. Journal of Global Optimization 12, 139–155.

相关文章:

更多相关标签:

- Constraint-propagation-based cutting planes An application to the resource-constrained proj
- Resource-Constrained Project Scheduling with Time Windows A Branching Scheme Based on Dynam
- The trade-off between stability and makespan in resource-constrained project scheduling
- Resource-constrained project scheduling a survey of recent developments
- 0 An Exact Algorithm for the Resource Constrained Project Scheduling Problem Based on a New
- Resource-constrained construction project scheduling model
- Management, Resource-Constrained Project Scheduling
- Disruption management for resource-constrained project scheduling(CPLEX)
- Stochastic resource-constrained project scheduling
- Resource-constrained project scheduling Past work and new directions
- A two-phase GA model for resource-constrained project scheduling 时间及资源限制工程优化
- Resource-Constrained Project Scheduling with Time Windows A Branching Scheme Based on Dynam
- Resource-constrained project scheduling a survey of recent developments
- Resource{constrained project scheduling with nonregular objective functions
- A competitive genetic algorithm for resource-constrained project scheduling