Deterministic scheduler

Fig. 9.4 Deterministic scheduler sequence of decisions and results for all scenarios (average objective after three periods P = —16.05).

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. 

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. 

The research in deterministic scheduling problems has followed a number of different directions (see Pinedo 1995). Three areas have received considerable attention ... 

Since the ARINC 653 specification was published, the Ravenscar profile (Bums, Dobbing and Romanski 1998) has been produced for Ada tasking. The Ravenscar Profile is a subset of the Ada tasking model that is deterministic, schedulable and memory-bounded. It was designed specifically to support the development of safety-critical, hard-real-time Ada programs. 

The deterministic scheduling model is formulated as a MILP problem based on a batch slot concept. With this formulation, the time horizon is viewed as a sequence of batches, each of which will be assigned to one particular product. The proposed mathematical model is shown in equations (1) to (13). It maximises the expected profit (sales -inventory costs - production shortfalls) using X(b,p) as sequencing decision variable (see Nomenclature). A small penalty term on the sum of the initial time of all batches is added to force the schedule to finish in the smallest makespan possible. 

Figure 1. Risk curves from the stochastic and deterministic schedules.

In last decade, many authors have recognized that it is unlikely to apply deterministic schedules in real scenarios without significantly reducing their performance, and have made efforts to expand the deterministic approaches to situations with uncertainty, in order to obtain better results when their solutions are deployed in real scenarios. Here, the S-graph deterministic framework is extended for solving production scheduling problems under uncertainty in demand. 

A new approach for solving scheduling problems under exogenous uncertainty has been presented. The approach is based on the S-graph framework which has proven to be a rigorous and efficient tool for solving deterministic scheduling problems. 

For most applications the makespan criterion is applied. For a very heavy load of the plant, the tardiness might be the most appropriate criterion that will enable to keep delivery dates undue. No matter which criterion is used, scheduling is always a problem of combinatorial character a large number of sequences must be simulated and the best combination chosen. Contrary to production planning, the problem of optimal scheduling is considered to be deterministic and static. This means that all problem parameters are known in advance and remain unchanged during the realization of the schedule. 

The use of uncertainty conscious schedulers - schedulers which consider the uncertain parameters already at the scheduling stage - have the potential to lead to a significant increase in the profit compared to deterministic methods. However, the resulting optimization problems are usually of large scale and it is difficult to solve them within the short period of time available in a real-time environment. 

In order to investigate the performance of a deterministic online scheduler, we apply it to the example problem under demand uncertainty for three periods. The model of the scheduling problem used in the scheduler considers a prediction horizon of H = 2 periods. Only the current production decision Xi(ti) is applied... 

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.8 Deterministic vs. stochastic scheduler comparison of the objective after three periods.

A recent and very promising application of the reachability analysis of TA is scheduling. This development, however, required the introduction of the notion of cost. In contrast to the verification of whether a behavior fulfills a specification or not, costs introduce a quantitative measure to evaluate the individual behaviors. Successful applications of priced TA [15, 16] by using the standard and a special version of Uppaal are documented in [17-19]. The first application to deterministic job-shop scheduling was published by Abdeddaim [20] and Abdeddaim and Maler [21], In order to further motivate the use of TA, the next section shows how the schedule in Figure 10.2 and the plant on which the operations are scheduled naturally translate into a set of timed automata. 

The above model consists of two main parts a scheduler and the plant to schedule. Since the scheduler defines exactly when to start and finish the tasks, the behavior of the entire system is deterministic. Running both parts, the scheduler and the plant, corresponds to a simulation in which one single behavior of the composed system is obtained. Obviously, this situation requires the presence of a scheduler which knows the (optimal) schedule. If such a scheduler is absent, then the resource automata in the plant receive no signals. Scheduling of a plant can be understood as the task of finding a scheduler automaton which provides the optimal schedule with respect to an optimization criterion. In the sequel it is assumed that a scheduler does not exist and the automata model is designed as shown in Figure 10.4. 

None of preventive maintenance planning models considers constraints on resources available in process plants, which include labor and materials (spare parts). For example, the maintenance work force, which is usually limited, cannot perform scheduled PM tasks for some equipments at scheduled PM time because of the need to repair other failed equipments. Such dynamic situations can not be handled by deterministic maintenance planning models or are not considered in published maintenance planning models that use Monte Carlo simulation tools. 

Each work package in the WBS is decomposed into the activities required to complete its predefined scope. A list of activities is constructed and the time to complete each activity is estimated. Estimates can be deterministic (point estimates) or stochastic (distributions). Precedence relations among activities are defined, and a model such as a Gantt chart, activity on arc (AOA), or activity on nodes (AON) network is constructed (Shtub et al. 1994). An initial schedule is developed based on the model. This unconstrained schedule is a basis for estimating required resources and cash. Based on the constraint imposed by due dates, cash and resource avaUabUity, and resource requirements of other projects, a constrained schedule is developed. Further tuning of the schedule may be possible by changing the resource combination assigned to activities (these resource combinations are known as modes). 

---