A hybrid simulated annealing for the single machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times and costs

摘要

Single machine capacitated lot-sizing and scheduling problem (SMCLSP) is one of the most famous fields of research in scheduling area. What makes this problem particularly difficult to solve is large and sequence dependent setups and also multiple criteria that must be considered. This paper formulates such a problem and presents a hybrid simulated annealing (HSA) for it. The superiority of HSA is shown compared to one the efficient recent heuristics. The average deviation of the HSA from the corresponding optimal solution for small size problems ranges from 0 to 10%.