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.