A simulated annealing algorithm for the capacitated lot-sizing and scheduling problem under sequence-dependent setup costs and setup times

In this research, the single machine capacitated lot-sizing and scheduling problem with sequence- dependent setup costs and setup times (CLSPSD) is considered. This problem is the extension of capacitated lot-sizing and scheduling problem (CLSP) with an additional assumption on sequence-dependent setup costs and setup times. The objective of the problem is minimizing the sum of production costs, inventory holding costs and setup costs satisfying customers' demands. It is known that the CLSPSD is NP-hard. In this paper, the MIP formulation is presented. To handle the problem more efficiently, a conceptual model is suggested, and one of the well-known meta-heuristics, the simulated annealing approach, is applied. To illustrate the performance of this approach, various instances are tested and the results of this algorithm are compared with those of the CLPEX. Computational results show that this approach generates optimal or nearly optimal solutions.