A Dependent-Chance ProgrammingModel for Proactive Scheduling

KE Hua（柯 華），WANG Lei（王 磊），HUANG Hu（黃 虎）

School of Economics and Management，Tongji University，Shanghai 200092，China

Introduction

Resource-constrained project scheduling problem（RCPSP）has been widely studied for decades.As a basic type of project scheduling，RCPSP aims at minimizing makespan of a project by scheduling activities subject to precedence relations and limited renewable resource availabilities.Assuming exact information and deterministic environment，the initial problem is solved by computing and executing baseline schedule.However，in the real world，with considerable uncertainty，the validity of these baseline schedules is undoubtedly affected.During project execution，numerous disruptions would appear.For example，activities may spend more or less time than planned，resources may breakdown，goods and materials may arrive later than scheduled，dates of schedule may change for specific reasons，new activities may have to be added into initial schedule，original activities may have to be removed for changes of project scope，or a bad weather condition may appear，etc.［1］Therefore，uncertain environment should be taken into account in project scheduling.In this paper，the uncertain factor considered is vagueness of activity duration，as effects of most other uncertainties can be converted into variation of activity duration.

Herroelen and Leus［2］distinguished five fundamental approaches for scheduling under uncertainty， namely reactive scheduling，stochastic scheduling，fuzzy scheduling，robust（proactive）scheduling and sensitivity analysis.In these five approaches，proactive scheduling and reactive scheduling both emphasize the importance of considering potential disturbs.Aytug et al.［3］pointed out the difference between proactive scheduling and reactive scheduling.Proactive scheduling settles uncertainties in advance while reactive scheduling reacts after disruptions.Specifically，reactive scheduling is used to revise or re-optimize the schedule based on different underlying strategies when disturbs occur.This approach does not rely on a proactive schedule.While proactive scheduling aims to build a robust baseline schedule，which is protected as much as possible when disruptions occur during schedule execution.It is clear that a proactive schedule plays a very significant role in guiding schedule execution by setting starting times of activities.However，Davenport and Beck［4］stated the possibility that proactive schedule became infeasible in the process of execution with consideration of uncertainty.Therefore，a reactive policy is needed to guide an infeasible schedule to be reverted to a feasible one.In this paper，we focus on proactive-reactive scheduling， which is the combination of proactive scheduling and reactive scheduling.Proactive approach includes creating multiple schedules，using probabilistic techniques to a deterministic schedule and inserting redundancy into schedule according to Sevaux and S?rensen［5］.We would develop proactive schedules by inserting extra buffer time.And reactive strategy adopted in this paper is repairing an infeasible schedule according to scheduled order［6］.For more researches on proactivereactive scheduling，readers can refer to Refs.［7-10］.

As the core part of proactive-reactive scheduling，proactive scheduling deserves to be discussed in detail.Schedule robustness，as a measure of schedule stability，is first proposed by Graves［11］in the field of production scheduling.Later，Vonder et al.［12］distinguished two types of robustness：quality robustness and solution robustness.Quality robustness could be measured by probability of ending project before deadline.While solution robustness was initially defined as sum of weighted deviations between realized and planed activity starting times.It seemed that solution robustness was more important than quality robustness in respect to guiding schedule execution.Thus many researchers were devoted to studies of solution robustness and some research achievements were gained.Al-Fawzan and Haouari［13］developed a surrogate robustness measure as the sum of free slacks of all activities.In this way，analytic evaluation of initial objective function and corresponding cumbersome simulation were avoided.The surrogate robustness measure was easy and quick to calculate and the validity of the new measure was proved in their research.Further research was studied by Lambrechts et al.［14］They noticed that the contribution of each free slack was equivalent for different activities in the previous research.This critic assumption was not reasonable.Therefore another effective surrogate robustness measure was proposed.The new robustness measure was denoted by a free slack-based function，which was equal to the weighted sum of free slack utility of each activity.

