Project scheduling under uncertainty: Survey and research potentials
---
paper_title: One-machine rescheduling heuristics with efficiency and stability as criteria

paper_content:

Abstract Heuristics for the problem of rescheduling a machine on occurrence of an unforeseen disruption are developed. The criteria include minimization of the makespan (schedule efficiency) and the impact of the schedule change (schedule stability). The impact of schedule change is a non-regular performance measure defined in two ways: (1) the starting time deviations between the new schedule and the original schedule, and (2) a measure of the sequence difference between the two schedules. Three local search procedures are developed for the bicriterion problem and a set of experiments are conducted to test the efficacy of the heuristics. The heuristic solutions are shown to be effective in that the schedule stability can be increased significantly with little or no sacrifice in makespan.
---
paper_title: Predictable scheduling of a job shop subject to breakdowns

paper_content:

Schedule modification may delay or render infeasible the execution of external activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules which can absorb disruptions without affecting planned external activities, while maintaining high shop performance. We present a predictable scheduling approach where the predictive schedule is built with such objectives. The procedure inserts additional idle time into the schedule to absorb the impacts of breakdowns. The amount and location of the additional idle time is determined from the breakdown and repair distributions as well as the structure of the predictive schedule. The effects of disruptions on planned support activities are measured by the deviations of job completion times in the realized schedule from those in the predictive schedule. We apply our approach to minimizing maximum lateness in a job shop environment with random machine breakdowns, and show that it provides high predictability with minor sacrifices in shop performance.
---
paper_title: Scheduling of Projects with Stochastic Evolution Structure

paper_content:

The so-called classical project networks used by the network techniques CPM, PERT, and MPM, only allow for modelling projects whose evolution in time is uniquely specified in advance (cf. Elmaghraby 1977 and Moder et al. 1983). Here, each project activity is carried out exactly once during a single project execution and it is not possible to return to activities previously performed (that is, no feedback is permitted). Many practical projects, however, do not meet those conditions, for example, R&D projects and projects in production management where quality control is included and thus some feedback may occur.
---
paper_title: Stochastic network project scheduling with non-consumable limited resources

paper_content:

Abstract This paper presents a newly developed resource constrained scheduling model for a PERT type project. Several non-consumable activity related resources, such as machines or manpower, are imbedded in the model. Each activity in a project requires resources of various types with fixed capacities. Each type of resource is in limited supply with a resource limit that is fixed at the same level throughout the project duration. For each activity, its duration is a random variable with given density function. The problem is to determine starting time values Sij for each activity (i,j) entering the project, i.e., the timing of feeding-in resources for that activity. Values Sij are not calculated beforehand and are random values conditional on our decisions. The model's objective is to minimize the expected project duration. Determination of values Sij is carried out at decision points when at least one activity is ready to be operated and there are free available resources. If, at a certain point of time, more than one activity is ready to be operated but the available amount of resources is limited, a competition among the activities is carried out in order to choose those activities which can be supplied by the resources and which have to be operated first. We suggest carrying out the competition by solving a zero-one integer programming problem to maximize the total contribution of the accepted activities to the expected project duration. For each activity, its contribution is the product of the average duration of the activity and its probability of being on the critical path in the course of the project's realization. Those probability values are calculated via simulation. Solving a zero-one integer programming problem at each decision point results in the following policy: the project management takes all measures to first operate those activities that, being realized, have the greatest effect of decreasing the expected project duration. Only afterwards, does the management take care of other activities. A heuristic algorithm for resource constrained project scheduling is developed. A numerical example is presented.
---
paper_title: Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling

paper_content:

This paperdescribes an algorithm designed to minimally reconfigure schedulesin response to a changing environment. External factors havecaused an existing schedule to become invalid, perhaps due tothe withdrawal of resources, or because of changes to the setof scheduled activities. The total shift in the start and endtimes of already scheduled activities should be kept to a minimum.This optimization requirement may be captured using a linearoptimization function over linear constraints. However, the disjunctivenature of the resource constraints impairs traditional mathematicalprogramming approaches. The unimodular probing algorithm interleavesconstraint programming and linear programming. The linear programmingsolver handles only a controlled subset of the problem constraints,to guarantee that the values returned are discrete. Using probebacktracking, a complete, repair-based method for search, thesevalues are simply integrated into constraint programming. Unimodularprobing is compared with alternatives on a set of dynamic schedulingbenchmarks, demonstrating its effectiveness.In the final discussion, we conjecture that analogous probebacktracking strategies may obtain performance improvements overconventional backtrack algorithms for a broad range of constraintsatisfaction and optimization problems.
---
paper_title: A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes

paper_content:

Abstract In this paper, a polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints, general precedence relations and multiple modes is proposed. Insertion objective is to minimize the resulting impact on maximum lateness, while keeping some essential characteristics of the initial schedule. A new disjunctive arc-based representation with multiple capacities associated to resource arcs is proposed. Under specific constraints, some simple dominance rules allow to find an optimal insertion position in the digraph with low-computational requirements.
---
paper_title: Matchup Scheduling with Multiple Resources, Release Dates and Disruptions

paper_content:

This paper considers the rescheduling of operations with release dates and multiple resources when disruptions prevent the use of a preplanned schedule. The overall strategy is to follow the preschedule until a disruption occurs. After a disruption, part of the schedule is reconstructed to match up with the preschedule at some future time. Conditions are given for the optimality of this approach. A practical implementation is compared with the alternatives of preplanned static scheduling and myopic dynamic scheduling. A set of practical test problems demonstrates the advantages of the matchup approach. We also explore the solution of the matchup scheduling problem and show the advantages of an integer programming approach for allocating resources to jobs.
---
paper_title: One-machine rescheduling heuristics with efficiency and stability as criteria

