# Multidimensional Dynamic Programming Algorithm forN-Level Batching with Hierarchical Clustering Structure

Authors: Seung-Kil Lim; June-Young Bang; Jae-Gon Kim
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This study focuses on theN-level batching problem with a hierarchical clustering structure. Clustering is the task of grouping a set of item types in such a way that item types in the same cluster are more similar (in some sense or another) to each other than to those in other clusters. In hierarchical clustering structure, more and more different item types are clustered together as the level of the hierarchy increases. N-level batching is the process by which items with different types are grouped into several batches passed from level 1 to level N sequentially for given hierarchical clustering structure such that batches in each level should satisfy the maximum and minimum batch size requirements of the level. We consider two types of processing costs of the batches: unit processing cost and batch processing cost. We formulate the N-level batching problem with a hierarchical clustering structure as a nonlinear integer programming model with the objective of minimizing the total processing cost. To solve the problem optimally, we propose a multidimensional dynamic programming algorithm with an example.


---

## Body

## 1. Introduction

According to Wikipedia, clustering problem is the task of grouping a set of item types in such a way that item types in the same cluster are more similar (in some sense or another) to each other than to those in other clusters. It is the main task of exploratory data mining and a common technique for statistical data analysis, used in many fields, including machine learning, pattern recognition, image analysis, information retrieval, bioinformatics, data compression, and computer graphics. Hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types: agglomerative clustering and divisive one. Agglomerative clustering is a bottom-up approach: that is, each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. To the contrary, divisive clustering is a top-down approach: that is, all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy. In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram.The hierarchical clustering problem has been studied for several decades in a wide range of fields including manufacturing, biotechnology, information technology (IT), logistics and transportation, financial, and postal industries. In the manufacturing sector, hierarchical clustering has been used to form manufacturing cells and processing batches. Vakharia and Wemmerlöv [1] investigated the performance of seven hierarchical agglomerative clustering techniques and eight dissimilarity measures in the context of cell formation in the cellular manufacturing system. Chen et al. [2] proposed a constrained agglomerative clustering algorithm for the single batch processing machine scheduling problem often encountered in semiconductor manufacturing and metal heat treatment. Hierarchical clustering is one of the most commonly used methods in biotechnology for classification. Cheng et al. [3] suggested hierarchical model-based clustering of DNA sequences by upgrading Bayesian model-based clustering. Cameron et al. [4] proposed hierarchical clustering of gene expression patterns consistent with the lineage of differentiating excitatory neurons during early neocortical development. Saunders et al. [5] used Markov clustering and hierarchical clustering to classify protein families of rust pathogens and rank them according to their likelihood of being effectors. Barzinpour et al. [6] proposed a spectral approach to community detection, where the multiplex is mapped onto Euclidean Space (using the top few eigenvectors) and applied k-mean clustering. See Andreopoulos et al. [7] for a review of the clustering algorithms applied in bioinformatics.Clustering is one of the most important techniques for image segmentation and data analytics in the IT industry. Arifin and Asano [8] presented a histogram thresholding algorithm using hierarchical cluster analysis for image segmentation. Nunez-Iglesias et al. [9] proposed an active machine learning approach for performing hierarchical agglomerative clustering from superpixels to improve segmentation of 2D and 3D images. See Zaitoun and Aqel [10] for a survey of image segmentation techniques. In relation to data analytics, Bouguettaya et al. [11] proposed a set of agglomerative hierarchical clustering methods, and Costa et al. [12] proposed a hierarchical approach for clustering XML documents with multiple forms of structural components. Hierarchical clustering also has been successfully applied to the logistics and transportation sector. Özdamar and Demir [13] proposed a multilevel clustering algorithm that groups demand nodes into smaller clusters at each planning level for coordinating vehicle routing in large-scale postdisaster distribution and evacuation activities. Zhu and Guo [14] extended the traditional hierarchical clustering method by generalizing flows to different hierarchical levels to aggregate and map large taxi flow data in an urban area. The hierarchical clustering problem arises in the postal industry as well. Lim et al. [15] studied the three-level presorting loading problem which occurs in the commercial bulk mail service. They considered the problem as a three-level hierarchical clustering problem and proposed an optimal solution algorithm. For the financial sector application, Aghabozorgi and Teh [16] suggested a novel three-phase clustering model to categorize companies based on the similarity in the shape of their stock markets. See Murtagh and Contreras [17] for an extensive survey on the agglomerative hierarchical clustering algorithms.In this study, we consider anN-level batching with agglomerative hierarchical clustering structure in which the highest possible level of the hierarchy is N. N-level batching is the process by which items with different types are grouped into several batches passed from level 1 to level N sequentially for a given hierarchical clustering structure such that batches in each level of the hierarchy should satisfy the maximum and minimum batch size requirements of the level. We assume that types of items that can be clustered together are given in each level (i.e., hierarchical clustering structure). Also, we assume that there exist the maximum and minimum batch size requirements at each level of the hierarchy. We consider two kinds of costs for processing batched items: batch processing cost and unit processing cost. If items in a batch are closely related, they can be processed as a batch simultaneously; hence, a batch processing cost occurs to the batch. On the other hand, if items in a batch are loosely related, they have to be processed separately; hence, a unit processing cost occurs to process each item in the batch. The objective of the problem is to minimize the total cost for processing all items.


