Hybrid simulated annealing and MIP-based heuristics for stochastic lot-sizing and scheduling problem in capacitated multi-stage production system

摘要

This paper addresses lot sizing and scheduling problem of a flow shop system with capacity constraints, sequence-dependent setups, uncertain processing times and uncertain multi-product and multi-period demand. The evolution of the uncertain parameters is modeled by means of probability distributions and chance-constrained programming (CCP) theory. A new mixed-integer programming (MIP) model with big bucket time approach is proposed to formulate the problem. Due to the complexity of problem, two MlP-based heuristics with rolling horizon framework named non-permutation heuristic (NPH) and permutation heuristic (PH) have been performed to solve this model. Also, a hybrid meta-heuristic based on a combination of simulated annealing, firefly algorithm and proposed heuristic for scheduling is developed to solve the problem. Additionally, Taguchi method is conducted to calibrate the parameters of the meta-heuristic and select the optimal levels of the algorithm's performance influential factors. Computational results on a set of randomly generated instances show the efficiency of the hybrid meta-heuristic against exact solution algorithm and heuristics.