paper_content:

Abstract Heuristics for the problem of rescheduling a machine on occurrence of an unforeseen disruption are developed. The criteria include minimization of the makespan (schedule efficiency) and the impact of the schedule change (schedule stability). The impact of schedule change is a non-regular performance measure defined in two ways: (1) the starting time deviations between the new schedule and the original schedule, and (2) a measure of the sequence difference between the two schedules. Three local search procedures are developed for the bicriterion problem and a set of experiments are conducted to test the efficacy of the heuristics. The heuristic solutions are shown to be effective in that the schedule stability can be increased significantly with little or no sacrifice in makespan.
---
paper_title: Rescheduling manufacturing systems: A framework of strategies, policies, and methods

paper_content:

Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice.
---
paper_title: Match-up scheduling under a machine breakdown

paper_content:

When a machine breakdown forces a modified flow shop (MFS) out of the prescribed state, the proposed strategy reschedules part of the initial schedule to match up with the preschedule at some point. The objective is to create a new schedule that is consistent with the other production planning decisions like material flow, tooling and purchasing by utilizing the time critical decision making concept. We propose a new rescheduling strategy and a match-up point determination procedure through a feedback mechanism to increase both the schedule quality and stability. The proposed approach is compared with alternative reactive scheduling methods under different experimental settings.
---
paper_title: Analysis of reactive scheduling problems in a job shop environment

paper_content:

Abstract In this paper, we study the reactive scheduling problems in a stochastic manufacturing environment. Specifically, we test the several scheduling policies under machine breakdowns in a classical job shop system. In addition, we measure the effect of system size and type of work allocation (uniform and bottleneck) on the system performance. The performance of the system is measured for the mean tardiness and makespan criteria. We also investigate a partial scheduling scheme under both deterministic and stochastic environments for several system configurations.
---
paper_title: Rescheduling of identical parallel machines under machine eligibility constraints

paper_content:

Abstract In this study, we address a rescheduling problem in parallel machine environments under machine eligibility constraints. We consider total flow time as efficiency measure and the number of jobs processed on different machines in the initial and revised schedules as a stability measure. We present an optimizing algorithm for minimizing the stability measure subject to the constraint that the efficiency measure is at its minimum level. We then propose several heuristic procedures to generate a set of approximate efficient schedules relative to efficiency and stability measures.
---
paper_title: Knowledge-based reactive scheduling

paper_content:

Abstract Reactive scheduling has emerged as a new concept in production planning and control over the past few years. It is attracting the increased interest of both academic and industrial researchers in developing available knowledge-based techniques in real-time shop floor control applications and providing advanced tools for subsequent industrial applications. In this paper, we provide an overview of research results in the domain of knowledge-based reactive scheduling and some related industrial applications. Since reactive scheduling is a new and not well-defined paradigm, we start by examining some definitions of the problem given by different practitioners in the field. We then examine alternative knowledge-representation technologies and reasoning approaches which, because of t heir flexibility and reactive capability, are often applied in real-time decision-making environments. This is followed by a review of some reported industrial applications, and a summary on major areas for further researc...
---
paper_title: Reactive Scheduling Systems

paper_content:

In most practical environments, scheduling is an ongoing reactive process where evolving and changing circumstances continually force reconsideration and revision of pre-established plans. Scheduling research has traditionally ignored this “process view” of the problem, focusing instead on optimization of performance under idealized assumptions of environmental stability and solution executability. In this paper, we present work aimed at the development of reactive scheduling systems, which approach scheduling as a problem of maintaining a prescriptive solution over time, and emphasize objectives (e.g., solution continuity, system responsiveness) which relate directly to effective development and use of schedules in dynamic environments. We describe OPIS, a scheduling system designed to incrementally revise schedules in response to changes to solution constraints. OPIS implements a constraint-directed approach to reactive scheduling. Constraint analysis is used to prioritize outstanding problems in the current schedule, identify important modification goals, and estimate the possibilities for efficient and non-disruptive schedule modification. This information, in turn, provides a basis for selecting among a set of alternative modification actions, which differ in conflict resolution and schedule improvement capabilities, computational requirements and expected disruptive effects.
---
paper_title: Project scheduling : a research handbook

paper_content:

Scope and Relevance of Project Scheduling.- The Project Scheduling Process.- Classification of Project Scheduling Problems.- Temporal Analysis: The Basic Deterministic Case.- Temporal Analysis: Advanced Topics.- The Resource-Constrained Project Scheduling Problem.- Resource-Constrained Scheduling: Advanced Topics.- Project Scheduling with Multiple Activity Execution Modes.- Stochastic Project Scheduling.- Robust and Reactive Scheduling.
---
paper_title: Preselective strategies for the optimization of stochastic project networks under resource constraints

paper_content:

This article deals with a stochastic version of the optimization problem for project networks under resource constraints. In this, activity durations are assumed to be realized according to some joint probability distribution and the aim of optimization is to minimize the expected overall project cost (monotonically increasing with project duration). Certain strategies are known that constitute feasible solutions to this problem, the best studied of which are the so-called ES strategies (“earliest start” with regard to fixed project structures). In this paper, a considerably broader class of strategies is introduced, namely preselective strategies. It is shown that this generalization, for which an algorithmic approach remains possible, preserves almost all the desirable behavior known for ES strategies. In particular, the number of “essential” strategies remains finite and even minimal optimum-determining sets of such strategies can, in general, be characterized. Also, the analytic behavior is still proper and there is considerable “stability” to weak convergence of the joint distribution of activity durations as well as to a. e. convergence of the cost function. Last but not least, possible generalization to arbitrary regular cost functions is again imminent.
---
paper_title: Understanding Simulation Solutions to Resource Constrained Project Scheduling Problems with Stochastic Task Durations

