The Integration of Dynamic Lot Sizing and
Customer Order Problem in Supply Chain Management
Sheng-Yuan, Hsu†
Department of Industrial Engineering and Management,
Chienkuo Technology University, Changhua, Taiwan, R.O.C.
Email:
Abstract: In supply chain management, on time delivery is very important issues for the customers. The order issued by the customer will purchase more than one items. How to finish the order on time, that is all the item of the order will be ready for delivering, will be an important task. Therefore, in the paper, the dynamic demand lot-sizing problem (DLSP) and customer ordering problem (COP) will be considered together. DLSP focused on the deterministic time-varying batch ordering lot sizing problem with backorders. COP is considered the order consists of a set of jobs thatmust be shipped as one batch at the same time. A Linear Programming model will be developed for describing the dynamic lot-sizing problem with customer order considering. Genetic algorithms (GA) are applied to the problem. Besides, for benchmarking considering, two popular algorithms, Silver-Meal (SM) algorithms and Wagner-Whitin (WW) algorithms will be modified to solve the problem. Two heuristics, MSM and MWW, are developed for solving the kinds of problem. 128 scenarios and 100 repetitions have been considered in the simulation test. In the statistical analysis, the performance of GA will be better than MSM and MWW. The decision based on GA will save more than 10-50% especially in those scenarios with long term, multiple items, and high expense rate (ordering cost and holding cost).
Keywords: dynamic lot-sizing problem, customer order problem, GA, supply chain management
1.Introduction
This paper addressed two typical problems in supply chain management, the one is DLSP, dynamic lot sizing problem, another one is COP, customer ordering problem. DLSP is focus on the deterministic time-varying batch ordering lots sizing problem with backorders. The objective is to determine the optimum ordering plan, i.e. the one minimizes the total cost, to satisfy a set of known demands over a specific planning horizon. COP is very common in supply chain, like as figure 1. Customer, issues the order based on their own order. The order will order more than one items for fulfilling their customer’s demand. All the items at the same order should be delivered at the same time. It’s not allowed to deliver if there is any one item to be out of stock. This type of problem is typical COP.
In traditional lot sizing problem, the purchasing decision will be made base on the customers’ order. In practice, the customer order will purchase more than one items in the same order. Furthermore, all the items at the same order should be delivered at the same ship for proceeding the next fabrication steps. Hence, COP should be considered in the dynamic lot sizing decision. In the research, we will address DLSP considering with COP, namely DLSCOP, dynamic lot sizing considering with customer ordering problem.
2.Literature review
2.1COP
COS, where each order consists of a set of jobs that must be shipped as one batch. The composition of an order is specified by the purchased order. The company may not ship the order until all the products in the order are completed. Let’s consider an electronics manufacturing facility where computer monitors are produced. Generally, this is a multi-stage production process including several fabrication operations, and a final assembly operation. The fabrication operations create various components including printed circuit board, front and back cabinet covers, and color display tubes. The components are then combined into a batch, and that batch is the set of parts required to produce one type of monitor. The final assembly operation is not started until all required components are finished by the fabrication operations. Figure 1 is another example of CNC machine.
In recent years, managing the efficiency of a supply chain has become an important topic for academic research and practical application in shop. How to deliver the products to a customer on time is an important task. Most customer orders must be delivered at a suitable time to the customer to allow them to carry on with their manufacturing process. Therefore, customer order scheduling is an important topic for improving customer satisfaction and providing a competitive advantage.
In thereviewing of Hsu and Liu (2009),there were only a few studies that focused on the customer order scheduling problem. Most of the studies focused on the single machine or parallel machine system and tried to find an optimal solution. Julien and Magazine (1990) assumed a job-dependent setup time for two different types of jobs. They assumed a Dynamic Programming (DP) algorithm for the single machine problem when there are only two types of jobs and the batch processing order is fixed. The objective here is to minimize the total completion time of the orders. Coffman et al. (1989) considered the same problem as that of Julien and Magazine (1990) under the assumption that the batch processing order isn’t fixed. In addition, Baker (1988), Gupta et al. (1997) and Gerodimos et al. (2000) also focused on the single machine case. Yang (2005) introduced the relatively new class of the case of COS forparallel machines. He proposedan optimal solution procedure for each of several problems with different types of objectives, job restrictions, and machine environments. Yang and Posner (2005) considered the COS case in for jobs thatmust be dispatched in batches. A heuristic was presented for the problem and a tight worst case bound on the relative error was found. Ahmadi et al. (2005) and Wang and Cheng (2007) considered the COS case for m dedicated facilities and n orders. Each job only needs one operation at a dedicated facility. They showed that the problem is unary NP-hard. They proposed a heuristic method to minimize the total weighted order completion time and analyzed a worst-case scenario. Daganzo (1989) and Peterkofsky and Daganzo (1990) focused on the crane scheduling problem, which is simplyanother kind of COS problem with a parallel machine. In their discussions, jobs consist of independent, single stage, pre-emptable tasks. The objective function is the minimization of the weighted tardiness. Daganzo (1989) applied the weighted shortest processing time first rule to obtain optimal solutions for some special cases. Peterkofsky and Daganzo (1990) developed a branch-and-bound solution procedure. However, they did not provide a theoretical basis for their method.
Blocher et al. (1998) dealt with the COS problem in a general job shop. The shop used in their study is made up of six machines. It is the first simulation study using the customer order environment. They specifically comparedthe dispatching rules from past job-based studies to rules that were adapted to include order characteristics. The performance measures weredivided into two parts: measures involving order flow time and measures involving due dates. The order flow time measure is similar to the common job flow time measure, except for the fact that the flow time is based on order parameters (group of jobs). The due date measures are based on average tardiness and proportion tardy. Of the sixteen dispatching rules tested, four simple rules dominate all others. Those rules consider order characteristics, namely order-based rules, perform better than their job-based counterparts.
Hsu and Liu (2009) discussedthe reducing of the stock level of finished goods and trying to improve the delivery efficiency for the COP in job shop. The main topic is how tocontrol the finished time of all jobs of the same order in a normal job shop.
2.2DLSP
Lot sizing models determine the optimal timing and level of production. At one end of the spectrum there are the continuous time scale, constant demand and infinite time horizon lot sizing problems. In this category we find the famous economic order quantity model (EOQ) and the economic lot scheduling problem (ELSP). At the other end of this spectrum there have discrete time scale, dynamic demand and finite time horizon lot sizing models. This type of planning is generally referred to as dynamic lot sizing and is the subject of the paper (Jans and Degraeve, 2007). A number of studies have provided a good introduction to the lot sizing problem. De Bodt et al. (1984) and Bahl et al. (1987) present earlier reviews. Jans and Degraeve (2007) provide a wider survey of meta-heuristics applicationsin dynamic lot sizing. Robinson et al. (2009) updates a 1988 review of the coordinated lot-sizing problem and complements recent reviews on the single-item lot-sizing problem and the capacitated lot-sizing problem. It provides a state-of-the-art review of the research and future research projections. A complete framework for lot sizing problem has been presented. Most of the model and algorithms have been discussed, too. There are different types of lot-sizing problems based on those parameter, like as static/dynamic demand, uncapacitated/capacitated, lot sizing, backorder, setup cost/purchasing cost, etc. However, none of the researches focused on lot-sizing problem considering the scenario of customer order problem in our reviewing.
One of the most commonly used suboptimal algorithms is the Silver-Meal (Silver and Peterson, 1985). The original SM algorithm finds the number of periods for which the total inventory costs per period is minimized and then orders the exact quantity to cover the demand for those periods. A dynamic programming algorithm to obtain the optimum solution to a simpler version of lot-sizing problem was developed by Wagner and Whitin (1958). Several extensions of the original WW algorithm were developed over time. However, in the reviewing of Jans and Degraeve(2007) and Robinsonet al. (2009), the lot-sizing problems are very complex to find the optimal solution. Lots of meta-heuristics for dynamic lot-sizing are presented, like as tabu search (TS), simulated annealing (SA) and genetic algorithms (GA).
Several authors have applied GAs to various versions of the lot of sizing problem. For example, Ozdamar and Birbil (1998) utilized GA, simulated annealing (SA), and tabu search to solve the capacitated lot sizing problem on parallel machines. Hung and Chien (2000) also utilized GA, SA, and tabu search to solve the multi-class multi-level capacitated lot sizing problem. Khouja et al. (1998) investigated the use of GAs to solve the economic lot size scheduling problem using the basic periodapproach. Prasad and Chetty (2001) applied GAs to multi-level lot sizing and observed that undera rolling horizon environment. The performance of GAs is superior to the popular heuristics.
Staggemeier et al. (2002) presented a hybrid GA to solve a lot sizing and scheduling problem by minimizing inventory and backlogcosts of multiple products on parallel machines with sequence-dependent set-up times. Basnet and Leung(2002) presented a multi-period inventory lot sizing scenario, where there are multiple products and multiplesuppliers. Sarker and Newton (2002) develop GA code with three different penalty functions to determineoptimal batch sizes for products and the purchasing policy of associated raw materials. GA results were comparedto optimal solutions, and the GA with a static penalty function obtained the global optimum 100% ofthe time. Moon et al. (2002) developed a hybrid genetic algorithm to address the lot schedulingproblem with time-varying lot sizes. A numerical experiment showed that the hybrid GA performed better than other heuristic methods. Shittu (2003) used GAs to address the lot sizing problem with batch sizing and compared their performanceto that of the SM.
After the discussion mentioned above, DLS is one of the key problem in production planning, inventory management, and supply chain management. The purchasing decision is a very important issue, especially in the cooperation with those members in the supply chain. How to make a quality decision for improving the performance of the whole supply chain should be considered for improving the advantage of competition. Besides, COP is another popular issue in supply chain management. Order-oriented decision will be very important for fulfilling the demand of the final customers in supply chain management. In the paper, we will deal with the dynamic lot sizing problem with order-oriented considering. That is, we will focus on the DLSP with COP considering, namely DLSCOP.
3.Problem formulation
This paper addresses the dynamic lot-sizing problem with customer order considering. There are two type of problems are considered in the research, DLSP and COP. DLSP is focused on the deterministic time-varying batch ordering lot sizing problem with back orders. We will consider the DLS problem at DLSP. Especially in the viewpoint of supply chain management, lot-sizing decision should consider the customer order’s content. All the time, customers’ order will order more than one item. The decision should be extended to multiple items. One item shortage at some period will have effect up on the others at the same order.
3.1 assumption and notations
The paper investigates the performance of GA in the DLSP with customer ordering considering with the following assumptions:
The demand is variable and deterministic.
Order quantities must be integer multiples of a constant batch size. No other limits are imposed on the size of the order.
Cost factors are time independent.
Replenishment is instantaneous.
Back orders are only allowed to make up for quantity discrepancies that result from batch ordering.
An order must be placed in the first period.
All the items order at the same order should be delivered at the same period. If any of them are shortage all the order will be backordered.
The following notations are used for developing the model.
i : order number, i =1,2,…m
j : Item type, j=1,2,…n
t : planning period, t=1,2,….T
cj: batch size of item j
dijt: demand of item j of order i at period t.
g: backorder cost per unit per period
h: holding cost per unit per period
M: a large number
p: ordering cost
T: the planning horizon
IIjt: independent inventory level of item j at the end of period t,
DIjt: dependent inventory level of item j at the end of period t,
wjt: positive Inventory level of item j at the end of period k. wjt = max(0,IIjt+DIjt ),
xjt: a decision variable that is a integer multiple of the batch size lending the quantity made or ordered of item j in period t,
yjt: Boolean variable to assign the ordering cost of item j in period t,
IBjt: independent backorder quantity of item j at the end of period t, IBjt= max(0, -IIjt),
DBjt: dependent backorder quantity of item j at the end of period t, DBjt=max(0, - DIjt) ,
zjt: backorder quantity at the end of period t, zjt=max(0, IBjt+DBjt),
yjt: Boolean variable to assign the setup/ordering cost of item j in period t,
uijt: Boolean variable to assign the dependent inventory level of item j of order i in period t,
vijt: Boolean variable to assign the dependent backorder of item j of order i in period t.
kijt: Boolean variable to ckeck dijt will be fulfilled (not become backorder) or not.
3.2 The mathematical model
Using the notation above, the mathematical formulation of the problem can be written as follows:
Minimize:
(1)
Subject to:
(2)
(3)
(4)
(5)
(6)
(7)
(8)(9)(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
The objective function (1) minimizesthe total ordering, holding, and backordering costover time. Constraint (2) models the flow conservation in period t. Constraint (3) and (6) models the total of dependent inventory/backorder at period t. Constraint (4) limits backorders to compensate for fixing quantities within c only. Constraint (5) models the total independent backorder at period t. Constraint (7) (10) force yjt to zero or one to ensure that setup/ordering cost is onlycharged when an order is made. Constraint (8) (9) (11) (12) model the dependent inventory and dependent backorder based on the definition of customer ordering problem. Constraint (13) sets the initial inventory level to zero.Constraint (15) ensures that an order is made in the first period.Finally, constraints (14) (16) (17) ensure that order, carryover, and backorderquantities are all non-negative.
4.Approach
Genetic algorithms (GAs) were first introduced by Holland (1975 *03) as optimization searchtechniques that generate and evaluate solutions until a stopping criterion is satisfied. In GAs, a solution is represented as a chromosome, which in our case is the string of T digits (where T is the number of periods). Each digit may take the value of 0, 1, or, 2. A digit may also be called a gene or a bit. The replenishment decision and how many periods in the future can be covered by a replenishment order are explicitly answered by the zero-one-two coding. A value of one or two in any digit indicates that an order should be placed in the period corresponding to that digit for its demand and the demand in all subsequent periods with a code of zero. Owing to consider the batch ordering ( c) limitation, code one and two are represented for sufficient replenishment and insufficient replenishment separately. The order of sufficient replenishment is higher than the total demand. Some extra quantity will be stocked. It indicates an order quantity that is the closet integer multiple of c higher than the total demand. Insufficient replenishment indicates an order quantity that is the closet integer multiple of c lower than the total demand. Some requirement will be fulfilled by backorder. A set of such chromosomes is generated randomly to form an initial population. The fitness of each chromosome in the population is evaluated based on the total cost of replenishment plan. The lower the cost, the better the fitness is. A new population of the same size is generated from the original population by manipulating its chromosomes using genetic operators. The new population is evaluated and another population is generated from it. This process continues until a stopping criterion is met. Genetic operators generate new chromosomes (children) form existing ones (parents) by manipulating the values assigned to the genes (digits) of some chromosomes (that are chosen randomly) in two ways: crossover and mutation. Every crossover operator is applied to two chromosomes (parents) and resulted in two new ones (children). Every mutation operator is applied to one chromosome and resulted in a different chromosome. The procedures of the GA for considering DLSP and COS is modeled as figure 2. All the steps will be described as following: