AN EVALUATION OF HEURISTIC ALGORITHMS FOR CELLULAR MANUFACTURING SYSTEMS

Johnny C. Ho, Abbott Turner College of Business, Columbus State University, Columbus, GA 31907-5645 706-562-1668

Yih-Long Chang, DuPree College of Management, Georgia Institute of Technology, Atlanta, GA 30332-0520 404-894-4334

ABSTRACT

This paper studies the lot-sizing problem in Material Requirements Planning/Group Technology and Cellular Manufacturing Systems. A major setup is required if switching from manufacturing one family of components to another family, and a minor setup is needed if switching from manufacturing a component type to another component type within the same family. Inventory holding (shortage) cost is incurred if inventory level is positive (negative). We propose a heuristic method to solve the problem, and conduct a simulation experiment to evaluate the performance of the proposed heuristic and some existing heuristics.

INTRODUCTION

Cellular manufacturing systems controlled by Material Requirements Planning (MRP) logic, also known as MRP/GT (Group Technology) systems, have been proposed as possible means for improving batch production for a number of reasons (New, 1977; Suresh, 1979; Hyer and Wemmerlov, 1982; Steudel and Desruelle, 1992). An important issue concerning the integration of MRP and GT deals with the question: How to determine the order/production quantity? This is known as the lot sizing decision in the literature. Many heuristics have been developed to address the lot sizing issue, the objective used in these heuristics is generally to minimize the sum of setup cost and inventory carrying cost by making a good balance between these two cost components.

In the MRP/GT manufacturing environment, major setups are performed only when switching of production of components among families; while minor setups are required to manufacture components that belong to the same family. Therefore, the lot-sizing problem becomes finding the best tradeoff among three cost components: major setups, minor setups, and inventory carrying. Shtub (1990) proposes a heuristic lot sizing procedure to minimize the sum of major setup cost, minor setup cost, and inventory holding cost for the MRP/GT systems. However, in many real-life situations, demand may not be met on time and so shortages do occur.

This paper considers the lot-sizing problem in MRP/GT systems where inventory shortages are allowed. In the proposed MRP/GT model with planned shortage, the total inventory cost not only accounts for setup and inventory carrying costs, but it also considers the cost of keeping customers on backorder. Hence, we add one more component, shortage cost, in the objective function. The planned shortage model is important because it very often provides lower overall inventory costs than the corresponding model without shortage. We propose a heuristic to solve the proposed lot-sizing problem. Next, the simulation experiment used to evaluate the effectiveness of the proposed heuristic are discussed. Finally, we give a conclusion to the paper.

THE PROPOSED HEURISTIC

We define the following notation for the proposed heuristic.

an index set of component types produced in the same cell.

an index set of families of components produced in the same cell. Each component type is a member of one such family

an index set of time periods in the planning horizon,

holding cost of component type i per unit per period.

shortage cost of component type i per unit per period.

cost of a major setup for family

cost of a minor setup for component type

unit production cost for component type

major setup time required for family

minor setup time required for component type

unit processing time of component type

GT cell capacity in terms of time in period

units of component type produced in period

We propose a heuristic method to solve the MRP/GT lot-sizing problem with planned shortage. Similar to a heuristic from Shtub (1990), the proposed method is an improvement heuristic and is based on the well-known and time-proven savings algorithm of Clarke and Wright (1964). The proposed heuristic consists of two phases. Phase 1 seeks to achieve cost improvement by shifting the production of an entire family forward or backward; while phase 2 seeks to achieve cost improvement by shifting the production of a component type forward or backward. The steps of the proposed Phase 1 heuristic are given as follows.

Phase 1

Input:An initial feasible schedule obtained by an existing MRP lot-sizing technique.

Step 1: For each family scheduled for production in time in quantities

  • Calculate the savings from rescheduling production of this family in a period such that .

(1)

where

  • Compute the savings from rescheduling production of this family in a period such that .

(2)

where

Step 2:Find the maximum value of

  • such that
  • such that

If and , then go to Step 4; otherwise, enter Step 3.

Step 3:Create a revised schedule, called the new current, by incorporating into the current one. Return to Step 1.

Step 4:Stop and output the current schedule.

The input of the proposed heuristic is any schedule that satisfies all capacity constraints. In step 1, we determine and using equations (1) and (2). The former represents the cost tradeoff from rescheduling production of family from period to an earlier period ; while the latter represents the cost tradeoff from rescheduling production of family from period to a later period . Step 2 finds the largest and largest values that satisfy the capacity constraints. If both values are negative, then the heuristic goes to step 4 and terminates. Otherwise, the heuristic enters step 3 and incorporates into the current schedule. We now return to step 1 to seek additional cost reduction. This cycle continues until no further improvement is possible.

Similar to Phase 1 heuristic, Phase 2 heuristic seeks cost reduction by shifting the production either forward or backward. However, Phase 2 focuses on the component type level rather than the family level. Hence, the potential cost reduction is derived from the elimination of a minor setup. The steps of the Phase 2 heuristic are given below.

Phase 2