paper_content:

AbstractThe project scheduling problem domain is an important research and applications area of engineering management. Recently introduced project scheduling software such as Risk+, @Risk for Project, SCRAM and Risk Master have facilitated the use of simulation to solve project scheduling problems with stochastic task durations. Practitioners, however, should be made aware that the solution algorithm used in these software systems is based on the implicit assumption of perfect information, an assumption that jeopardizes the feasibility of solution results. This paper discusses the impact of assuming perfect information, introduces a multi-period stochastic programming based model of the project scheduling problem with stochastic task durations, and presents an alternative simulation algorithm that does not assume the availability of perfect information. A simple case study is used to illustrate the practical implications of applying simulation to address project scheduling problems with stochastic task d...
---
paper_title: Scheduling tasks with AND/OR precedence constraints

paper_content:

In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. Such a task is called an AND task. The authors allow certain tasks, known as OR tasks, to be ready when just one of their predecessors is complete. They analyze the complexity of two types of real-time AND/OR task scheduling problems. In the first type of problem, all predecessors of every OR task must eventually be completed, but in the second type of problem, some OR predecessors may be left unscheduled. The authors present two priority-driven heuristic algorithms that may be used to schedule AND/OR task systems on m processors to minimize completion time, and analyze the worst-case performance of these algorithms. >
---
paper_title: Scheduling of project networks

paper_content:

The paper deals with the network optimization problem of minimizing regular project cost subject to an arbitrary precedence relation on the sets of activities and to arbitrarily many resource constraints. The treatment is done via a purely structural approach that considerably extends the disjunctive graph concept. It is based on so-called feasible posets and includes a quite deep and useful representation theorem. This theorem permits many insights concerning the analytical behaviour of the optimal value function, the description and counting of all essentially different optimization problems, the nature of Graham anomalies, connections with the on-line stochastic generalizations, and several others. In addition, it also allows the design of a quite powerful class of branch-and-bound algorithms for such problems, which is based on an iterative construction of feasible posets. Using so-called distance matrices, this approach permits the restriction of the exponential part of the algorithm to the often comparatively small set of ‘resource and cost essential’ jobs. The paper reports on computational experience with this algorithm for examples from the building industry and includes a rough comparison with the integer programming approach by Talbot and Patterson.
---
paper_title: Using tabu search to schedule activities of stochastic resource-constrained projects

paper_content:

Abstract In this paper, a higher level heuristic procedure “tabu search” is proposed to provide good solutions to resource-constrained, randomized activity duration project scheduling problems. Our adaptation of tabu search uses multiple tabu lists, randomized short-term memory, and multiple starting schedules as a means of search diversification. The proposed method proves to be an efficient way to find good solutions to both deterministic and stochastic problems. For the deterministic problems, most of the optimal schedules of the test projects investigated are found. Computational results are presented which establish the superiority of tabu search over the existing heuristic algorithms.
---
paper_title: Stochastic network project scheduling with non-consumable limited resources

paper_content:

Abstract This paper presents a newly developed resource constrained scheduling model for a PERT type project. Several non-consumable activity related resources, such as machines or manpower, are imbedded in the model. Each activity in a project requires resources of various types with fixed capacities. Each type of resource is in limited supply with a resource limit that is fixed at the same level throughout the project duration. For each activity, its duration is a random variable with given density function. The problem is to determine starting time values Sij for each activity (i,j) entering the project, i.e., the timing of feeding-in resources for that activity. Values Sij are not calculated beforehand and are random values conditional on our decisions. The model's objective is to minimize the expected project duration. Determination of values Sij is carried out at decision points when at least one activity is ready to be operated and there are free available resources. If, at a certain point of time, more than one activity is ready to be operated but the available amount of resources is limited, a competition among the activities is carried out in order to choose those activities which can be supplied by the resources and which have to be operated first. We suggest carrying out the competition by solving a zero-one integer programming problem to maximize the total contribution of the accepted activities to the expected project duration. For each activity, its contribution is the product of the average duration of the activity and its probability of being on the critical path in the course of the project's realization. Those probability values are calculated via simulation. Solving a zero-one integer programming problem at each decision point results in the following policy: the project management takes all measures to first operate those activities that, being realized, have the greatest effect of decreasing the expected project duration. Only afterwards, does the management take care of other activities. A heuristic algorithm for resource constrained project scheduling is developed. A numerical example is presented.
---
paper_title: Project Scheduling with Stochastic Activity Interruptions

paper_content:

In this chapter we address the problem of scheduling the activities of a resource-constrained project, some of which may be interrupted by an uncertain amount of time. The resources may be, for example, machines in a jobshop, computers with specialized software packages (as those needed for engineering designs), or highly specialized technicians.
---
paper_title: Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines

paper_content:

Abstract In this paper, we address the problem of minimizing expected total weighted tardiness of jobs that have stochastic interruptions and that are processed on a set of parallel machines. Our research generalizes the problem of scheduling parallel machines to minimize total weighted tardiness. The proposed solution method is based on the scatter search methodology and implements an innovative structured combination procedure. Extensive computational testing with more than 400 problem instances shows the merit of the proposed solution method.
---
paper_title: A Stochastic Branch-and-Bound Approach to Activity Crashing in Project Management