## 2.N-Level Batching Problem with Hierarchical Clustering Structure

Now we describe theN-level batching problem (NLBP) with agglomerative hierarchical clustering structure considered in this study. The paper develops an integer nonlinear programming model for the NLBP using the notations (see Notations).An integer nonlinear programming formulation for the NLBP is now presented.(1)[NLBP]  Minimize∑n=1N∑ln∈ΛUnClnUΩln+∑n=1N∑ln∈ΛBnClnBΩlnWln,(2)subjecttoQln=Rln+Ωln∀n,ln,(3)Qln=∑ln-1∈ΔlnRln-1∀n≥1,ln,(4)RlN=0∀lN,(5)ΩlnΩln/Wln≤WlnifΩlnΩln/Wln≥Dln∀n≥1,ln,(6)Dln≤ΩlnΩln/Wln≤WlnifΩlnΩln/Wln<Dln,Ωln≥Dln∀n≥1,ln,(7)Ωln=0ifQln<Dln∀n≥1,ln,(8)Qln≥0and  integer∀n,ln,(9)Ωln≥0and  integer∀n,ln,(10)Rln≥0and  integer∀n,ln.The objective function (1) to be minimized denotes the total processing cost for all batched items. Both of unit processing cost and batch processing cost are involved in the total cost. Constraint (2) balances the number of items to be batched, the number of items batched, and number of items not batched for all hierarchical clusters. Constraint (3) ensures that the total number of items to be batched at any cluster should be equal to the number of items not batched in the clusters at the immediate preceding level. Constraint (4) ensures that there is no remained item not batched until level N. Constraints (5)–(7) indicate that items batched at any cluster should satisfy both the minimum and the maximum batch size requirements. Constraints (8)–(10) represent decision variables.Figure1 provides an example of a NLBP with N=3 and nine original item types: that is, Λ0=10,20,…,90. As shown in the figure, NLBP can be represented as a network flow problem. The network consists of nine source nodes with Ql0 items to be batched through 3-level batching. That is, there are nine level-1 clusters (l1 for l=1,2,…,9) where the first level batches are formed with Ωl1 satisfying both the minimum and the maximum batch size requirements of the clusters at level 1, three level-2 clusters (l2 for l=1,2,3) where different types of items are batched (for example, four different types of items are batched at 12 cluster), one level-3 cluster where all nine item types can be batched together, and finally one destination node 0. In the network, items are taken out to form batches passed from level-1 clusters to level-3 cluster sequentially with the objective of minimizing total processing costs of batched items. Here, processing costs of batched items, in general, increase as the level of cluster is deeper. Also, the minimum and maximum batch size requirements of clusters may be different. Item quantities to be batched at level n (1≤n≤3) are the total number of items not batched at level n-1.Figure 1
An example of a NLBP withN=3 and nine original item types.Lim et al. [15] developed an optimal solution algorithm for a special type of 3-level batching problem that has tapering discount structure in unit processing cost of batched item: that is, Cl2U-Cl1U≥Cl3U-Cl2U for any l. In this study, we challenge a more general problem than that of Lim et al. [15] by extending the hierarchical level to N and considering more general cost structure for batched items. This paper develops a dynamic programming solution algorithm for the NLBP to obtain an optimal N-level batching with hierarchical clustering structure.


## 3. Dynamic Programming Algorithm for the NLBP

