A hybrid evolutionary algorithm for solving two-stage stochastic integer programs in chemical batch scheduling

This contribution deals with the solution of two-stage stochastic integer programs with discrete scenarios (2-SIPs) that arise in chemical batch scheduling under uncertainty. Since the number of integer variables in the second-stage increases linearly with the number of scenarios considered, the real world applications usually give rise to large scale deterministic equivalent mixed-integer linear programs (MILPs) which cannot be solved easily without incorporating decomposition methods or problem specific knowledge.In this paper a new hybrid algorithm is proposed to solve 2-SIPs based on stage decomposition: an evolutionary algorithm performs the search on the first-stage variables while the second-stage subproblems are solved by mixed-integer programming. The algorithm is tested for a real-world scheduling problem with uncertainties in the demands and in the production capacity. Numerical experiments have shown, that the new algorithm is robust and superior to state-of-the-art solvers if good solutions are needed in short CPU-times.