Abstract
Lot-sizing models usually divide time horizon into several planning periods and assume setups cannot be carried over. However, carry-over setups are obvious in most manufacturing environment. In order to make lot-sizing problem more appropriate, we consider carry-over setups and formulate our problem as a mixed integer programming which considers single machine type, multiple machines, multiple products, multiple periods, setup times, setup costs, and carry-over setups. This problem includes two kinds of decisions --- the decisions of setups (binary variables) and the size of production lot. Due to the problem being NP-Hard, this study uses search algorithms to slove the problem formulation. Recently, many researchers use tabu search and simulated annealing to solve difficult optimization problems and scheduling problems. Most of them are able to obtain satisfactory results. Thus, to solve the production planning with setups carry-over, this study uses tabu search and simulated annealing and proposes seven kinds of search algorithms to improve the efficiency of the search process while solving the problem . Based on the experiment in the study, the solving time using search algorithms is much less than using branch and bound algorithm in most problems. Quick move tabu search using evaluation model always has best performance in search time and in the quality of solution. Thus, quick move tabu search is a good search algorithm for solving production planning with setups carry-over.