Despite high performance of robustness measures proposed before，a robust schedule may become infeasible considering unforeseen resource breakdowns or activity duration increases［4］.Then one question we may concentrate on is how high the probability of infeasibility is.This question reminds us to consider robustness of a schedule from viewpoint of chance.In other words，we can measure insensitivity of planned activity starting times with chance functions.Actually，those former models can be categorized into expected value model and solutions reached by those models can be realized with a probability of about 50%in theory.In reality，some project managers would rather sacrifice more cost to get a schedule with a higher realization probability.In this situation， they may set some management targets，such as the most cost they can accept，and the due date of a project.With these targets，they want to get a schedule with the maximum realization probability.We know when some targets are given，dependent-chance programming（DCP）proposed by Liu and Iwamura［15］can be used to settle probability maximization problem.In DCP，decision-makers hope to maximize chance functions，referring to the probabilities of satisfying some events.The readers interested in DCP may consult Refs.［16-18］.In this paper，we define a new robustness measure with DCP.

In general， proactive-reactive project scheduling problem will be discussed with stochastic activity durations.The main difference from former works is that we consider solution robustness as well as realization probability in process of developing schedule，which is realized by applying a DCP model.A hybrid intelligent algorithm integrating stochastic simulation and genetic algorithm （GA）will be designed to settle the proposed model.

This paper is organized as follows.Section 1describes general proactive project scheduling in detail.Section 2 builds one stochastic model based on DCP to measure the realization probability of proactive scheduling.In section 3，a hybrid intelligent algorithm integrating stochastic simulation and GA is designed.Then section 4 gives a numerical example in order to reveal the effectiveness of the proposed model and the algorithm.Finally some conclusions are drawn in section 5.

1 Problem Description

Generally，aproject can be described by an activity-onthe-node network like Fig.1.Let G ＝ （N，A）be an activity-on-the-node network representing aproject，where N＝｛1，2，…，n｝is the set of nodes representing activities，and A is the set of arcs representing zero-lag finish-start precedence relations among activities.Activities 1and nare dummy activities，denoting the start point and the end point of a project.The durations of activities 2to n-1can be given by a vector d＝（d2，d3，…，dn-1）.As for renewable resource type k，the available amount is represented by ak.

Fig.1 Project network

On the basis of activity-on-the-node network，we would like to introduce the classical deterministic RCPSP.A conceptual formulation can be shown as follows：

subject to：

In the above model，constraint（2）enforces precedence feasibility，where simeans the planned start time of activity i.The renewable resource constraint is enforced by constraint（3），where Stmeans the set of activities executed at time t，and rikmeans resource requirement of activity i for renewable resource type k.The objective is minimization of project duration sn.As an extension of the classical deterministic RCPSP，proactive scheduling drops deterministic environment and replaces the initial objective with deviation between the planned schedule and the real one.The model of proactive scheduling problem can be written as follows：

subject to：

The objective function（4）is the sum of the weighted deviations between realized and planed starting times.simeans the realized starting time of activity i and wirepresents the marginal delay cost of activity i.Compared with deterministic RCPSP，a deadline constraint is added by constraint（7）to prevent the appearance of an unconstrained long protected baseline schedule，where δ is a given deadline.

2 DCP Model of Proactive Scheduling

With the second model of section 1，we may get one schedule characterized by solution robustness，which is protected against disruptions as much as possible.However，this robust schedule can be realized with probability of about 50%in theory.Facing two schedules，one with less cost and lower realization probability while the other with higher cost and higher realization probability，which is better？In reality，some managers may pay more attention to realization probability than cost.In this situation，they may set some management targets，such as the most cost they can accept，and the due date of a project.When given those management targets，DCP proposed by Liu and Iwamura［15］can be used to solve scheduling problems.For the application of DCP in the field of project scheduling，Ke et al.［19］built a stochastic model based on DCP to settle project scheduling problem with stochastic activity durations，which did not take solution robustness into account.A DCP model considering robustness is built as follows：

subject to：

The objective （8）is maximizing the probability of completing aproject within budget，which is represented by C0.In our model，the due date restriction is relaxed while we would punish schedules which exceed the due date.Cis a marginal cost which would arise if scheduled completion time exceeds the due date.Precedence feasibility is imposed by constraint（9）.Constraint （10）enforces the renewable resource constraint.In our research，the uncertain factor is the vagueness of activity durations，which are given by a random vector d＝（d2，d3，…，dn-1）.

