Abstract
Production Planning usually eliminates setup time and setup cost for simplifying problem and speeding up solving. In order to make production planning more practical, we take setup time and setup cost into consideration. We formulate the problem as a mixed integer program (MIP), and that make solving lot-sizing problem be NP-Hard. In this study, we develop heuristic algorithms to solve the problem formulation.Recently, many heuristic algorithms were widely used to solve NP-hard problems. Using tabu search to solve problems is always able to obtain satisfactory results. This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. We improve tabu search by a new candidate list strategy, which sorts the neighbor solution using post-information provided by the tableau of the linear programming simplex algorithm. A solution with higher priority in the ranking sequence has higher probability of being the best neighbor solution of a current solution. According to the ranking candidate, we can reduce neighborhood search and, thus, speed up computation time.We analysed the quality of solution by using various algorithms to solve random problems. Based on the experiment, our search algorithms have good performance in search time and in the quality of solution.