Clustering-based solution approach for a capacitated lot-sizing problem on parallel machines with sequence-dependent setups*
针对食品工业中带序列相关设置时间的并行机容量批量问题，提出聚类方法近似设置时间，结合松弛-固定和固定-优化启发式，在工业实例上快速获得可行解。
This paper studies an industrial lot-sizing and scheduling problem coming from the food-industry that extends the multi-item capacitated lot-sizing and includes lost sales, overtimes, safety stock and non-uniform sequence-dependent setups on parallel machines. We introduce two different formulations and adapt the well-known Relax-and-Fix and Fix-and-Optimise heuristics in order to quickly obtain feasible solutions on large industrial instances. The complexity of our problem prevents the procedure to obtain good solutions within the time allocated by practitioners on real-life cases, hence we propose to use a clustering approach to approximate the sequence-dependent setup times. The resulting problem is significantly smaller to solve and experimental results suggest that this transformation effectively improves the solutions found on industrial instances. In particular, the combination of this clustering method and Relax-and-Fix and Fix-and-Optimise procedure turns out to be a promising approach to obtain good solutions in the given time-limit.