Scheduling of process operations using mathematical programming techniques: Towards a prototype decision support system

A general approach suitable for handling a wide range of process scheduling problems and that can be effectively utilized in a framework of a scheduling decision support system is developed. A mixed integer linear programming formulation that handles a variety of complexities, including variable batch sizes, limited availability of resources, intermediate product draw-offs, and a number of objectives is presented along with various techniques to reduce its size and eliminate a large number of the complicating variables and constraints. The characteristics of the difficulty of scheduling instances is investigated via a series of computational experiments. It is found that sharing of equipment and production routes and high set-up costs lead to higher computational times. Large orders, higher processing times, and unstable intermediates lead to smaller CPU times when problems are only slightly constrained and large times for more constrained problems. Initial feasible solutions to the scheduling problem are provided by a new class of heuristic procedures. These heuristics are based on the mathematical programming formulation and exploit the structure of the scheduling problem in order to modify the exact solution procedure to rapidly obtain solutions. The quality of the heuristics is shown to be good, both in terms of computational expense and accuracy. The linear programming relaxations to the mixed integer linear programming formulation are tightened by introducing a number of valid inequalities, which are developed based on the model structure. Computational experiments are shown and the implementation of a separation algorithm that detects violated valid inequalities and amends them to the original formulation is described. New information at each node in the branch-and-bound tree is exploited via an algorithm that predicts which of the valid inequalities will be strong for the inner nodes and amends them to the original formulation. Lastly, an integrated solution approach that combines the findings of this work is presented and its power to solve large practical scheduling problems involving up to 2700 binary variables is demonstrated