Input:A schedule obtained from Phase 1 heuristic.

Step 1: For each component type scheduled for production in time in quantities .

  • Calculate the savings from rescheduling production of this component in a period such that .

(3)

  • Compute the savings from rescheduling production of this component in a period such that .

(4)

Step 2:Find the maximum value of

  • such that
  • such that

If and , then go to Step 4; otherwise, enter Step 3.

Step 3:Create a revised schedule, called the new current, by incorporating into the current one. Return to Step 1.

Step 4:Stop and output the current schedule.

A SIMULATION EXPERIMENT

A simulation experiment is conducted to evaluate the effectiveness of the proposed heuristic. We have selected LFL, POQ, SM, and LUC as inputs to the proposed heuristic. However, POQ, SM, and LUC are not directly applicable to this problem without modifying the definition of setup cost for each component. We therefore have created four criteria (versions) for setup cost to be used in each of the three heuristics. They are: 1) minor setup cost; 2) major setup cost; 3) average with number of components/products; and 4) prorated with demand. We will denote version i of POQ, SM, and LUC as POQ:i, SM:i, and LUC:i, respectively.

The simulated system produces two families of components. Family one consists of two components with the unit process times of 0.3 and 0.4 hours, respectively. Family two consists of four components with the unit process times of 0.2, 0.2, 0.2, and 0.3 hours, respectively. Each period has forty hours of operations. The major (family) setup time and minor (component) setup time are 5 and 1 hours, respectively. The unit holding and unit shortage costs are $1 and $1.5, respectively. For each component type, the demand is generated from a discrete uniform distribution of [0, 10, 20, 30,…, 10X], where X is chosen to control the system utilization.

We consider three factors in this experimental study: the minor setup cost and the major setup cost, and mean system utilization. The minor setup cost is set in two levels: $10 and $50. The major setup cost is set in three levels: one time, four times, and ten times of minor setup cost. The mean system utilization is set in four levels: 62.5%, 72.5%, 82.5%, and 92.5% and is given as [(mean demand per component per period) × (mean unit process time) × 6 + (mean major setup time per period) + (mean minor setup time per period)]/40. For each utilization level, 50 problems are created. We solve each problem with the six combinations of minor setup cost and major setup cost.

Computational Results

We use LFL as the benchmark for all other methods by transforming the total cost into a relative performance index as follows: performance index for heuristic i = total cost from heuristic i / total cost from LFL. Hence, the performance index for LFL is always 1. The computational results consistently indicate that as the ratio of major setup cost to minor setup cost increases, the performance of the proposed heuristic ameliorates. The mean performance indices after applying the proposed heuristic for the ratio of 1, 4, and 10 (across all seed solutions) are 0.9251, 0.8580, and 0.7628, respectively. Furthermore, as the minor setup cost and/or major setup cost go up, the effectiveness of the proposed heuristic also improves. For 92.5% system utilization, the computational results show that the proposed heuristic with LFL as input has an index of 0.9955 when major and minor setup costs are both 10. However, the index improves to 0.8764 when major and minor setup costs are both 50, and it improves to 0.6393 when major and minor setup costs are 500 and 50, respectively. Therefore, the proposed heuristic is particularly useful when the ratio of major setup cost to minor setup cost is large, and minor/major setup costs are relatively high.

Moreover, the computational results consistently show that as the system utilization decreases, the proposed heuristic is able to reduce total cost by a greater margin. Again using LFL as input and assuming major and minor setup costs are 500 and 50, the relative indices after applying the proposed heuristic for 92.5%, 82.5%, 72.5%, and 62.5% mean system utilization are 0.6393, 0.5739, 0.4849, and 0.3791, respectively. When the system utilization is at the highest level, the proposed heuristic reduces the total cost by about 36%, but when the system utilization is at the lowest level, it cuts the total cost by about 62%. Therefore, the proposed heuristic is the most effective when system utilization is low, and minor and major setup costs are relatively high.

Lastly, we examine which existing heuristics are among the best for serving as input of the proposed heuristic. For relatively low system utilization, the computational results indicate that LFL possesses the best performance in 10 out of 12 cases. In the other two cases, SM:2 provides the lowest total cost. For relatively high system utilization, the best method is not as obvious as that of the relatively low system utilization. While the SM:2 and SM:4 are generally the best methods, LFL turns out to be the best when major and minor setup costs are high, i.e., 200 for major setup cost and 50 for minor setup cost.

CONCLUSIONS

We consider the problem of lot sizing in cellular manufacturing systems controlled by MRP logic. An important characteristic of these systems is that only minor setup time and cost is required when switching from producing one component to another within the same family. However, a major setup cost is needed when switching between families. The proposed model allows for both inventory surplus and shortage. The model is important because it often provides lower overall inventory costs than the corresponding model without shortage. We propose an efficient improvement heuristic to solve this problem. A simulation experiment is performed to evaluate the performance of the proposed heuristic against some of the existing heuristics. The computational results show that the proposed heuristic is useful to reduce the total cost significantly over a wide variety of simulated environments.

References available upon request from Johnny C. Ho