paper_content:

Many applications such as project scheduling, workflow modeling, or business process re-engineering incorporate the common idea that a product, task, or service consisting of interdependent time-related activities should be produced or performed within given time limits. In real-life applications, certain measures like the use of additional manpower, the assignment of highly-skilled personnel to specific jobs, or the substitution of equipment are often considered as means of increasing the probability of meeting a due date and thus avoiding penalty costs. This paper investigates the problem of selecting, from a set of possible measures of this kind, the combination of measures that is the most cost-efficient. Assuming stochastic activity durations, the computation of the optimal combination of measures may be very expensive in terms of runtime. In this article, we introduce a powerful stochastic optimization approach to determine a set of efficient measures that crash selected activities in a stochastic activity network. Our approach modifies the conventional Stochastic Branch-and-Bound, using a heuristic--instead of exact methods--to solve the deterministic subproblem. This modification spares computational time and by doing so provides an appropriate method for solving various related applications of combinatorial stochastic optimization. A comparative computational study shows that our approach not only outperforms standard techniques but also definitely improves conventional Stochastic Branch-and-Bound.
---
paper_title: Critical path planning under uncertainty

paper_content:

This paper concerns a CPM network in which individual job times are random variables. Specifically the time for each job consists of a component which is a linear function of the investment (up to some maximum) in that job and a random variable that is independent of the investment. It is desired to find the minimum investment required as a function of expected project completion time. The problem is solved by a cutting plane technique in which the investment allocations yield feasibility cuts. Because of the special structure of this problem, these cuts can be generated by solving a sequence of longest path problems in an acyclic network.
---
paper_title: Activity time-cost tradeoffs under time and cost chance constraints

paper_content:

We describe a stochastic extension of the critical path method time-cost tradeoff model. This extension includes four fundamental formulations of time-cost tradeoff models that represent different assumptions of the effect of the changing performance speed on the frequency distribution parameters of the activity duration, as well as the effect of the random activity duration on the activity cost. The formulations are based on clean fractile methods and therefore avoid the unfeasible necessity for additional groups of experts' estimates for each possible performance speed. Our formulations also enable us to consider both stochastic time and cost parameters. We developed several ideas for formulating the relationships between time-cost tradeoffs and two chance constraints for a single activity, the time chance constraint and the cost chance constraint. The developed formulas for multiobjective models can easily be incorporated into time-cost optimization procedures, thus enabling the procedures to optimize cost risks as well as time risks.
---
paper_title: A fuzzy set approach to activity scheduling for product development

paper_content:

Industries need to effectively manage their product development processes to reduce the product development time and cost. Due to incomplete design information at the early stage of product development, the duration of each activity is difficult to estimate accurately. The objective of this research is to develop a methodology to schedule product development projects having imprecise temporal information. The research problem is formulated as a fuzzy constraint satisfaction problem and a new method based on possibility theory is proposed to determine the satisfaction degrees of fuzzy temporal constraints. Based on the proposed method, a fuzzy scheduling procedure is developed to construct a schedule with the least possibility of being late and to maximize the satisfaction degrees of all fuzzy temporal constraints. Moreover, the computational efficiency of the proposed approach is also discussed. The proposed methodology can produce more satisfactory schedules in an uncertain product development environment.
---
paper_title: A fuzzy robust scheduling approach for product development projects

paper_content:

Abstract Efficient scheduling of a product development project is difficult, since a development project is usually unique in nature and high level of design imprecision exists at the early stages of product development. Moreover, risk-averse project managers are often more interested in estimating the risk of a schedule being late over all potential realizations. The objective of this research is to develop a robust scheduling methodology based on fuzzy set theory for uncertain product development projects. The imprecise temporal parameters involved in the project are represented by fuzzy sets. A measure of schedule robustness based on qualitative possibility theory is proposed to guide the search process to determine the robust schedule; i.e., the schedule with the best worst-case performance. A genetic algorithm approach is developed for solving the problem with acceptable performance. An example of electronic product development project is used to illustrate the concept developed.
---
paper_title: Uncertainty Modelling in Software Development Projects (With Case Study)

paper_content:

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.
---
paper_title: Stochastic Versus Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty

paper_content:

I. The General Framework.- 1. Multiobjective programming under uncertainty : scope and goals of the book.- 2. Multiobjective programming : basic concepts and approaches.- 3. Stochastic programming : numerical solution techniques by semi-stochastic approximation methods.- 4. Fuzzy programming : a survey of recent developments.- II. The Stochastic Approach.- 1. Overview of different approaches for solving stochastic programming problems with multiple objective functions.- 2. "STRANGE" : an interactive method for multiobjective stochastic linear programming, and "STRANGE-MOMIX" : its extension to integer variables.- 3. Application of STRANGE to energy studies.- 4. Multiobjective stochastic linear programming with incomplete information : a general methodology.- 5. Computation of efficient solutions of stochastic optimization problems with applications to regression and scenario analysis.- III. The Fuzzy Approach.- 1. Interactive decision-making for multiobjective programming problems with fuzzy parameters.- 2. A possibilistic approach for multiobjective programming problems. Efficiency of solutions.- 3. "FLIP" : an interactive method for multiobjective linear programming with fuzzy coefficients.- 4. Application of "FLIP" method to farm structure optimization under uncertainty.- 5. "FULPAL" : an interactive method for solving (multiobjective) fuzzy linear programming problems.- 6. Multiple objective linear programming problems in the presence of fuzzy coefficients.- 7. Inequality constraints between fuzzy numbers and their use in mathematical programming.- 8. Using fuzzy logic with linguistic quantifiers in multiobjective decision making and optimization: A step towards more human-consistent models.- IV. Stochastic Versus Fuzzy Approaches and Related Issues.- 1. Stochastic versus possibilistic multiobjective programming.- 2. A comparison study of "STRANGE" and "FLIP".- 3. Multiobjective mathematical programming with inexact data.
---
paper_title: Project scheduling : a research handbook

