Optimal schedule

The algorithms of solving the task of creating an optimal schedule of measurement are discussed. In addition, they are realized in the software package OPTIMIZM. 

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. 

In fact, no model can represent every aspect of an actual production process. Accordingly, the. scheduler must have some flexibility to modify the schedule proposed by the optimization algorithm, based on experience that is gained al.so at the realization of the optimal schedule. This leads to evolutionary improvement strategies starting from approximate optimization techniques. An interactive graphical presentation of the plant should enable quick intervention. 

Optimal schedules are given in Table 7.4-20. Clearly, for cleaning times of five hours, single-product campaigns are the best solution of the scheduling problem, while for zero cleaning times (theoretical case) mixed-product campaigns would be best. 

Zhang, X., 1995. Algorithms for optimal scheduling using nonlinear models. PhD thesis, University of London, London. 

In a situation where scheduling is not given beforehand, time is treated as an optimisation variable to provide a truly optimal schedule for freshwater demand and wastewater generation. The problem, in this particular case, can be stated as follows. Given the aforementioned (i)-(v ) conditions for each water using operation as well as ... 

Papageorgiou, L.G., Shah, N., Pantelides, C.C., 1994. Optimal scheduling of heat-integrated multipurpose plants. Ind. Eng. Chem. Res., 33 3168-3186 Peneva, K., Ivanov, B., Bancheva, N., 1992. Heat integration of batch vessels at fixed time interval. 

Mendez, C.A., Henning, G.P. and Cerda, J. (2000) Optimal scheduling of batch plants satisfying multiple product orders with different due-dates. Comput. Chem. Eng., 24, 2223-2245. 

Fig. 10.2 The Gantt chart of the optimal schedule for the example process.

We define the following parameters for the example process B0 = Bi = B2 = B3 = B4 = 20 d = d2 = 3 d3 = 2 b = 10 b2 = bz = 4. The initial amount of Si is 20 units and the goal of the production is to produce 8 units of S3 and 12 units of S4. The optimal schedule with respect to the makespan (the overall production time) is shown in Figure 10.2. Each occurrence of a task in the schedule is called an operation and the number of operations must be determined by the scheduler. The schedule in Figure 10.2 is obviously valid because it satisfies the requirements from Section 10.1.3. It is also optimal, because none of the operations can be shifted to the left to reduce the makespan which is determined by the last operation of T3. In the optimal schedule, 2 operations of both, T1 and T2, as well as 3 operations of T3 are necessary to meet the market demand. The optimal makespan is 10 and all raw and intermediate materials have been processed without overproduction of final products. 

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. 

Each valid evolution starts in a predefined initial state in which sufficient quantities of the raw materials are given. Furthermore, it must meet the requirements from Section 10.1.3. A schedule will be accepted only if the market demand has been satisfied. Hence, at the end of the evolution, the demanded quantities of final products must be present in the storages. Each evolution which does not satisfy the above requirements leads to an invalid schedule and thus must be rejected. In order to synthesize a valid and optimal schedule, the scheduler has to fix all degrees of freedom by choosing appropriate signals for the resource automata. A valid and optimal schedule corresponds to evolutions which minimize a given optimality criterion. 

In the context of reachability analysis, this graph is called symbolic reachability graph of the automaton A and can be searched using shortest path search techniques as widely used in computer science. Hence, the task of finding the cost-optimal schedule is to find the shortest (or cheapest) path in a (priced) symbolic reachability graph. 

Behrmann, G., Larsen, K.G. and Rasmussen, (.1. (2005b) Optimal scheduling using priced timed automata. ACM Sigmelric, 32(4), 34 40. 

Rasmussen, J.I., Larsen, K.G. and Sub-ramani, K. (2004) Resource-Optimal Scheduling Using Priced Timed Automata. Proceedings of TACAS 04, Springer, London. 

EXAMPLE 1.5 OPTIMAL SCHEDULING FORMULATION OF THE OPTIMATION PROBLEM... 

Murray, J. E. and T. F. Edgar. Optimal Scheduling of Production and Compression in Gas Fields. J Petrol Technol 109-118 (January, 1978). 

Mokashi, S. D. and A. Kokossis. The Maximum Order Tree Method A New Approach for the Optimal Scheduling of Product Distribution Lines. Comput Chem Eng 21 S679-684 (1997). 

An experimental design approach was also used in Reference 26 for the chiral analysis of amino acid derivatives. The screening and optimization schedule followed... 

---