Stochastic scheduler

In the first part of this chapter (Section 9.2), we present an uncertainty conscious scheduling approach that combines reactive scheduling and stochastic scheduling by using a moving horizon scheme with an uncertainty conscious model. In this approach, it is assumed that decisions are made sequentially and that the effect of the revealed uncertainties can be partially compensated by later decisions. The sequence of decisions and observations is modeled by a sequence of two-stage stochastic programs. 

The moving horizon scheme using the two-stage model is shown in Figure 9.6. In contrast to the deterministic scheduler which uses the expected value of the demands dls and ds i (see Section 9.2.2), the stochastic scheduler updates the demand in form of the distribution given in Table 9.1 d, df, d]+1, and dj+1. 

The sequence of decisions obtained from the stochastic scheduler for all possible evolutions of the demand for the three periods is provided in Figure 9.7. The sequence of decisions obtained by the stochastic scheduler differs from that obtained by the deterministic one, e.g., xi(ti) = lOinstead ofxi(ti) = 6. The average objective for the stochastic scheduler after three periods is P = —17.65. 

The performance ofthe deterministic and of the stochastic scheduler is compared in Figure 9.8. The figure shows the objective for all scenarios and the average objective. The stochastic scheduler improves the average objective by approximately 10% and for five out of eight scenarios. On the other hand, the stochastic scheduler produces a larger variation in the objective of the scenarios. 

Fig. 9.7 Stochastic scheduler sequence of decisions and results for all scenarios (average objective after three periods P = —17.65), compare to Figure 9.4.

Fig. 9.8 Deterministic vs. stochastic scheduler comparison of the objective after three periods.

In the previous section it was shown that the performance of a scheduler can be significantly improved by the use of stochastic models. In this section, we present the mathematical models that represent two-stage stochastic scheduling problems and algorithmic approaches to the optimization of the schedules. 

An uncertainty conscious scheduling approach for real-time scheduling was presented in this chapter. The approach is based on a moving horizon scheme where in each time period a two-stage stochastic program is solved. For the investigated example it was found that the stochastic scheduler improved the objective on average by 10% compared to a deterministic scheduler. 

In this section, the framework proposed for solving stochastic scheduling problems is described. It basically consists in a systematic search strategy based on the schedule generator (S-graph) and the expected performance evaluator (LP Model). The algorithm flowsheet is presented in Fig. 8.4. 

Bohnenkamp, H.C., Hermanns, H., Klaren, R. et al. (2004, September) Synthesis and stochastic assessment of schedules for lacquer production. Proceedings of QEST 04, LNCS. 

Figure 6.10 shows the data flow of the software tool BayAPS PP for optimal capacity assignment for given stochastic demands. Transaction data about demand and inventories is typically imported from SAP R/3 as indicated, production capacity master data and side conditions are stored in the software tool. Forecasts can be taken from a forecast tool or from SAP R/3. The output ofthe tool is a list ofpriorities of products and their lot sizes, which are optimal based on the presently available information. Only the next production orders are realized before the computation is repeated, and the subsequently scheduled production is only a prediction. 

Sand, G. and Engell, S. (2003) Modeling and solving real-time scheduling problems by stochastic integer programming. Comput. Chem. Eng., 28, 1087-1103. 

Uncertainty Conscious Scheduling by Two-Stage Stochastic Optimization... 

The performance of the scheduler can be significantly improved by the use of a stochastic model. The stochastic model used here considers not only the probability distribution of the uncertain parameters but also the structure of decisions and observations that result from the moving horizon scheme. 

Some of the production decisions of the aggregated scheduling problem are provided to the detailed scheduler. These decisions have to be taken before any observation of the outcome of the uncertain parameters is available. Thus, they correspond to the first-stage decisions of the two-stage stochastic problem. Consequently, the vector of first-stage decisions x consists of all production decisions of the short-term horizon N >rp and Zy, for i e 1,..., If. ... 

---