An experimental evaluation of single-stage lot-size scheduling heuristics in a multi-stage, multi-product production environment

Journal of Business Logistics, 1995 by El-Najdawi, M K

Scheduling interference is possible when a single production facility is used to produce more than one product and the lot size for each is determined without considering that all products share the same facility. When the lot size for a product is determined by the Economic Production Lot Size Method, it is assumed that the product has unrestricted access to the facility. In a situation where the common facility is greatly underused, the assumption of unrestricted access may be true. However, if the common facility is being used to full or nearly full capacity, then no product can realistically have unrestricted access to the facility, and scheduling interference results. This situation presents the "Economic Lot Scheduling Problem." Research has attempted to develop some cycling policy in order to avoid the risk of infeasible schedules. One way to solve this problem--imposing the rule that every item be produced once each cycle--is Common Cycle Scheduling.

The first solutions to the (single-stage) Common Cycle Scheduling Problem (CCSP) in the literature were reported by Eilon(1) and Hanssmann.(2) Since then many other researchers have studied the CCSP and its variations. Eilon considered the single-stage CCSP problem and introduced a variation of the conventional economic production lot quantity model that determines the length of the cycle and the buffer stock to meet a stationary demand profile of finished products. His model treats the multistage case in aggregate as if executed by a single facility. Taha and Skeith(3) and Jensen and Khan(4) generalized earlier work on production lot-sizing to accommodate instantaneous production and various forms of capacity restrictions.

Szendrovits(5) refined Eilon's concept and developed a model that treats the manufacturing cycle time as a function of the lot size in a multistage production system. He used this functional relationship to determine the magnitude of the work-in-process inventory and developed a model to calculate the Economic Production Quantity.

Buffa,(6) relying on Hanssmann, studied the CCSP and argued that the CCSP was a reasonable framework for dealing with scheduling interference problems in multiproduct inventory systems. Of course, common cycle scheduling can provide a feasible solution only as long as the total load is within system capacity. The CCSP single stage model developed by Hanssmann and refined by Buffa will be referred to in this paper as the Conventional Common Cycle Scheduling Model (CCCS).

The CCCS model for a number of products (N) was developed by methods similar to those used to develop EOQ formulas. The total annual cost, which consists of annual inventory and set-up costs under the CCCS policy, is:

(Equation 1 omitted)

where: S sub i = ordering and set-up costs for product i

alpha V sub i = unit inventory cost for i

P sub i = annual production rate for i

D sub i = annual requirement for i

The number of production runs that jointly minimize annual inventory plus set-up costs for all products is:

(Equation 2 omitted)

where the optimal cycle time T* = 1/N*. The total incremental cost of an optimal solution is:

(Equation 3 omitted)

The CCSP model has been applied in a number of cases reported in the literature.(7,8) While these applications were concerned with the multiproduct CCSP case, they failed (with the exception of Szendrovits) to incorporate in-process inventories into the analysis; only finished goods inventories and related cost were considered.

El-Najdawi and Kleindorfer(9) provided an optimizing framework for CCSP for a multistage, multiproduct, flow-shop environment, generalizing earlier CCSP results, as well as the single-product results of Szendrovits. El-Najdawi's model was formulated to minimize total cost for all products while meeting given, stationary demands and remaining within feasible capacity limits. The total cost in the production process is the total carrying costs of finished and in-process inventories plus the total set-up costs.

Although El-Najdawi's model incorporates in-process inventories and gives an optimal solution to the CCSP in a multiproduct, multistage production environment, its applicability and cost efficiency for large scale and real world problems is difficult to justify. Heuristic solutions to similar problems prove to be efficient and effective.(10) The objective of the present paper is to follow this realistic trend and to develop easily invoked and applicable heuristic solutions to the multistage, multiproduct production scheduling problem. The performance of these heuristics will be tested against the El-Najdawi and Kleindorfer model, which gives an optimal solution to the multistage, multiproduct CCSP.

EXPERIMENTAL EVALUATION OF HEURISTICS FOR THE CCSP PROBLEM

In this section, the results of an experimental evaluation of various heuristics for the Common Cycle Scheduling Problem are presented. The essence of the evaluation is to use the optimality results of the El-Najdawi and Kleindorfer model as a benchmark against which the performance of various heuristics can be compared. The heuristics of interest are concerned with two primary decisions, which are solved for jointly in the optimization algorithm. The first decision is the cycle time. The second is the scheduling of jobs at each processing center, given the cycle time (and therefore the lot sizes for each product). The scheduling problem is solved by specifying the wait times (or start times) for each job i at each machine j. Concerning the cycle time, the basic heuristics we use derive from compressing (in various ways) the multistage process of interest here into an approximating single-stage process. Thereafter, any of a number of heuristics can be used for solving the resulting approximating single-stage process for an optimal cycle time. We use the best-known of the single-stage heuristics presented by Buffa.