In the dynamic programming algorithm for the NLBP, stagenn=1,2,…,N is represented by the level and the state at a stagen is the numbers of items of cluster ln not batched yet until leveln: that is R1n,R2n,…,Rln. Also, possible alternatives at stage n are the numbers of items of cluster ln batched at leveln: that is, Ω1n,Ω2n,…,Ωln, satisfying the balancing constraints (2)–(4) and the minimum and maximum batch size constraints (5)–(7). First, we give notation used in the DP recursive equations as follows:ΨnR1n,R2n,…,Rln: the minimum processing cost for batched items during level 1 throughn when the numbers of items not batched at level n are R1n,R2n,…,RlnΓnΩ1n,Ω2n,…,Ωln: the processing cost for batched items at leveln when the numbers of items batched at level n are Ω1n,Ω2n,…,Ωln (here, ΓnΩ1n,Ω2n,…,Ωln=∑l(n)∈ΛU(n)Cl(n)UΩl(n)+∑l(n)∈ΛB(n)Cl(n)BΩl(n)/Wl(n))The forward DP recursive equations for the NLBP are(11)Ψ1R11,R21,…,Rl1=minΩl1=Rl0-Rl1∀l1Batches fromΩl1should satisfy the batch size constraints.⁡Γ1Ω11,Ω21,…,Ωl1,ΨnR1n,R2n,…,Rln=minΩln=∑l∈ΔlnRln-1-Rln∀lnBatches fromΩlnshould satisfy the batch size constraints.⁡ΓnΩ1n,Ω2n,…,Ωln+Ψn-1R1n-1,R2n-1,…,Rln-1forn=2,3,…,N-1,ΨNR1N=minΩ1N=∑l∈ΔlNRlN-1Batches fromΩ1Nshould satisfy the batch size constraints.⁡ΓNΩ1N+ΨN-1R1N-1,R2N-1,…,RlN-1.Optimal objective value for the NLBP is ΨNR1(N)=ΨN0.It is necessary to reduce the number of states for computational efficiency. We find the range ofRl(n) needed to be considered in the DP recursive equations to find an optimal solution of the NLBP when unit processing cost, ClnU, is charged for batched items.Property 1.
For a given clusterl(n) charged by unit processing cost, Rl(n)≤ClNU-ClnU/Cln+1U-ClnUR^l(n)′, where R^l(n)′ is as follows:(a)
IfQl(n)/Wl(n) is an integer, R^l(n)′=min⁡{(Ql(n)/Wl(n))·(Wl(n)-Dl(n)),Dl(n)-1}.(b)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)≥Dl(n), R^l(n)′=minQln-Qln/Wln·Dln,Dln-1.(c)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)<Dl(n), R^l(n)′=minQln-Qln/Wln·Dln,Dln-1.Proof.
LetRl(n)′ be the number of items of cluster l(n) not batched at level n and assume that Rl(n)′≤Dl(n)-1. In this case (Case 1), the maximum processing cost of cluster l(n) becomes Ωl(n)′Cl(n)U+Rl(n)′Cl(N)U when Rl(n)′ is batched at the last level N. Here, Ωl(n)′ is the number of items of cluster l(n) batched at level n with Rl(n)′ not batched items. Let Rl(n)′′ be the number of items of cluster l(n) not batched at level n but Rl(n)′′≥Dl(n). Also, let Ωl(n)′′ be the number of items of cluster l(n) batched at level n with Rl(n)′′ not batched items. In this case (Case 2), the minimum processing cost of cluster l(n) becomes Ωl(n)′′Cl(n)U+Rl(n)′′Cl(n+1)U when Rl(n)′′ is batched at the next level n+1. The difference between the maximum cost of Case 1 and the minimum cost of Case 2 is Ωl(n)′Cl(n)U+Rl(n)′Cl(N)U-(Ωl(n)′′Cl(n)U+Rl(n)′′Cl(n+1)U) = (Ωl(n)′-Ωl(n)′′)Cl(n)U+Rl(n)′Cl(N)U-Rl(n)′′Cl(n+1)U = (Rl(n)′′-Rl(n)′)Cl(n)U+Rl(n)′Cl(N)U-Rl(n)′′Cl(n+1)UsinceΩln′+Rln′=Ωln′′+Rln′′ = (Rl(n)′′-Rl(n)′)Cl(n)U+Rl(n)′Cl(N)U-Rl(n)′′Cl(n+1)U = (Cl(N)U-Cl(n)U)Rl(n)′-(Cl(n+1)U-Cl(n)U)Rl(n)′′. As a result, it is better to keep Rl(n)′≤Dl(n)-1 items not batched at level n than to keep Rl(n)′′≥Dl(n) if (Cl(N)U-Cl(n)U)Rl(n)′-(Cl(n+1)U-Cl(n)U)Rl(n)′′≤0. That is, keeping Rl(n)′ items at level n gives less processing cost of batched items if Rl(n)′′≥ClNU-ClnU/Cln+1U-ClnURl(n)′. In other words, it is sufficient to consider Rl(n)<ClNU-ClnU/Cln+1U-ClnURl(n)′ to obtain an optimal solution of the NLBP. Here, note that ClNU-ClnU/Cln+1U-ClnU≥1 since Cl(n)U<Cl(n+1)U for all n. There are three cases where Rl(n)′≤Dl(n)-1. The first case is when Ql(n)/Wl(n) is an integer. In this case, each batch can contain Wl(n) items and (Wl(n)-Dl(n)) items in each batch can remain not batched. As a result, Rl(n)′=min⁡Qln/Wln·Wln-Dln,Dln-1 in this case. The second case is when Ql(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)≥Dl(n). We can form Ql(n)/Wl(n) batches and Ql(n)-(Ql(n)/Wl(n)·Dl(n)) items can remain not batched. As a result, Rl(n)′=min⁡Qln-Qln/Wln·Dln,Dln-1 in this case. The third case is when Ql(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)<Dl(n). We can form Ql(n)/Wl(n) batches and Ql(n)-(Ql(n)/Wl(n)·Dl(n)) items can remain not batched. As a result, Rl(n)′=min⁡Qln-Qln/Wln·Dln,Dln-1 in this case. This completes the proof.LetΦln be the set of Rl(n) needed to be considered in DP recursive equations to obtain an optimal solution of the NLBP when unit processing cost, Cl(n)U, is charged for batched items.Property 2.
For a givenl(n) charged by unit processing cost satisfying 1≤n≤N-1, Φln is given as follows. (a)
IfQl(n)/Wl(n) is an integer, Φln={Rln∣0≤Rln≤ClNU-ClnU/Cln+1U-ClnUR^ln′ and Qln-Rln/Qln-Rln/Wln≥Dln} when ClNU-ClnU/Cln+1U-ClnUR^l(n)′≥Dl(n) whereas Φln=Rln∣0≤Rln≤R^ln′andQln-Rln/Qln-Rln/Wln≥Dln when ClNU-ClnU/Cln+1U-ClnUR^l(n)′≤Dl(n)-1 where R^ln′=min⁡Qln/Wln·Wln-Dln,Dln-1.(b)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)≥Dl(n), Φln={Rln∣0≤Rln≤ClNU-ClnU/Cln+1U-ClnUR^ln′ and Qln-Rln/Qln-Rln/Wln≥Dln} when (Cl(N)U-Cl(n)U)/(Cl(n+1)U-Cl(n)U)R^l(n)′≥Dl(n), whereas Φln={Rl(n)∣0≤Rl(n)≤R^l(n)′ and (Ql(n)-Rl(n))/Qln-Rln/Wl(n)≥Dl(n)} when (Cl(N)U-Cl(n)U)/(Cl(n+1)U-Cl(n)U)R^l(n)′≤Dl(n)-1, where R^l(n)′=min⁡Qln-Qln/Wln·Dln,Dln-1.(c)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)<Dl(n) and Ql(n)≥Dl(n), Φln={Rln∣Qln-Qln/Wln·Wln ≤ Rln≤ClNU-ClnU/Cln+1U-ClnUR^ln′ and Qln-Rln/Qln-Rln/Wln≥Dln} when ClNU-ClnU/Cln+1U-ClnUR^l(n)′≥Dl(n), whereas Φln={Rln∣Qln-Qln/Wln·Wln≤Rln≤R^ln′ and Qln-Rln/Qln-Rln/Wln≥Dln} when (Cl(N)U-Cl(n)U)/(Cl(n+1)U-Cl(n)U)R^l(n)′≤Dl(n)-1, where R^l(n)′=min⁡Qln-Qln/Wln·Dln,Dln-1.(d)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)<Dl(n) and Ql(n)<Dl(n), Φln=Qln.Proof.
It is obvious from Property1.The next property gives the range ofRl(n) needed to be considered in the DP recursive equations to find an optimal solution of the NLBP when batch processing cost Cl(n)B is charged instead of unit processing cost Cl(n)U.Property 3.
For a given clusterl(n) charged by batch processing cost, it is sufficient to consider Rl(n)≤Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B in DP recursive equations.Proof.
LetRl(n)′ be the number of items of cluster l(n) not batched at level n and assume that Rl(n)′≤Dl(n)-1. In this case (Case 1), the maximum processing cost of cluster l(n) becomes Ωl(n)′/Wl(n)Cl(n)B+Cl(N)B≤Ωln′/Wln+1Cl(n)B+Cl(N)B (since Ωl(n)′/Wl(n)≤(Ωl(n)′/Wl(n))+1) when Rl(n)′ is batched at the last level N. Here, Ωl(n)′ is the number of items of cluster l(n) batched at leveln with Rl(n)′ not batched items. Let Rl(n)′′ be the number of items of cluster l(n) not batched at level n but Rl(n)′′≥Dl(n). Also, let Ωl(n)′′ be the number of items of cluster l(n) batched at leveln with Rl(n)′′ not batched items. In this case (Case 2), the minimum processing cost of cluster l(n) becomes Ωl(n)′′/Wl(n)Cl(n)B+Rl(n)′′/Wl(n)Cl(n+1)B≥(Ωl(n)′′/Wl(n))Cl(n)B+(Rl(n)′′/Wl(n))Cl(n+1)B (since Ωl(n)′′/Wl(n)≤(Ωl(n)′′/Wl(n))+1 and Rl(n)′′/Wl(n)≤(Rl(n)′′/Wl(n))+1) when Rl(n)′′ is batched at the next level n+1. The difference between the maximum cost of Case 1 and the minimum cost of Case 2 is {ClnB(Ωln′-Ωln′′)/Wln}+ClNB-Cln+1BRln′′/Wln = {ClnB(Rln′-Rln′′)/Wln}+ClNB-Cln+1BRln′′/Wln since Ωl(n)′+Rl(n)′=Ωl(n)′′+Rl(n)′′. As a result, it is better to keep Rl(n)′≤Dl(n)-1 items not batched at level n than to keep Rl(n)′′≥Dl(n) if {ClnB(Rln′-Rln′′)/Wln}+ClNB-Cln+1BRln′′/Wln≤0. That is, keeping Rl(n)′ items at level n gives less processing cost of batched items if Rl(n)′′≥Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B. In other words, it is sufficient to consider Rl(n)<Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B to obtain an optimal solution of the NLBP.LetΦ~ln be the set of Rl(n) needed to be considered in DP recursive equations to obtain an optimal solution of the NLBP when batch processing cost, Cl(n)B, is charged for batched items.Property 4.
For a givenl(n) charged by batch processing cost satisfying 1≤n≤N-1, Φ~ln is given as follows. (a)
IfQl(n)/Wl(n) is an integer, Φ~ln={Rl(n)∣0≤Rl(n)≤Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B and (Ql(n)-Rl(n))/(Ql(n)-Rl(n))/Wl(n)≥Dl(n)} when Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B≥Dl(n), whereas Φ~ln={Rln∣0≤Rln≤R^ln′ and Qln-Rln/Qln-Rln/Wln≥Dln} when Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B≤Dl(n)-1, where R^l(n)′=min⁡Qln/Wln·Wln-Dln,Dln-1.(b)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)≥Dl(n), Φ~ln={Rl(n)∣0≤Rl(n)≤Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B and (Qln-Rln)/Qln-Rln/Wln≥Dln}when Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B≥Dl(n), whereas Φ~ln={Rln∣0≤Rln≤R^ln′ and Qln-Rln/Qln-Rln/Wln≥Dln} when Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B≤Dl(n)-1, where R^l(n)′=min⁡Qln-Qln/Wln·Dln,Dln-1.(c)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)<Dl(n) and Ql(n)≥Dl(n), Φ~ln={Rln∣Qln-Qln/Wln·Wln≤Rln≤Rln′ClnB+WlnClNB/ClnB+Cln+1B and Qln-Rln/Qln-Rln/Wln≥Dln} when Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B≥Dl(n), whereas Φ~ln={Rln∣Qln-Qln/Wln·Wln≤Rln≤R^ln′ and Qln-Rln/Qln-Rln/Wln≥Dln} when Rl(n)′Cl(n)B+Wl(n)Cl(N)B/Cl(n)B+Cl(n+1)B≤Dl(n)-1, where R^l(n)′=min⁡Qln-Qln/Wln·Dln,Dln-1.(d)
IfQl(n)/Wl(n) is not an integer and Ql(n)/Ql(n)/Wl(n)<Dl(n) and Ql(n)<Dl(n), Φ~(ln)=Qln.Proof.
It is obvious from Property3.Now, we can redefine the forward DP recursive equations as follows:(12)Ψ1R11,R21,…,Rl1=minΩl1=Rl0-Rl1∀l1Rl1∈Φl1∀l1∈ΛU1Rl1∈Φ~l1∀l1∈ΛB1⁡Γ1Ω11,Ω21,…,Ωl1,ΨnR1n,R2n,…,Rln=minΩln=∑l∈ΔlnRln-1-Rln∀lnRln∈Φln∀ln∈ΛUnRln∈Φ~ln∀ln∈ΛBn⁡ΓnΩ1n,Ω2n,…,Ωln+Ψn-1R1n-1,R2n-1,…,Rln-1forn=2,3,…,N-1,ΨNR1N=minΩ1N=∑l∈ΔlNRlN-1R1N∈Φ1N∀lN∈ΛUNR1N∈Φ~1N∀lN∈ΛBN⁡ΓNΩ1N+ΨN-1R1N-1,R2N-1,…,RlN-1.


