Specially structured formulations and solution methods for optimization problems important to process scheduling

In the chemical process industries, there exist opportunities to improve capital utilization, customer satisfaction, resource allocation, and customer responsiveness by improving process scheduling. The area of process scheduling refers to developing models of operation and solution algorithms to effectively allocate process resources among competing alternatives. As the chemical process industries serve more diverse market segments, the complexity and number of possible alternatives grows along with the possible gain associated with making better decisions. The challenge for researchers is to address these opportunities for improvement by developing effective models and algorithms to solve complex optimization problems. The difficulty of the underlying problems and the cost improvements to be achieved are the main driving factors in a growing body of research in this area. In this thesis, several contributions are made to this effort. First, a model of parallel scheduling of chemical facilities is developed. This model applies to processes where there are significant changeover, production, and transportation costs subject to demand constraints. The main assumption of the model is that each unit operation is independent of all others (i.e. the units are in parallel). An algorithm was developed for this problem which performed well on cases with a hundred products being demanded for a plant having eight units with time divided into a hundred segments on each unit. Theoretical relationships between this parallel flowshop and other models of process scheduling were developed. These results were based on a rigorous comparison of the underlying representation of the discrete decision space. This comparison assumes independent operation of units and the only costs were for changeover, production, transportation and deadline violation. This comparison showed that the parallel flowshop model developed in this thesis was a superior characterization for all possible instances. Finally, a general model of process scheduling was developed based on a new representation of the discrete decision space corresponding to production and changeover. This model was compared empirically to an existing general model and it was shown that the representation presented in this thesis was superior for the examples considered