It should be noted that railway scheduling is used in this paper.In railway scheduling，activities are prevented from starting before the planned starting times.Many people thought that a roadrunner scheduling，which starts feasible activities as soon as possible without considering the scheduled times，was better than railway scheduling in terms of its contribution to ending the whole project within deadline.However， Tian and Demeulemeester［20］demonstrated that railway scheduling improved both the stability and the expected project makespans over roadrunner scheduling in one realistic situation.In fact，extra cost would appear when activities are carried out in advance as well as they are delayed.We adopt railway scheduling with consideration of its contribution to improving solution robustness of a schedule.

3 Hybrid Intelligent Algorithm

In this paper，a hybrid intelligent algorithm integrating stochastic simulation and GA is designed to solve the model proposed in section 3.Readers can refer to Ref.［21］for a detailed introduction of GA.

3.1 Solution representation and stochastic simulation

In GA，the representation of an individual is the key for the performance of the algorithm.In our research，a schedule is represented by an activity list （AL）and a relevant buffer time list （BL）.A decoding process is operated to produce a corresponding schedule.The decoding process can be described as follows.

?

Stochastic simulation is applied to simulating the objective function of a given schedule.A reactive approach according to scheduled order［6］is also included，which is operated similarly with Algorithm 1.In reactive scheduling，direpresents duration of activity i in simulation and activities are not allowed to start before planed stating times according to railway scheduling.The process of stochastic simulation is as follows.

?

（continued）

3.2 Hybrid intelligent algorithm

In this subsection，the stochastic simulation in the previous subsection is embedded into GA.In general，the procedure can be summarized as follows.Firstly，pop-size chromosomes are initialized，each of which consists of an activity list and a relevant buffer time list.Secondly，crossover and mutation operations are conducted to update the chromosomes.The next step is to calculate the objective values of all chromosomes and accordingly compute the fitness of each chromosome.Spinning roulette wheel is utilized to select the chromosomes on the basis of the different fitness values.After a certain number of generations，we report the chromosome with the best fitness value as the optimal solution.In the hybrid intelligent algorithm，stochastic simulation is used to calculate the objective values of chromosomes.

4 Numerical Example

In this section，the algorithm designed in section 3is applied to the example illustrated in Fig.1.The durations and resource requirements as well as the marginal delay costs for the relevant activities are presented in Table 1.The marginal cost C in the objective function is assumed to be 50.Activity durations are assumed to be random variables with normal distributions denoted by N（a，b），where aand b are crisp numbers.

Table 1 Basic data of activities

The minimal makespan Cmaxof the project in a deterministic environment is 15［6］.According to Vonder et al.［22］，it was adequate to set due date to be 1.3times of Cmaxin most project schedules.Therefore，the due date in our example is set as 20.With the due date，we would like to compute the minimal expected cost Cmincaused by deviations between scheduled and realized activity starting times.Given with AL1＝［1，4，5，8，2，3，7，6，9，10］and BL1＝［0，0，0，0，1，1，0，1，2，0］，Cmaxequals 87.08.However，the corresponding realization probability only equals 53.76%.In our research，the cost target C0is assumed to be 1.5times of Cmin.The optimal schedule in our model is got by AL2＝［1，4，3，2，6，5，8，7，9，10］and BL2＝［0，0，0，0，0，0，0，2，2，0］.And the corresponding realization probability is 87.62%.We compare the performance of the above two schedules and present the results in Table 2.S1and S2represent schedules generated from AL1and BL1， and AL2and BL2respectively.The realization probability of S2is close to 90%，while the realization probability of S1only equals 53.76%.Managers who can accept cost target 1.5 Cminand pay more attention to realization probability would prefer S2.

Table 2 Performance of different schedules

5 Conclusions

In this paper，we concentrate on proactive-reactive scheduling，and a new model based on DCP is proposed to measure robustness， which considers probability of realization as well as solution robustness.A hybrid algorithm integrating stochastic simulation and GA is designed and applied to an example.Two optimal schedules are got from expected value model and our model respectively and their performances are compared.By increasing cost target to 1.5 times of the minimal expected cost Cmin，we get a schedule with a much higher realization probability with the DCP model.Managers who pay more attention to realization probability than cost would prefer schedule generated from the DCP model.The results suggest our model is an effective one to settle proactive-reactive scheduling problem with consideration of realization probability.Further researches would concentrate on application of the proposed model.

