Scheduling

• J.R. Birge and M.A.H. Dempster, "Optimal Match-Up Strategies in Stochastic Scheduling", Discrete Applied Mathematics 57 (1995) 105-120.

  Abstract

  Practical scheduling problems require the consideration of random events that may affect planned starting and completion times. In general, these problems are quite difficult to analyze. In a previous paper, general conditions were, however, developed for turnpike optimal strategies and the asymptotic optimality of strategies that match up with a turnpike strategy. In this paper, we present examples of these models, comparisons with deterministic approaches, and discuss implications for practical scheduling.

• M.J. Maddox and J.R. Birge, "Bounds on the Distribution of Tardiness in PERT Networks," Technical Report, Department of Industrial and Operations Engineering, University of Michigan.

  Abstract

  Project activity durations are most often random. Frequently, fixed penalties occur when the project exceeds the deadline and other post-deadline dates. The costs are due to contractual clauses or fixed costs of expedition. We consider fixed tardiness costs incurred if a project is more than $\alpha$ time units tardy. The expected cost of this delay is the fixed cost times the probability the project tardiness is greater than $\alpha$. Our interest is, therefore, in calculating this probability of $\alpha$ time units of delay. Because the project completion time is the maximum of a number of possibly dependent random variables, exactly calculating this probability is difficult. The problem is further complicated because there is often only incomplete information on the distributions of the random activity durations.

• J.R. Birge and M.A.H. Dempster, " Stochastic Programming Approaches to Stochastic Scheduling," Technical Report 95-12, Department of Industrial and Operations Engineering, University of Michigan.

  Abstract

  Scheduling problems typically require decisions without full information about the outcomes of those decisions. Yields, resource availability, performance, demand, costs, and revenues may all vary. Incorporating these quantities into stochastic scheduling models often produces difficulties in analysis that may be addressed in a variety of ways. In this paper, we present results based on stochastic programming approaches to the hierarchy of decisions in typical stochastic scheduling situations. Our unifying framework allows us to treat all aspects of a decision in a similar framework. We show how views from different levels enable approximations that can overcome nonconvexities and duality gaps that appear in deterministic formulations. In particular, we show that the stochastic program structure leads to a vanishing Lagrangian duality gap in stochastic integer programs as the number of scenarios increases.
• M.J. Maddox and J.R. Birge, "Using Second Moment Information in Stochastic Scheduling," Technical Report TR 96-1, Department of Industrial and Operations Engineering, University of Michigan, December 1995. (postscript)
• J.R. Birge and K.D. Glazebrook, "Bounds on Optimal Values in Stochastic Scheduling," Technical Report TR 96-2, Department of Industrial and Operations Engineering, University of Michigan, February 1996, revised January 1997. (pdf)