A process scheduling problem arising from chemical production planning

In this paper we investigate scheduling problems which stem from real-world applications in the chemical process industry both from a theoretical and from a practical point of view. After providing a survey and a general mixed integer programming model, we present some results on the complexity of the process scheduling problem and investigate some important special cases. (We prove the NP-hardness in general and the polynomial solvability for specially structured cases.) Furthermore, we suggest a new heuristic approach and compare this to other heuristics known from the literature.