paper_content:

Scope and Relevance of Project Scheduling.- The Project Scheduling Process.- Classification of Project Scheduling Problems.- Temporal Analysis: The Basic Deterministic Case.- Temporal Analysis: Advanced Topics.- The Resource-Constrained Project Scheduling Problem.- Resource-Constrained Scheduling: Advanced Topics.- Project Scheduling with Multiple Activity Execution Modes.- Stochastic Project Scheduling.- Robust and Reactive Scheduling.
---
paper_title: A fuzzy project scheduling approach to minimize schedule risk for product development

paper_content:

The efficient management of product development projects is important to reduce the required development time and cost. However, each project is unique in nature and the duration of activities involed in a project often cannot be predicted accurately. The uncertainty of activity duration may lead to incorrect scheduling decisions. The objective of this research is to develop a fuzzy scheduling methodology to deal with this problem. Possibility theory is used to model the uncertain and flexible temporal information. The concept of schedule risk is proposed to evaluate the schedule performance. A fuzzy beam search algorithm is developed to determine a schedule with the minimum schedule risk and the start time of each activity is selected to maximize the minimum satisfaction degrees of all temporal constraints. In addition, the properties of schedule risk are also discussed. We show that the proposed methodology can assist project managers in selecting a schedule with the least possibility of being late in an uncertain scheduling environment. An example with an electronic product development project is used to illustrate the developed approach.
---
paper_title: Fuzzy project scheduling system for software development

paper_content:

Abstract This paper presents an FPS (Fuzzy Project Scheduling) decision support system applied to software project scheduling. The purpose of the FPS system is to allocate resources (software engineers) among dependent activities (system design, user interface design, modules implementation, modules integration and tests), taking into account one of two criteria: project completion time and maximum lateness, under uncertain time parameters of activities. By time parameters we understand durations, ready times and due dates of particular activities. Uncertainty of these parameters is modelled by means of L-R fuzzy numbers. A general procedure for transforming the fuzzy scheduling problem into a set of associate deterministic problems is based on the use of α-cuts. Optimistic and pessimistic schedules are heuristically generated for given α-levels. Aggregation of optimistic and pessimitic values of a minimized criterion for all α-levels gives a fuzzy result. Comparison of fuzzy result is based on a compensation of areas determined by the membership functions. The FPS system is described and its application to software project management is presented on a real example.
---
paper_title: Fuzzy priority heuristics for project scheduling

paper_content:

Abstract This paper presents a generalization of the known priority heuristic method for solving resource-constrained project scheduling problems (RCPS) with uncertain time parameters. The generalization consists of handling fuzzy time parameters instead of crisp ones. In order to create priority lists, a fuzzy ordering procedure has been proposed. The serial and parallel scheduling procedures which usually operate on these lists have also been extended to handle fuzzy time parameters. The performance of the method is presented on an example problem.
---
paper_title: Reactive Scheduling - Improving the Robustness of Schedules and Restricting the Effects of Shop Floor Disturbances by Fuzzy Reasoning

paper_content:

Abstract Practical scheduling usually has to reach to many unpredictable events and uncertainties in the production environment. Although often possible in theory, it is undesirable to reschedule from scratch in such cases. Since the surrounding organization will be prepared for the predicted schedule, it is important to change only those features of the schedule that are necessary. We show how, on one side, fuzzy logic can be used to support the construction of schedules that are robust with respect to changes due to certain types of event. On the other side, we show how a reaction can be restricted to a small environment by means of fuzzy constraints and a repair-based problem-solving strategy. We demonstrate the proposed representation and problem-solving method by introducing a scheduling application in a steelmaking plant. We construct a preliminary schedule by taking into account only the most likely duration of operations. This schedule is iteratively "repaired" until some threshold evaluation is found. A repair is found with a local search procedure based on Tabu Search. Finally, we show which events can lead to reactive scheduling and how this is supported by the repair strategy.
---
paper_title: On the optimal management of project risk

paper_content:

The uncertainty of project networks has been mainly considered as the randomness of duration of the activities. However, another major problem for project managers is the uncertainty due to the randomness of the amount of resources required by each activity which can be expressed by the randomness of its cost. Such randomness can seriously affect the discounted cost of the project and it may be strongly correlated with the duration of the activity.In this paper, a model considering the randomness of both the cost and the duration of each activity is introduced and the problem of project scheduling is studied in terms of the project's discounted cost and of the risk of not meeting its completion time. The adoption of the earliest (latest) starting time for each activity decreases (increases) the risk of delays but increases (decreases) the discounted cost of the project. Therefore, an optimal compromise has to be achieved. This problem of optimization is studied in terms of the probability of the duration and of the discounted cost of the project falling outside the acceptable domain (Risk function) using the concept of float factor as major decision variable. This last concept is proposed to help the manager to synthetize the large number of the decision variables representing each schedule for the studied project. Numerical results are also presented for a specific project network.
---
paper_title: ROBUSTNESS MEASURES AND ROBUST SCHEDULING FOR JOB SHOPS

paper_content:

