Order scheduling problem formulation

This section explains the formulation of the order scheduling problem in an order-based manufacturing factory. Production processes of each order should be performed in different types of shop floors respectively. Each type of shop floor comprises one or more assembly lines. According to a pre-determined production flow, production processes involved in each order must be completed on an assembly line of the corresponding shop floor. For simplicity, we assume that there is no work in progress (WIP) in each shop floor. 

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. 

Simple heuristics such as the five described above provide adequate results only for the simplest scheduling problems. Real-world scheduling problems usually require techniques that are significantly more sophisticated than a myopic priority rule that just orders the jobs according to a function of one or two parameters. There are various ways of formulating scheduling problems as well as various types of solution procedures. These are discussed next. 

In [4], we have proposed an Integer Linear Programming(ILP) formulation for the time-constrained scheduling problem. Since we use the As-Soon-As-Possible(ASAP) and As-Late-As-Possible(ALAP) scheduling techniques to reduce the solution space, the ILP formulation is very efficient and able to optimally solve practical problems, such as the fifth order elliptic filter[10], in a few seconds. 

This paper has addressed the optimal periodic scheduling of an industrial batch plant from a new perspective. The aim has been to select a convenient number of equipment units so as to rninirnize the total equipment allocation cost and hence achieve a trade-off between a low makespan and high free capacity. A decomposition method based on a Resource-Task Network discrete-time formulation has been proposed that, when compared to the solution of the full problem, was able to reduce the total computational effort by one order of magnitude without severely compromising optimality. 

First the problem was solved with an MILP formulation, i.e. without resorting to dividing any order. Makespan was considered as a constraint and an optimum schedule, with an objective function value of 81.4 days and a completion time of 26.25 days, was found. However, the results, as shown in Figure 2a, indicated that dividing the order 6 would have resulted in even better optimal solution in terms of fulfilling a possible customer demand of earlier completion of the set of orders. 

---