［1 ］Demeulemeester E， Herroelen W.Stochastic Project Scheduling ［M ］／／Project Scheduling： a Research Handbook.US：Springer，2002：535-591.

［2］Herroelen W，Leus R.Project Scheduling under Uncertainty：Survey and Research Potentials［J］.European Journal of Operational Research，2005，165（2）：289-306.

［3］Aytug H，Lawley M A， McKay K，et al.Executing Production Schedules in the Face of Uncertainties：a Review and Some Future Directions ［J］.European Journal of Operational Research，2005，161（1）：86-110.

［4］Davenport A J，Beck J C.A Survey of Techniques for Scheduling with Uncertainty ［D／OL］.（2000）［2014］.http：／／tidel.mie.utoronto.ca／publications.php.

［5］Sevaux M，S?rensen K.A Genetic Algorithm for Robust Schedules in a Just-in-Time Environment［R］.Antwerp，Belgium：University of Antwerp，2002.

［6］Lambrechts O，Demeulemeester E，Herroelen W.Proactive and Reactive Strategies for Resource-Constrained Project Scheduling with Uncertain Resource Availabilities ［J］.Journal of Scheduling，2008，11（2）：121-136.

［7］Van de Vonder S.Proactive-Reactive Procedures for Robust Project Scheduling［D］.Leuven：Katholieke Universiteit Leuven，2006.

［8］Van de Vonder S，Demeulemeester E，Herroelen W.A Classification of Predictive-Reactive Project Scheduling Procedures［J］.Journal of Scheduling，2007，10（3）：195-207.

［9］Deblaere F，Demeulemeester E，Herroelen W.Reactive Scheduling in the Multi-mode RCPSP ［J］.Computers ＆Operations Research，2011，38（1）：63-74.

［10］Zhou Y K.A Fuzzy Buffer Setting Method for Project Scheduling under Uncertainty［J］.Applied Mechanics and Materials，2013，291／292／293／294：2889-2894.

［11］Graves S C.A Review of Pproduction Scheduling ［J］.Operations Research，1981，29（4）：646-675.

［12］Van de Vonder S，Demeulemeester E，Herroelen W，et al.The Use of Buffers in Project Management：the Trade-off between Stability and Makespan［J］.International Journal of Production Economics，2005，97（2）：227-240.

［13］Al-Fawzan M A，Haouari M.A Bi-objective Model for Robust Resource-Constrained Project Scheduling［J］.International Journal of Production Economics，2005，96（2）：175-187.

［14］Lambrechts O，Demeulemeester E，Herroelen W.A Tabu Search Procedure for Developing Robust Predictive Project Schedules ［J］.International Journal of Production Economics，2008，111（2）：493-508.

［15］Liu B D，Iwamura K.Modelling Stochastic Decision Systems Using Dependent-Chance Programming ［J］.European Journal of Operational Research，1997，101（1）：193-203.

［16］Liu B D.Uncertain Programming ［M］.New York：John Wiley ＆Sons，Inc.，1999.

［17］Liu B D.Theory and Practice of Uncertain Programming［M］.2nd ed.Berlin：Springer-Verlag，2009.

［18］Liu B D.Uncertain Programming：a Unifying Optimization Theory in Various Uncertain Environments［J］.Applied Mathematics and Computation，2001，120（1／2／3）：227-234.

［19］Ke H，Liu B D.Project Scheduling Problem with Stochastic Activity Duration Times ［J］.Applied Mathematics and Computation，2005，168（1）：342-353.

［20］Tian W D，Demeulemeester E.Railway Scheduling Reduces the Expected Project Makespan over Roadrunner Scheduling in a Multi-mode Project Scheduling Environment ［J］.Annals of Operations Research，2014，213（1）：271-291.

［21］Goldberg D E.Genetic Algorithms in Search，Optimization，and Machine Learning［M］.Boston，MA，USA：Addison-Wesley Longman Publishing Co.，Inc.，1989.

［22］van de Vonder S，Demeulemeester E，Leus R，et al.Proactive-Reactive Project Scheduling Trade-offs and Procedures ［M ］／／Perspectives in Modern Project Scheduling.US：Springer，2006：25-51.