(61d) Strengthening the Continuous Time Formulation of a Mixed Plant Cyclic Scheduling Problem

We study in this paper a continuous time formulation for a test
case of the cyclic scheduling of hybrid production lines, i.e. composed of batch
and continuous processes. This test case is similar to the problem studied in
[2], [3] and [4]. The objective is to maximize productivity. We base our formulation
on the resource task network representation.

The main characteristic of this continuous time formulation is that the size
of the time interval between two events (i.e points in time when the system
state changes) and the duration of the cycle are variables of the model.

This formulation is very compact in the sense that the number of events is
much smaller than the number of time periods needed for the corresponding discrete
time formulation. The latter formulation is usually quite tight but the size
of the time period is fixed and has to be smaller than the greatest common divisor
of all the processing times of the batch processes. Therefore, the number of
time periods needed is typically very large.[1] However, the drawback is that
continuous time formulations are very weak, i.e. duality gaps are large, because
big M type constraints need to be introduced to build a correct model formulation.We
show in this paper how a continuous time formulation can be improved for the
batch part of the problem by using some valid inequalities that are facets for
some subproblems of the general problem studied here. These inequalities are
obtained using strengthening techniques [6] and the analysis of small polytopes
[5]. Finally, we show that a better formulation is obtained with these improvements
in the sense that the duality gap is smaller than before for some canonical
subproblems and that numerical instances of the test case problem can be solved
more rapidly.

References

[1] N. Shah, C.C. Pantelides, and R.W.H. Sargent : Optimal periodic scheduling
of multipurpose batch plants (1993), Annals of Operations Research 42, p. 193-228.

[2] G. Schilling, C.C. Pantelides : Optimal periodic scheduling of multipurpose
plants (1999), Computers chem. Engng 23,p. 635-655.

[3] P.M. Castro, A.P. Barbosa-Povoa, and H.A. Matos : Optimal periodic scheduling
of batch plants using RTN-based discrete and continuous-time formulations :
A case study approach (2003), Ind. Eng. Chem. Res. 42, p. 3346-3360.

[4] D. Wu, M. Ierapetritou : Cyclic short-term scheduling of multiproduct batch
plants using continuous-time representation (2004), Computers chem. Engng 28,p.
2271-2286.

[5] T. Christof and A. Loebel. Porta - a polyhedron representation transformation
algorithm. available via http://www.zib.de/Optimization/Software/Porta/, 1997.

[6] K. Andersen and Y. Pochet. Coefficient strengthening : a tool for formulating
mixed integer programs. To be submitted, 2006.