استفاده از TS با فهرست رتبه بندی نامزد برای حل مشکلات برنامه ریزی تولید با راه اندازی

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.

The Lot Sizing Problem has been studied for almost a century. The first models for this problem are renowned EOQ/EMQ formulas, which are applied to individual product types. As manufacturing techniques become increasingly more complex, solving the lot sizing problem becomes much more difficult. First, limitations on manufacturing resources lead to the so-called Capacitated Lot Sizing Problem. Second, more than one product may compete for the same manufacturing resources. This problem is usually referred as Multi-Item Capacitated Lot Sizing. Third, the number of periods considered is another difficulty in solving lot sizing problems. Considering the timing of setups on a continuous time horizon, the EOQ/EMQ models determine the sequence and the length of cycle time, whereas the dynamic capacitated lot sizing models and MRP systems ( Orlicky, 1975) consider time-phased decisions—multiple period decisions. Fourth, producing one lot of a particular product in a particular period requires one setup for that product on each required resource during that period. A setup may imply two kinds of resource consumption. One is setup cost, expressed in monetary terms; the other is setup time, consuming a certain amount of resource-hours. In sum, five dimensions of problem complexity—availability of multiple limited resources, existence of multiple products, multiple periods in the planning horizon, setup times, and setup costs—are considered in this study. Our problem formulation differs from conventional capacitated lot sizing problems. We call it Production Planning Problems With Setups, which involves the decision for the production quantity of each product in each period. If a particular product is to be manufactured during a certain period, each required machine must be setup once in that period to make production possible. On the other hand, if a certain product is not to be produced, no setups on any machine need to be performed for this product type. A setup means deducting the setup time from the available resource-hours and deducting the setup cost from the objective function in the formulation, which maximizes corporate cash flow. Our problem is a generalized version of the capacitated lot sizing problem, which involves setup decisions for a production facility where multiple products are manufactured by multiple resources over multiple periods. This kind of problem is frequently encountered in manufacturing environments. However, as in the conventional capacitated lot sizing problem, we assume the setup status cannot be carried over to the next period and we do not consider sequencing decisions within each period. This problem can be formulated as a mixed integer program (MIP), which is the same as the one solved by Hung and Hu (1998). 1. Index: i: product type, i=1,2,…,I; k: resource type, k=1,2,…,K; t: planning period, t=1,2,…,T. 2. Decision Variables: Xit: the quantity of product i produced in period t; Iit: the inventory level of product i at the end of period t; Bit: the backorder level of product i at the end of period t; Yit: the setup decision for product i during period t, a binary integer variable. Yit=1 means setting up for product i in period t; while, Yit=0 means otherwise. The relationship with Xit is defined by: 3. Parameters: ckt: the available resource-hours of resource k in period t; uik: the setup time for product i on resource k; aik: the consumption of resource k per unit of product i; hit: the inventory holding cost per unit of product i at the end of period t; bit: the backorder cost per unit of product i at the end of period t; rit: the revenue per unit of product i in period t; sikt: the setup cost for product i on resource k during period t; dit: the external demand for product i in period t; Ii0: the initial inventory of product i; M: a large number to be used in the inequality that allows Xit to be a positive value and less than M, when Yit=1. 4. Objective Function: 5. Constraints: 1. Inventory Balance: 2. Resource Capacity: 3. Domain Constraints: For a detailed description of this problem formulation, please consult Hung and Hu (1998).

For solving an LP problem, the shadow prices and row zero coefficients are useful in post-optimization analysis. Similarly, we can use such information to help determine the setup integer variables during the search process of an MIP problem. In this study, the information provides the ranking in neighborhood evaluation of tabu search algorithm. A neighbor with a higher ranking has a higher probability of being the best neighbor. Using these heuristic ranking methods, this study proposes two new candidate list strategies for tabu search. Our experiments show that the proposed methods find a good solution faster than the TSTS. More specifically, the QMTS is faster than the RNTS, and the RNTS is, in turn, better than the TSTS. Thus, the proposed tabu search algorithms, especially QMTS, are useful in solving large-scale realistic production planning problems with setups. This study also suggests that, if the evaluation of the entire neighborhood space requires too much computation, developing an efficient and effective neighborhood sorting method and using ranking candidate list strategy could improve the performance of tabu search. Computation time could be saved by using one of the following two strategies. First, reduce the neighborhood space by examining only the higher portion of the ranking sequence. Second, evaluating the ranked neighbors sequentially and move to a better neighbor immediately by ignoring the remaining neighbors. Using the production planning problems with setups, we demonstrate the efficiency and effectiveness of the ranking candidate list strategy for tabu search.