Page 182 - Sustainability in the process industry

Pro c ess O p timization F r ame w ork s 159

7.3 Scheduling of Batch Processes: S-Graphs

7.3.1 Scheduling Frameworks: Suitability and Limitations
Scheduling problems arise in many various areas, including chemical
engineering, supply chain management, operating systems design,
or train timetable design. The terminology and details vary among
the different types of applications, but the core of scheduling remains
the same: assigning tasks to resources at time intervals that satisfy
predefined conditions. The goal is usually to find a feasible schedule
that performs better—in terms of a particular objective—than any
alternative.
One of the first contributions to scheduling of chemical processes
by Mathematical Programming was the paper by Kondili, Pantelides,
and Sargent (1993). These authors developed the state task network
(STN) representation in order to formulate production scheduling
in multipurpose plants as a MILP problem. Pantelides (1993) also
developed the resource task network (RTN) representation, which
employs a uniform treatment for all available resources. Originally,
the time representation in the formulations are discrete—in other
words, a certain number of predefined times on the time horizon can
be considered in the schedule. Zhang and Sargent (1996) extended the
formulation to accommodate continuous-time representation, where
the time points may vary, their number still have to be predefined.
Ierapetritou and Floudas (1998a) employed the concept of unit-specific
event points. Majozi and Zhu (2001) reformulated the problem to reduce
the number of variables in certain applications. Cerdá, Henning,
and Grossmann (1997) and Méndez and Cerdá (2003) developed
precedence-based models suitable for cases where sequence-dependent
changeovers must be considered.
The rest of this section addresses some issues associated with
conventional approaches to scheduling. These issues motivated the
development of a novel, graph-theoretic approach: the S-graph
framework (Sanmartí, Friedler, and Puigjaner, 1998; Sanmartí et al.,
2002), which is introduced in Section 7.3.2.
In most MILP formulations, the time horizon is divided into time
intervals by so-called time points, which denote the possible starting
and ending times of tasks. The number of time points is one of the
model’s parameters, so it must be specified prior to optimization.
Even though the quality of the solution depends strongly on this
parameter, the minimum number required for the optimal solution
is not known in advance. Therefore, an iterative approach is applied
to determining the number of time points. First the model is solved
using a small number of time points, after which each subsequent
iteration increases that number by 1 until the same objective value is
obtained for, say, two consecutive steps. However, it is not certain
that this initial convergence necessarily yields the optimal solution.