Abstract A robust schedule is defined as a schedule that is insensitive to unforeseen shop floor disturbances given an assumed control policy. In this paper, a definition of schedule robustness is developed which comprises two components: post-disturbance make-span and post-disturbance makespan variability. We have developed robustness measures and robust scheduling methods for the case where a “right-shift” control policy is used. On occurrence of a disruption, the right-shift policy maintains the scheduling sequence while delaying the unfinished jobs as much as necessary to accommodate the disruption. An exact measure of schedule robustness is derived for the case in which only a single disruption occurs within the planning horizon. A surrogate measure is developed for the more complex case in which multiple disruptions may occur. This surrogate measure is then embedded in a genetic algorithm to generate robust schedules for job-shops. Experimental results show that robust schedules significantly outper...
---
paper_title: Enhancing real-time schedules to tolerate transient faults

paper_content:

We present a scheme to guarantee that the execution of real-time tasks can tolerate transient and intermittent faults assuming any queue-based scheduling technique. The scheme is based on reserving sufficient slack: in a schedule such that a task can be re-executed before its deadline without compromising guarantees given to other tasks. Only enough slack is reserved in the schedule to guarantee fault tolerance if at most one fault occurs within a time interval. This results in increased schedulability and a very low percentage of deadline misses even if no restriction is placed on the fault separation. We provide two algorithms to solve the problem of adding fault tolerance to a queue of real-time tasks. The first is a dynamic programming optimal solution and the second is a greedy heuristic which closely approximates the optimal.
---
paper_title: The Shifting Bottleneck Procedure for Job Shop Scheduling

paper_content:

We describe an approximation method for solving the minimum makespan problem of job shop scheduling. It sequences the machines one by one, successively, taking each time the machine identified as a bottleneck among the machines not yet sequenced. Every time after a new machine is sequenced, all previously established sequences are locally reoptimized. Both the bottleneck identification and the local reoptimization procedures are based on repeatedly solving certain one-machine scheduling problems. Besides this straight version of the Shifting Bottleneck Procedure, we have also implemented a version that applies the procedure to the nodes of a partial search tree. Computational testing shows that our approach yields consistently better results than other procedures discussed in the literature. A high point of our computational testing occurred when the enumerative version of the Shifting Bottleneck Procedure found in a little over five minutes an optimal schedule to a notorious ten machines/ten jobs problem on which many algorithms have been run for hours without finding an optimal solution.
---
paper_title: Predictable scheduling of a job shop subject to breakdowns

paper_content:

Schedule modification may delay or render infeasible the execution of external activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules which can absorb disruptions without affecting planned external activities, while maintaining high shop performance. We present a predictable scheduling approach where the predictive schedule is built with such objectives. The procedure inserts additional idle time into the schedule to absorb the impacts of breakdowns. The amount and location of the additional idle time is determined from the breakdown and repair distributions as well as the structure of the predictive schedule. The effects of disruptions on planned support activities are measured by the deviations of job completion times in the realized schedule from those in the predictive schedule. We apply our approach to minimizing maximum lateness in a job shop environment with random machine breakdowns, and show that it provides high predictability with minor sacrifices in shop performance.
---
paper_title: On the optimal management of project risk

paper_content:

The uncertainty of project networks has been mainly considered as the randomness of duration of the activities. However, another major problem for project managers is the uncertainty due to the randomness of the amount of resources required by each activity which can be expressed by the randomness of its cost. Such randomness can seriously affect the discounted cost of the project and it may be strongly correlated with the duration of the activity.In this paper, a model considering the randomness of both the cost and the duration of each activity is introduced and the problem of project scheduling is studied in terms of the project's discounted cost and of the risk of not meeting its completion time. The adoption of the earliest (latest) starting time for each activity decreases (increases) the risk of delays but increases (decreases) the discounted cost of the project. Therefore, an optimal compromise has to be achieved. This problem of optimization is studied in terms of the probability of the duration and of the discounted cost of the project falling outside the acceptable domain (Risk function) using the concept of float factor as major decision variable. This last concept is proposed to help the manager to synthetize the large number of the decision variables representing each schedule for the studied project. Numerical results are also presented for a specific project network.
---
paper_title: Robust scheduling of a two-machine flow shop with uncertain processing times

paper_content:

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance.
---
paper_title: Robust Discrete Optimization and Its Applications

paper_content:

Preface. 1. Approaches to Handle Uncertainty In Decision Making. 2. A Robust Discrete Optimization Framework. 3. Computational Complexity Results of Robust Discrete Optimization Problems. 4. Easily Solvable Cases of Robust Discrete Optimization Problems. 5. Algorithmic Developments for Difficult Robust Discrete Optimization Problems. 6. Robust 1-Median Location Problems: Dynamic Aspects and Uncertainty. 7. Robust Scheduling Problems. 8. Robust Uncapacitated Network Design and International Sourcing Problems. 9. Robust Discrete Optimization: Past Successes and Future Challenges.
---
paper_title: Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production

paper_content:

Schedulers confronted with significant processing time uncertainty often discover that a schedule which is optimal with respect to a deterministic or stochastic scheduling model yields quite poor performance when evaluated relative to the actual processing times. In these environments, the notion of schedule robustness, i.e., determining the schedule with the best worst-case performance compared to the corresponding optimal solution over all potential realizations of job processing times, is a more appropriate guide to schedule selection. In this paper, we formalize the robust scheduling concept for scheduling situations with uncertain or variable processing times. To illustrate the development of solution approaches for a robust scheduling problem, we consider a single-machine environment where the performance criterion of interest is the total flow time over all jobs. We define two measures of schedule robustness, formulate the robust scheduling problem, establish its complexity, describe properties of the optimal schedule, and present exact and heuristic solution procedures. Extensive computational results are reported to demonstrate the efficiency and effectiveness of the proposed solution procedures.
---
paper_title: RanGen: A Random Network Generator for Activity-on-the-Node Networks

