Review of Scheduling Models

Having introduced a general road map for classifying problems and models for batch scheduling we present a brief review on the specific models that have been proposed in the literature (for model details see Mendez et al. [6]).  

The most relevant contribution for global discrete time models is the State Task Network representation proposed by Kondili et al. [7] and Shah et al. [8] (see also [9]). The model involves 0-1 variables for allocating tasks to processing units at the beginning of the postulated time intervals. Most important equations comprise mass balances over the states, constraints on batch sizes and resource constraints. The STN model covers all the features that are included at the column on discrete time in Table 8.1. 

A simpler and general discrete time scheduling formulation can also be derived by means of the Resource Task Network concept proposed by Pantelides [10], The major advantage of the RTN formulation over the STN counterpart arises in some problems involving many identical pieces of equipment. In these cases, the RTN formulation introduces a single binary variable instead of the multiple variables used by the STN model. The RTN-based model also covers all the features at the column on discrete time in Table 8.1. In order to deal with different types of resources in a uniform way, this approach requires only three different classes of constraints in terms ofthree types of variables defining the task allocation, the batch size, and the resource availability. Briefly, this model reduces the batch scheduling problem to a simple resource balance problem carried out in each predefined time period. 

We can then conclude that while the discrete time STN and RTN models are quite general and effective in monitoring the level of limited resources at the fixed times, their major weakness in terms of capability is the handling of relatively small processing and changeover times. Regarding the objective function, these models can easily handle profit maximization (cost minimization) for a fixed time horizon. Intermediate due dates can be easily modeled. Other objectives such as makespan minimization are more complex to implement since the time horizon and, in consequence, the number of time intervals, are unknown a priori (see [11]). 

Different continuous-time formulations were also developed based on the RTN concept initially proposed by Pantelides [10]. The work developed by Castro et al. [18] which has been improved by Castro et al. [19] falls into this group. Major assumptions of this approach are (1) processing units are considered individually, i.e., one resource is defined for each available unit, and (2) only one task can be 

---