## 4. An Example for the Dynamic Programming Algorithm

In this section, we give an example to explain how to solve the NLBP with the DP recursive equations. Note that this example is the same as that given in Figure1. Problem data is as follows. Here, we assume that all batched items are charged by unit processing cost.(13)Wln=100∀n,ln,Dl1=80∀l1,Dl2=75∀l2,Dl3=0∀l3,Cl1U=100∀l1,Cl2U=125∀l2,Cl3U=140∀l3,Q10=Q11=128,Q20=Q21=258,Q30=Q31=78,Q40=Q41=480,Q50=Q51=298,Q60=Q61=400,Q70=Q71=99,Q80=Q81=555,Q90=Q91=171.Table 1 shows DP calculations at the first stage. Also, the processing cost for batched items at this stage (i.e., level 1) for given (Ω11,Ω21,…,Ω91) is computed as(14)Γ1Ω11,Ω21,…,Ω91=∑l=19Ωl1Cl1U.The minimum processing cost for batched items to level 1 for given (R11,R21,…,R91) is computed as(15)Ψ1R11,R21,…,R91=minΩl1=Rl0-Rl1∀l1Rl1∈Φl1∀l1⁡Γ1Ω11,Ω21,…,Ω91.Also, we can define the set of Rl(1) needed to be considered in DP recursive equations to obtain an optimal solution of the NLBP as follows: (16)R^11′=min⁡Q11-D11·Q11W11,D11-1=min⁡128-80·128100,79=48,C13U-C11UC12U-C11UR^11′=140-100125-10048=76.8Φ11=R11∣Q11-Q11W11·W11≤R11≤R^11′,Q11-R11Q11-R11/W11≥D11,Φ11=R11∣128-128100·100≤R11≤48,128-R11128-R11/100≥80,Φ11=R11∣28≤R11≤48,128-R11128-R11/100≥80,Φ11=28,29,…,48,R^21′=min⁡Q21-D21·Q21W21,D21-1=min⁡258-100·258100,79=58,C13U-C11UC12U-C11UR^21′=140-100125-10058=92.8,Φ21=R21∣0≤R21≤C13U-C21UC12U-C21UR^21′,Q21-R21Q21-R21/W21≥D21,Φ21=R21∣0≤R21≤140-100125-10058,258-R21258-R21/100≥80,Φ21=R21∣0≤R21≤92,258-R21258-R21/100≥80,Φ21=0,1,2,…,18,58,59,…,92,Φ31=78,R^41′=min⁡Q41-D41·Q41W41,D41-1=480-80·5,79=79,C13U-C41UC12U-C41UR^41′=140-100125-10079=126.4,Φ41=R41∣0≤R41≤C13U-C41UC12U-C41UR^41′,Q41-R41Q41-R41/W41≥D41,Φ41=R41∣0≤R41≤140-100125-10079,480-R41480-R41/100≥80,Φ41=R41∣0≤R41≤126,480-R41480-R41/100≥80,Φ41=0,1,2,…,126,R^51′=min⁡Q51-D51·Q51W51,D51-1=298-80·3,79=58,C13U-C51UC22U-C51UR^51′=140-100125-10058=92.8,Φ51=R51∣0≤R51≤C13U-C51UC22U-C51UR^51′,Q51-R51Q51-R51/W51≥D51,Φ51=R51∣0≤R51≤140-100125-10058,298-R51298-R51/100≥80,Φ51=R51∣0≤R51≤92,298-R51298-R51/100≥80,Φ51=0,1,2,…,58,R^61′=min⁡Q61W61·W61-D61,D61-1=min⁡400100·100-80,79=79,C13U-C11UC12U-C11UR^61′=140-100125-10079=126.4,Φ61=R61∣0≤R61≤C13U-C61UC22U-C61UR^61′,Q61-R61Q61-R61/W61≥D61,Φ61=R61∣0≤R61≤126,400-R61400-R61/100≥80,Φ61=0,1,2,…,80,100,101,…,126,R^71′=min⁡Q71-D71·Q71W71,D71-1=min⁡99-80·1,79=19,C13U-C71UC32U-C71UR^71′=140-100125-10019=30.4,Φ71=R71∣0≤R71≤R^71′,Q71-R71Q71-R71/W71≥D71,Φ71=R71∣0≤R71≤19,99-R7199-R71/100≥80,Φ71=0,1,2,…,19,R^81′=min⁡Q81-D81·Q81W81,D81-1=min⁡555-80·6,79=75,C13U-C81UC32U-C81UR^81′=140-100125-10075=120,Φ81=R81∣0≤R81≤C13U-C81UC32U-C81UR^81′,Q81-R81Q81-R81/W81≥D81,Φ81=R81∣0≤R81≤120,555-R81555-R81/100≥80,Φ81=0,1,2,…,120,R^91′=min⁡Q91-D91·Q91W91,D91-1=min⁡171-80·2,79=11,C13U-C91UC32U-C91UR^91′=140-100125-10011=17.6,Φ91=R91∣0≤R91≤R^91′,Q91-R91Q91-R91/W91≥D91,Φ91=R81∣0≤R81≤11,171-R91171-R91/100≥80,Φ91=0,1,2,…,11.All possible states at stage 1 are defined with all combinations of R11,R21,…,R91 of the sets Φ11,Φ21,…,Φ91 and given in the first column of Table 1. That is, the number of possible states is 21×93×1×127×59×127×20×121×12. Since the time complexity of the DP algorithm depends on both the number of stages and the number of possible states at each stage, the DP algorithm has exponential time complexity because the number of states increases exponentially due to the multidimensionality from the agglomerative hierarchical clustering structure. However, we expect that the DP algorithm works well for moderate-sized problem instances because the size of the solution space can be dramatically reduced in many cases by reducing the number of states using Properties 1 and 2.Table 1
DP calculations at stage 1.
R
1
1
,
R
2
1
,
…
,
R
9
1
Ω
1
1
,
Ω
2
1
,
…
,
Ω
9
1
Γ
1
Ω
1
1
,
Ω
2
1
,
…
,
Ω
9
1
Ψ
1
R
1
1
,
R
2
1
,
…
,
R
9
1
(
28,0
,
78,0
,
0,0
,
0,0
,
0
)
(
100,258,0
,
480,298,400,99,555,171
)
100
+
⋯
+
171
×
100
=
236100
236100
(
28,0
,
78,0
,
0,0
,
0,0
,
1
)
(
100,258,0
,
480,298,400,99,555,170
)
100
+
⋯
+
170
×
100
=
236000
236000
⋯
⋯
⋯
⋯
(
48,92,78,126,58,126,19,120,11
)
(
80,166,0
,
354,240,274,80,435,160
)
(
80
+
⋯
+
160
)
×
100
=
178900
178900Table2 shows DP calculations at stage 2. The processing cost for batched items at this stage (i.e., level 2) for given (Ω12,Ω22,Ω32) is computed as(17)Γ2Ω12,Ω22,Ω32=∑l=13Ωl2Cl2U.The minimum processing cost for batched items until level 2 for given (R12,R22,R32) is computed as (18)Ψ2R12,R22,R32=minΩl2=∑l∈Δl2Rl1-Rl2∀l2Rl2∈Φl2∀l2⁡Γ2Ω12,Ω22,Ω32+Ψ1R11,R21,…,R91.Next, we define the set of Rl(2) needed to be considered in DP recursive equations to obtain an optimal solution of the NLBP as follows. As shown in Table 2, possible states at stage 2 are defined with the states at stage 1. For example, 26 states (26×1×1) at stage 2 are defined with a state (R1(1),R2(1),R3(1),R4(1),R5(1),R6(1),R7(1),R8(1),R9(1))=(28,0,78,0,0,0,0,0,0) as follows. Here, note that a state at stage 2 can be defined by several different states at stage 1. See the state R12,R22,R32=7,18,0 of Table 2. This state can be defined by the state R11,R21,R31,R41,R51,R61,R71,R81,R91=28,0,78,0,0,0,0,0,0 and the state R11,R21,R31,R41,R51,R61,R71,R81,R91=28,1,78,0,0,0,0,0,0. As a result, Ψ2R12,R22,R32 should be determined among several different states R11,R21,R31,R41,R51,R61,R71,R81,R91 at the first stage making the same state R12,R22,R32 at the second stage. (19)Q12=R11+R21+R31+R41=28+0+78+0=106,Q22=R51+R61=0+18=18,Q32=R71+R81+R91=0+0+0=0,R^12′=min⁡Q12-D12·Q12W12,D12-1=min⁡106-75·106100,74=31,C13U-C12UC13U-C12UR^12′=140-125140-12531=31,Φ12=R12∣Q12-Q12W12·W12≤R12≤R^12′,Q12-R12Q12-R12/W12≥D12,Φ12=R12∣106-106100·100≤R12≤31,106-R12106-R12/100≥75,Φ12=R12∣6≤R12≤31,106-R12106-R12/100≥75,Φ12=6,7,…,31,Φ22=18,Φ32=0.We can define 1575 states 45×35×1 with another state of stage 1, R11,R21,R31,R41,R51,R61,R71,R81,R91=48,92,78,126,58,126,19,120,11 as follows:(20)Q12=R11+R21+R31+R41=48+92+78+126=344,Q22=R51+R61=58+126=184,Q32=R71+R81+R91=19+120+11=150,R^12′=min⁡Q12-D12·Q12W12,D12-1=344-75·4,74=44,C13U-C12UC13U-C12UR^12′=140-125140-12544=44,Φ12=R12∣0≤R12≤R^12′,Q12-R12Q12-R12/W12≥D12,Φ12=R12∣0≤R12≤44,344-R12344-R12/100≥75,Φ12=0,1,2,…,44,R^22′=min⁡Q22-D22·Q22W22,D22-1=184-75·2,74=34,C13U-C22UC13U-C22UR^22′=140-125140-12534=34,Φ22=R22∣0≤R22≤R^22′,Q22-R22Q22-R22/W22≥D22,Φ22=R22∣0≤R22≤34,184-R22184-R22/100≥75,Φ22=0,1,2,…,34,R^32′=min⁡N32-D2·N32W,D2-1=150-75·2,74=0,C13U-C32UC13U-C32UR^32′=140-125140-1250=0,Φ32=R32∣0≤R32≤R^32′,Q32-R32Q32-R32/W32≥D32,Φ32=0.Table 3 shows DP calculations at stage 3. The processing cost for batched items at this stage (i.e., level 3) for given Ω13 is computed as(21)Γ3Ω13=Ω13C13U.The minimum processing cost for batched items until level 3 for given R13 is computed as(22)Ψ3R13=Ψ30=minΩ13=∑l∈Δl3Rl2R13∈Φ13⁡Γ3Ω13+Ψ2R12,R22,R32.As shown in Table 3, there exists only one state at stage 3: that is, R13=0. This means that all items should be batched until the last level.Table 2
DP calculations at stage 2.
R
1
1
,
R
2
1
,
…
,
R
9
1
R
1
2
,
R
2
2
,
R
3
2
Ω
1
2
,
Ω
2
2
,
Ω
3
2
Γ
2
Ω
1
2
,
Ω
2
2
,
Ω
3
2
+
Ψ
1
R
1
1
,
R
2
1
,
…
,
R
9
1
Ψ
2
R
1
2
,
R
2
2
,
R
3
2
(
28,0
,
78,0
,
0,0
,
0,0
,
0
)
(
6,18,0
)
(
100,0
,
0
)
100
+
0
+
0
×
125
+
236100
=
248600
(
7,18,0
)
(
99,0
,
0
)
(
99
+
0
+
0
)
×
125
+
236100
=
248475
⋯
⋯
⋯
(
31,18,0
)
(
75,0
,
0
)
75
+
0
+
0
×
125
+
236100
=
245475
(
28,0
,
78,0
,
0,0
,
0,0
,
1
)
(
6,18,1
)
(
100,0
,
0
)
100
+
0
+
0
×
125
+
236000
=
248500
(
7,18,1
)
(
99,0
,
0
)
99
+
0
+
0
×
125
+
236000
=
248375
⋯
⋯
(
31,18,1
)
(
75,0
,
0
)
75
+
0
+
0
×
125
+
236000
=
245375
⋯
⋯
⋯
⋯
(
28,1
,
78,0
,
0,0
,
0,0
,
0
)
(
7,18,0
)
(
100,0
,
0
)
100
+
0
+
0
×
125
+
236000
=
248500
(
8,18,0
)
(
99,0
,
0
)
99
+
0
+
0
×
125
+
236000
=
248375
⋯
⋯
⋯
(
32,18,0
)
(
75,0
,
0
)
75
+
0
+
0
×
125
+
236000
=
245375
⋯
⋯
⋯
⋯
(
48,92,78,126,58,126,19,120,11
)
(
0,0
,
0
)
(
344,184,150
)
(
0,1
,
0
)
(
344,183,150
)
⋯
⋯
(
44,34,0
)
(
300,150,150
)Table 3
DP calculations at stage 3.
R
1
2
,
R
2
2
,
R
3
2
R
1
3
Ω
1
3
Γ
3
Ω
1
3
+
Ψ
2
R
1
2
,
R
2
2
,
R
3
2
Ψ
3
R
1
3
(
6,18,0
)
0
24
6
+
18
+
0
×
140
+
Ψ
2
6
,
18
,
0
(
7,18,0
)
0
25
(
7
+
18
+
0
)
×
140
+
Ψ
2
7
,
18
,
0
⋯
⋯
⋯
⋯
(
44,34,0
)
0
78
(
44
+
34
+
0
)
×
140
+
Ψ
2
38
,
61,30


## 5. Concluding Remarks

In this study, we consider theN-level batching problem (NLBP) with a hierarchical clustering structure for minimizing the total cost for processing all items. In the N-level batching problem, given items with different types can be grouped into several batches at each level and this batching process is performed from level 1 to level N (from the shallower to the deeper level) sequentially in the given hierarchical clustering structure until all of given items are grouped. In this problem, we assume that the less processing cost is incurred for the batches in the shallower level, since more similar items are required to be grouped in a batch of the shallower level. Both of unit processing cost and batch processing cost are considered for batches at each level for real-world applications.We formulate the NLBP as a nonlinear integer programming model, propose a multidimensional dynamic programming algorithm for the NLBP, and develop several optimal properties by which the number of states is efficiently reduced in the proposed DP algorithm. For the clear understanding of the proposed DP algorithm and the properties, we provide the tangible example of NLBP and its solution. In the further research, we will apply the proposed algorithm to real world such as the batching processes of the semiconductor wafer fabrications to reduce the manufacturing cost. In addition, it is necessary to develop more efficient heuristic algorithms for the NLBP since the time and space complexity of the proposed DP algorithm is too high to solve large-sized problem instances.



---

*Source: 6021708-2017-04-11.xml*