paper_content:

In this paper, we describe RanGen, a random network generator for generating activity-on-the-node networks and accompanying data for different classes of project scheduling problems. The objective is to construct random networks which satisfy preset values of the parameters used to control the hardness of a problem instance. Both parameters which are related to the network topology and resource-related parameters are implemented. The network generator meets the shortcomings of former network generators since it employs a wide range of different parameters which have been shown to serve as possible predictors of the hardness of different project scheduling problems. Some of them have been implemented in former network generators while others have not.
---
paper_title: On the construction of stable project baseline schedules

paper_content:

The vast majority of project scheduling efforts assume complete information about the scheduling problem to be solved and a static deterministic environment within which the pre-computed baseline schedule will be executed. In reality, however, project activities are subject to considerable uncertainty, which generally leads to numerous schedule disruptions. It is of interest to develop pre-schedules that can absorb disruptions in activity durations without affecting the planning of other activities, such that co-ordination of resources and material procurement for each of the activities can be performed as smoothly as possible. The objective of this paper is to develop and evaluate various approaches for constructing a stable preschedule, which is unlikely to undergo major changes when it needs to be repaired as a reaction to minor activity duration disruptions.
---
paper_title: β-Robust scheduling for single-machine systems with uncertain processing times

paper_content:

In scheduling environments with processing time uncertainty, system performance is determined by both the sequence in which jobs are ordered and the actual processing times of jobs. For these situations, the risk of achieving substandard system performance can be an important measure of scheduling effectiveness. To hedge this risk requires an explicit consideration of both the mean and the variance of system performance associated with alternative schedules, and motivates a β-robustness objective to capture the likelihood that a schedule yields actual performance no worse than a given target level. In this paper we focus on β-robust scheduling issues in single-stage production environments with uncertain processing times. We define a general β-robust scheduling objective, formulate the β-robust scheduling problem that results when job processing times are independent random variables and the performance measure of interest is the total flow time across all jobs, establish problem complexity, and develop exact and heuristic solution approaches. We then extend the β-robust scheduling model to consider situations where the uncertainty associated with individual job processing times can be selectively controlled through resource allocation. Computational results are reported to demonstrate the efficiency and effectiveness of the solution procedures.
---
paper_title: A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes

paper_content:

Abstract In this paper, a polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints, general precedence relations and multiple modes is proposed. Insertion objective is to minimize the resulting impact on maximum lateness, while keeping some essential characteristics of the initial schedule. A new disjunctive arc-based representation with multiple capacities associated to resource arcs is proposed. Under specific constraints, some simple dominance rules allow to find an optimal insertion position in the digraph with low-computational requirements.
---
paper_title: Scheduling independent tasks to reduce mean finishing time

paper_content:

Sequencing to minimize mean finishing time (or mean time in system) is not only desirable to the user, but it also tends to minimize at each point in time the storage required to hold incomplete tasks. In this paper a deterministic model of independent tasks is introduced and new results are derived which extend and generalize the algorithms known for minimizing mean finishing time. In addition to presenting and analyzing new algorithms it is shown that the most general mean-finishing-time problem for independent tasks is polynomial complete, and hence unlikely to admit of a non-enumerative solution.
---
paper_title: Stability and resource allocation in project planning

paper_content:

The majority of resource-constrained project scheduling efforts assume perfect information about the scheduling problem to be solved and a static deterministic environment within which the precomputed baseline schedule is executed. In reality, project activities are subject to considerable uncertainty, which generally leads to numerous schedule disruptions. In this paper, we present a resource allocation model that protects a given baseline schedule against activity duration variability. A branch-and-bound algorithm is developed that solves the proposed resource allocation problem. We report on computational results obtained on a set of benchmark problems.
---
paper_title: RanGen: A Random Network Generator for Activity-on-the-Node Networks

paper_content:

In this paper, we describe RanGen, a random network generator for generating activity-on-the-node networks and accompanying data for different classes of project scheduling problems. The objective is to construct random networks which satisfy preset values of the parameters used to control the hardness of a problem instance. Both parameters which are related to the network topology and resource-related parameters are implemented. The network generator meets the shortcomings of former network generators since it employs a wide range of different parameters which have been shown to serve as possible predictors of the hardness of different project scheduling problems. Some of them have been implemented in former network generators while others have not.
---
paper_title: Criticality in Resource Constrained Networks

paper_content:

Project managers readily adopted the concept of the critical path as an aid to identifying those activities most worthy of their attention and possible action. However, current project management packages do not offer a useful measure of criticality in resource constrained projects. A revised method of calculating resource constrained float is presented, together with a discussion of its use in project management. While resource constrained criticality appears to be a practical and useful tool in the analysis of project networks, care is needed in its interpretation as any calculation of such float is conditional on the particular resource allocation employed. A number of other measures of an activity's importance in a network are described and compared in an application to an aircraft development. A quantitative comparison of the measures is developed based on a simulation of the process of management identifying the key activities and directing their control efforts. Resource constrained float appears to be a useful single measure of an activity's importance, encapsulating several useful pieces of management information. However, there are some circumstances in which other measures might be preferred.
---
paper_title: A new method for workshop real time scheduling

paper_content:

Workshop real time scheduling is one of the key factors in improving manufacturing system efficiency. This is especially true for workshops in which various products are processed simultaneously, and use multipurpose machines. Real time scheduling is appropriate to handle perturbations in the environment of the manufacturing process, a major issue at the shop floor level. The products to be processed have release times and due dates and the resources are multipurpose machines. A decision support system for real time scheduling is described. It is based on an original approach, aiming at searching for characteristics of a set of schedules compatible with the main manufacturing constraints to be satisfied. This set of schedules is obtained by defining sequences of groups of permutable operations for every resource. A method to find such a set is described. We emphasize the use of this group sequence as a decision support system. Significant states and events requiring real time decisions are identified and ...
---
paper_title: Characterization of a set of schedules in a multiple resource context

paper_content:

ABSTRACT For real time scheduling, a decision aid approach, based on the characterization of a set of schedules compatible with the problem constraints, is proposed. This set is specified in terms of sequences of permutable operations on the resources. Generating such a group sequence is described for the scheduling problem where products have to be performed according to a specified routeing with release times and due dates. Each product operation requires a set of resources, each of them being selected inside a pool of several resources.
---
paper_title: Sensitivity analysis of scheduling algorithms

paper_content:

Abstract We are interested in this work in studying the performances of static scheduling policies in presence of on-line disturbances. In the general case, the sensitivity of the schedules, i.e., the degradation of the performance of the solution due to the disturbances, is linear in the magnitude of the perturbation. Our main result within this paper is to show that in some scheduling contexts, namely the case of independent tasks, the sensitivity can be guaranteed not to exceed the square root of the magnitude of the perturbation.
---
paper_title: A new method for workshop real time scheduling

paper_content:

Workshop real time scheduling is one of the key factors in improving manufacturing system efficiency. This is especially true for workshops in which various products are processed simultaneously, and use multipurpose machines. Real time scheduling is appropriate to handle perturbations in the environment of the manufacturing process, a major issue at the shop floor level. The products to be processed have release times and due dates and the resources are multipurpose machines. A decision support system for real time scheduling is described. It is based on an original approach, aiming at searching for characteristics of a set of schedules compatible with the main manufacturing constraints to be satisfied. This set of schedules is obtained by defining sequences of groups of permutable operations for every resource. A method to find such a set is described. We emphasize the use of this group sequence as a decision support system. Significant states and events requiring real time decisions are identified and ...
---
paper_title: Stochastic network project scheduling with non-consumable limited resources

paper_content:

Abstract This paper presents a newly developed resource constrained scheduling model for a PERT type project. Several non-consumable activity related resources, such as machines or manpower, are imbedded in the model. Each activity in a project requires resources of various types with fixed capacities. Each type of resource is in limited supply with a resource limit that is fixed at the same level throughout the project duration. For each activity, its duration is a random variable with given density function. The problem is to determine starting time values Sij for each activity (i,j) entering the project, i.e., the timing of feeding-in resources for that activity. Values Sij are not calculated beforehand and are random values conditional on our decisions. The model's objective is to minimize the expected project duration. Determination of values Sij is carried out at decision points when at least one activity is ready to be operated and there are free available resources. If, at a certain point of time, more than one activity is ready to be operated but the available amount of resources is limited, a competition among the activities is carried out in order to choose those activities which can be supplied by the resources and which have to be operated first. We suggest carrying out the competition by solving a zero-one integer programming problem to maximize the total contribution of the accepted activities to the expected project duration. For each activity, its contribution is the product of the average duration of the activity and its probability of being on the critical path in the course of the project's realization. Those probability values are calculated via simulation. Solving a zero-one integer programming problem at each decision point results in the following policy: the project management takes all measures to first operate those activities that, being realized, have the greatest effect of decreasing the expected project duration. Only afterwards, does the management take care of other activities. A heuristic algorithm for resource constrained project scheduling is developed. A numerical example is presented.
---

Title: Project scheduling under uncertainty: Survey and research potentials

Section 1: Introduction
Description 1: Introduce the context and importance of project scheduling, highlighting the challenges and sources of uncertainty.

Section 2: Reactive Scheduling
Description 2: Discuss the strategies for revising or re-optimizing baseline schedules in response to unexpected events.

Section 3: Generating a Baseline Schedule
Description 3: Outline the approaches for developing baseline schedules, including considerations for variability and robustness.

Section 4: Stochastic Project Scheduling
Description 4: Provide an overview of the literature and methodologies for scheduling under stochastic conditions, focusing on resource-constrained problems and scheduling policies.

Section 5: Scheduling Policies
Description 5: Explain different scheduling policies used in stochastic project scheduling to handle uncertainties in activity durations.

Section 6: Stochastic Activity Interruptions
Description 6: Discuss the methodologies for handling interruptions and time/cost trade-offs in a stochastic environment.

Section 7: Fuzzy Project Scheduling
Description 7: Describe the use of fuzzy set theory to model activity durations under imprecision rather than uncertainty.

Section 8: Proactive (Robust) Project Scheduling
Description 8: Examine techniques for constructing robust schedules that can withstand uncertainties.

Section 9: Redundancy-Based Techniques
Description 9: Discuss the application of redundancy, either in resources or time, to enhance schedule robustness.

Section 10: Robust Machine Scheduling Techniques
Description 10: Explore robust scheduling methods and their applications in machine scheduling, highlighting potential adaptations for project environments.

Section 11: Sensitivity Analysis
Description 11: Review the methods for analyzing schedule sensitivity to parameter changes and their relevance to project scheduling.

Section 12: Summary and Suggestions for Further Research
Description 12: Summarize the findings and suggest directions for future research in project scheduling under uncertainty.