In this paper, we consider the problem of determining the production rate, production batch size, and production sequence when production rate, setup cost, and unit processing cost are sequence-dependent. Using a standard lot sizing model with backorder, a tabu search algorithm for solving this problem is proposed. The algorithm is tested on some random test problems and its performance is compared with random sequencing. Computational results show that the proposed algorithm is very efficient.
Automation helped manufacturing systems to increase their flexibility through the use of flexible machines. With this increased flexibility, manufacturing systems are able to accommodate different routings and have the choice to choose the best. However, the increased flexibility increases the complexity of production planning since now the number of different routings has increased.
In this paper, we consider the production planning problem when the operations sequence is flexible. This problem is concerned with finding the best operations sequence which minimizes the total cost. Upon finding such a sequence, determining the best production rate, batch size, and backorder quantity are straightforward.
While literature on production planning is very rich, there has been little work done on this specific problem. Egbelu (1993) formulated the problem as a nonlinear integer programming. He suggested a dynamic programming algorithm and a graph theory based heuristic to solve it. Egbelu (1996) developed a methodology to integrate the operation sequencing and machine routing decisions of the process planner and the work of the inventory control analyst in order to minimize total cost of manufacturing in environment with routing flexibility. Khouja (1997) extended the classical economic lot-scheduling problem (ELSP) to cases, where production rates are flexible. Markowitz, Reiman, and Wein (2000) have considered two queuing control problems that are stochastic versions of the economic lot scheduling problem: a single server processes N customer classes, and completed units enter a finished goods inventory that services exogenous customer demand. Unsatisfied demand is backordered, and each class has its own general service time distribution, renewal demand process, and holding and backordering cost rates. In the first problem, a setup cost is incurred when the server switches class, and the setup cost is replaced by a setup time in the second problem. In both problems they employed a long run average cost criterion that is restricted to a class of dynamic cyclic policies, where idle periods and lot sizes are state-dependent, but the N classes must be served in a fixed sequence.
In a recent paper, Ouenniche and Boctor, 2001a and Ouenniche and Boctor, 2001b have developed a new and efficient heuristic to multi-product, multi-stage, sequencing, lot sizing and scheduling problems in flow shop environments. The objective was to minimize the sum of setup and inventory holding costs while a given demand is fulfilled without backlogging. Their heuristic, called the TG method, assumes that cycle times are integer multiples of a basic period and restricts these multiples to take only one of two values: 1 or K (K≥1). The items to be produced once each K basic period are then partitioned into K sub-groups and each sub-group is assigned to one and only one of the K basic periods of the global cycle. Finally, a production sequence is determined for each sub-group of products and a non-linear program is solved to determine lot sizes and to construct a feasible production schedule. Magnusson (2001) considered the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs and times. An important additional feature of his problem was that setups may be carried over from one period to the next, and that setups are preserved over periods during which the machine is idle. He provided an exact formulation of this problem as a mixed-integer program and provided numerical examples dealing with small instances of the problem. These numerical examples were solved using commercially available optimization software.
In this paper, we present a new tabu search based algorithm for solving the above-discussed problem. The paper is organized as follows: the problem statement is given in Section 2. In Section 3, we give a brief introduction to tabu search. The proposed algorithm is stated in Section 4. Computational results and discussion are presented in Section 5. Finally, conclusions are given in Section 6.
In this paper, a new algorithm for the production planning problem in a flexible manufacturing environment has been presented. The algorithm which is based on tabu search technique determines the sequence-dependent production rate, batch size, and the production sequence when the setup cost and processing cost are also operation sequence-dependent. Computational results show that our algorithm is very promising. One can utilize our algorithm in an integrated systems like computer-aided process planning (CAPP). Our algorithm constitutes an important part of CAPP system, where the part features and shape information are extracted from CAD (computer-aided design) system.
One can extend the work by considering stochastic demand. One can also extend the work by investigating other features for generating the random sequences and by using other elements of tabu search such as long-term memory, strategic oscillation, path relinking, among others. One could also improve the performance of the proposed algorithm by getting a good initial solution.
