Printer Friendly

Multidimensional Dynamic Programming Algorithm for N-Level Batching with Hierarchical Clustering Structure.

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 Wemmerlov [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 fc-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. Ozdamar 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 an N-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 the N-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.

[mathematical expression not reproducible], (1)

[mathematical expression not reproducible], (2)

[mathematical expression not reproducible], (3)

[mathematical expression not reproducible], (4)

[mathematical expression not reproducible], (5)

[mathematical expression not reproducible], (6)

[mathematical expression not reproducible], (7)

[mathematical expression not reproducible], (8)

[mathematical expression not reproducible], (9)

[mathematical expression not reproducible]. (10)

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.

Figure 1 provides an example of a NLBP with N = 3 and nine original item types: that is, [[LAMBDA].sup.(0)] = {[1.sup.(0)], [2.sup.(0)], [9.sup.(0)]}. As shown in the figure, NLBP can be represented as a network flow problem. The network consists of nine source nodes with [mathematical expression not reproducible] items to be batched through 3-level batching. That is, there are nine level-1 clusters ([l.sup.(1)] for l = 1, 2, ..., 9) where the first level batches are formed with [mathematical expression not reproducible] satisfying both the minimum and the maximum batch size requirements of the clusters at level 1, three level-2 clusters ([l.sup.(2)] for l = 1, 2, 3) where different types of items are batched (for example, four different types of items are batched at [l.sup.(2)] 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 maybe different. Item quantities to be batched at level n (1 [less than or equal to] n [less than or equal to] 3) are the total number of items not batched at level n - 1.

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, [mathematical expression not reproducible] 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, stage n (n = 1, 2, ..., N) is represented by the level and the state at a stage n is the numbers of items of cluster not batched yet until level n: that is [mathematical expression not reproducible]. Also, possible alternatives at stage n are the numbers of items of cluster [l.sup.(n)] batched at level n: that is, [mathematical expression not reproducible], 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:

[mathematical expression not reproducible]: the minimum processing cost for batched items during level 1 through n when the numbers of items not batched at level n are [mathematical expression not reproducible]

[mathematical expression not reproducible]: the processing cost for batched items at level n when the numbers of items batched at level n are [mathematical expression not reproducible]

The forward DP recursive equations for the NLBP are

[mathematical expression not reproducible]. (11)

Optimal objective value for the [mathematical expression not reproducible].

It is necessary to reduce the number of states for computational efficiency. We find the range of [mathematical expression not reproducible] needed to be considered in the DP recursive equations to find an optimal solution of the NLBP when unit processing cost, [mathematical expression not reproducible], is charged for batched items.

Property 1. For a given cluster [l.sup.(n)] charged by unit processing cost, [mathematical expression not reproducible] is as follows:

(a) If [mathematical expression not reproducible].

(b) If [mathematical expression not reproducible].

(c) If [mathematical expression not reproducible].

Proof. Let [mathematical expression not reproducible] be the number of items of cluster [l.sup.(n)] not batched at level n and assume that [mathematical expression not reproducible]. In this case (Case 1), the maximum processing cost of cluster [mathematical expression not reproducible] is batched at the last level N. Here, [mathematical expression not reproducible] is the number of items of cluster batched at level n with [mathematical expression not reproducible] not batched items. Let [mathematical expression not reproducible] be the number of items of cluster [l.sup.(n)] not batched at level n but [mathematical expression not reproducible]. Also, let [mathematical expression not reproducible] be the number of items of cluster [l.sup.(n)] batched at level n with [mathematical expression not reproducible] not batched items. In this case (Case 2), the minimum processing cost of cluster [l.sup.(n)] becomes [mathematical expression not reproducible] 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 [mathematical expression not reproducible]. As a result, it is better to keep [mathematical expression not reproducible] items not batched at level n than to keep [mathematical expression not reproducible]. That is, keeping [mathematical expression not reproducible] items at level n gives less processing cost of batched items [mathematical expression not reproducible]. In other words, it is sufficient to consider [mathematical expression not reproducible] to obtain an optimal solution of the NLBP. Here, note that [mathematical expression not reproducible] for all n. There are three cases where [mathematical expression not reproducible]. The first case is when [mathematical expression not reproducible] is an integer. In this case, each batch can contain [mathematical expression not reproducible] items in each batch can remain not batched. As a result, [mathematical expression not reproducible] in this case. The second case is when [mathematical expression not reproducible] is not an integer and [mathematical expression not reproducible]. We can form [mathematical expression not reproducible] items can remain not batched. As a result, [mathematical expression not reproducible] in this case. The third case is when [mathematical expression not reproducible] is not an integer and [mathematical expression not reproducible]. We can form [mathematical expression not reproducible] items can remain not batched.

As a result, [mathematical expression not reproducible] in this case. This completes the proof.

Let [PHI]([l.sup.(n)]) be the set of [mathematical expression not reproducible] needed to be considered in DP recursive equations to obtain an optimal solution of the NLBP when unit processing cost, [mathematical expression not reproducible], is charged for batched items.

Property 2. For a given [l.sup.(n)] charged by unit processing cost satisfying 1 [less than or equal to] n [less than or equal to] N - 1, [PHI]([l.sup.(n)]) is given as follows.

(a) If [mathematical expression not reproducible].

(b) If [mathematical expression not reproducible].

(c) If [mathematical expression not reproducible].

(d) If [mathematical expression not reproducible].

Proof. It is obvious from Property 1.

The next property gives the range of [mathematical expression not reproducible] needed to be considered in the DP recursive equations to find an optimal solution of the NLBP when batch processing cost [mathematical expression not reproducible] is charged instead of unit processing cost [mathematical expression not reproducible].

Property 3. For a given cluster [l.sup.(n)] charged by batch processing cost, it is sufficient to consider [mathematical expression not reproducible] in DP recursive equations.

Proof. Let [mathematical expression not reproducible] be the number of items of cluster [l.sup.(n)] not batched at level n and assume that [mathematical expression not reproducible]. In this case (Case 1), the maximum processing cost of cluster [mathematical expression not reproducible] is batched at the last level N. Here, [mathematical expression not reproducible] is the number of items of cluster [l.sup.(n)] batched at level n with [mathematical expression not reproducible] not batched items. Let [mathematical expression not reproducible] be the number of items of cluster [l.sup.(n)] not batched at level n but [mathematical expression not reproducible]. Also, let [mathematical expression not reproducible] be the number of items of cluster [l.sup.(n)] batched at level n with [mathematical expression not reproducible] not batched items. In this case (Case 2), the minimum processing cost of cluster [l.sup.(n)] becomes [mathematical expression not reproducible] 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 [mathematical expression not reproducible]. As a result, it is better to keep [mathematical expression not reproducible] items not batched at level n than to keep [mathematical expression not reproducible]. That is, keeping [mathematical expression not reproducible] items at level n gives less processing cost of batched items if [mathematical expression not reproducible]. In other words, it is sufficient to consider [mathematical expression not reproducible] to obtain an optimal solution of the NLBP.

Let [??]([l.sup.(n)]) be the set of [mathematical expression not reproducible] needed to be considered in DP recursive equations to obtain an optimal solution of the NLBP whenbatchprocessingcost, [mathematical expression not reproducible], is charged for batched items.

Property 4. For a given [l.sup.(n)] charged by batch processing cost satisfying 1 [less than or equal to] n [less than or equal to] N - 1, [??]([l.sup.(n)]) is given as follows.

(a) If [mathematical expression not reproducible].

(b) If [mathematical expression not reproducible].

(c) If [mathematical expression not reproducible].

(d) If [mathematical expression not reproducible].

Proof. It is obvious from Property 3.

Now, we can redefine the forward DP recursive equations as follows:

[mathematical expression not reproducible]. (12)

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 Figure 1. Problem data is as follows. Here, we assume that all batched items are charged by unit processing cost.

[mathematical expression not reproducible]. (13)

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 [mathematical expression not reproducible] is computed as

[mathematical expression not reproducible]. (14)

The minimum processing cost for batched items to level 1 for given [mathematical expression not reproducible] is computed as

[mathematical expression not reproducible]. (15)

Also, we can define the set of fyi) needed to be considered in DP recursive equations to obtain an optimal solution of the NLBP as follows:

[mathematical expression not reproducible]. (16)

All possible states at stage 1 are defined with all combinations of [mathematical expression not reproducible] and given in the first column of Table 1. That is, the number of possible states is 21 x 93 x 1 x 127 x 59 x 127 x 20 x 121 x 12. Since the time complexity of the DP algorithm depends on both the number ofstages 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 2 shows DP calculations at stage 2. The processing cost for batched items at this stage (i.e., level 2) for given [mathematical expression not reproducible] is computed as

[mathematical expression not reproducible]. (17)

The minimum processing cost for batched items until level 2 for given [mathematical expression not reproducible] is computed as

[mathematical expression not reproducible]. (18)

Next, we define the set of Rp) 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 x 1 x 1) at stage 2 are defined with a state [mathematical expression not reproducible] as follows. Here, note that a state at stage 2 can be defined by several different states at stage 1. See the state [mathematical expression not reproducible] Table 2. This state can be defined by the state [mathematical expression not reproducible]. As a result, [mathematical expression not reproducible] should be determined among several different states [mathematical expression not reproducible] at the first stage making the same state [mathematical expression not reproducible] at the second stage.

[mathematical expression not reproducible]. (19)

We can define 1575 states (45 x 35 x 1) with another state of stage 1, [mathematical expression not reproducible] as follows:

[mathematical expression not reproducible]. (20)

Table 3 shows DP calculations at stage 3. The processing cost for batched items at this stage (i.e., level 3) for given Q1(3) is computed as

[mathematical expression not reproducible]. (21)

The minimum processing cost for batched items until level 3 for given [mathematical expression not reproducible] is computed as

[mathematical expression not reproducible]. (22)

As shown in Table 3, there exists only one state at stage 3: that is, [mathematical expression not reproducible]. This means that all items should be batched until the last level.

5. Concluding Remarks

In this study, we consider the N-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.
Notations

Parameters

n:                         Index of levels (n = 0, 1, 2, N)
[l.sup.(n)]:               Index of clusters at level n (here, note
                           that any cluster includes item types and
                           items of these item types should be
                           batched. Each cluster at level n is composed
                           of clusters at level n-1 (i.e.,
                           agglomerative hierarchical clustering
                           structure). Also, [l.sup.(0)] is the
                           index of original item types not clustered)
[[LAMBDA].sup.(n)]:        Set of all clusters at level n (here,
                           [[LAMBDA].sup.(n)] is the set of all
                           original item types not clustered)
[[LAMBDA].sup.(n).sub.U]:  Set of all clusters at level n and charged
                           by unit processing cost (here, we assume
                           that clusters charged by unit processing
                           cost are known in advance)
[[LAMBDA].sup.(n).sub.B]:  Set of all clusters at level n and charged
                           by batch processing cost (here, we assume
                           that clusters charged by batch processing
                           cost are known in advance)
[mathematical expression
  not reproducible]:       Set of clusters at level n-1 that consists
                           of cluster [mathematical expression not
                           reproducible] for all n. Also, we assume
                           that any cluster at level n-1 can be
                           included in only one cluster at level n)
[mathematical expression
  not reproducible]:       The maximum batch size requirement of
                           cluster [l.sup.(n)]
[mathematical expression
  not reproducible]:       The minimum batch size requirement of
                           cluster [l.sup.(n)]
[mathematical expression
  not reproducible]:       Unit processing cost of item batched in the
                           cluster [l.sup.(n)] (here, we assume that
                           [mathematical expression not reproducible]
[mathematical expression
  not reproducible]:       Batch processing cost of item batched in the
                           cluster [l.sup.(n)] (here, we assume that
                           [mathematical expression not reproducible]
                           for all n).

Decision Variables

[mathematical expression
  not reproducible]:       Total number of items to be batched in the
                           cluster [l.sup.(n)]
[mathematical expression
  not reproducible]:       Total number of items batched in the cluster
                           [l.sup.(n)] (here, [mathematical expression
                           not reproducible]
[mathematical expression
  not reproducible]:       Total number of items not batched in the
                           cluster [l.sup.(n)] [mathematical expression
                           not reproducible] Also, [mathematical
                           expression not reproducible] is the number
                           of items in the cluster [l.sup.(0)] to
                           be batched).


Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

This work was supported by the Incheon National University (International Cooperative) Research Grant in 2013.

References

[1] A. J. Vakharia and U. Wemmerlov, "A comparative investigation of hierarchical clustering techniques and dissimilarity measures applied to the cell formation problem," Journal of Operations Management, vol. 13, no. 2, pp. 117-138, 1995.

[2] H. Chen, B. Du, and G. Q. Huang, "Scheduling a batch processing machine with non-identical job sizes: a clustering perspective," International Journal of Production Research, vol. 49, no. 19, pp. 5755-5778, 2011.

[3] L. Cheng, T. R. Connor, J. Siren, D. M. Aanensen, and J. Corander, "Hierarchical and spatially explicit clustering of DNA sequences with BAPS software," Molecular Biology and Evolution, vol. 30, no. 5, pp. 1224-1228, 2013.

[4] D. A. Cameron, F. A. Middleton, A. Chenn, and E. C. Olson, "Hierarchical clustering of gene expression patterns in the Eomes + lineage of excitatory neurons during early neocortical development," BMC Neuroscience, vol. 13, no. 1, article 90, 2012.

[5] D. G. O. Saunders, J. Win, L. M. Cano, L. J. Szabo, S. Kamoun, and S. Raffaele, "Using hierarchical clustering of secreted protein families to classify and rank candidate effectors of rust fungi," PLoS ONE, vol. 7, no. 1, Article ID e29847, 2012.

[6] F. Barzinpour, B. H. Ali-Ahmadi, S. Alizadeh, and S. Golamreza Jalali Naini, "Clustering networks' heterogeneous data in defining a comprehensive closeness centrality index," Mathematical Problems in Engineering, vol. 2014, Article ID 202350,10 pages, 2014.

[7] B. Andreopoulos, A. An, X. Wang, and M. Schroeder, "A roadmap of clustering algorithms: finding a match for a biomedical application," Briefings in Bioinformatics, vol. 10, no. 3, pp. 297-314, 2009.

[8] A. Z. Arifin and A. Asano, "Image segmentation by histogram thresholding using hierarchical cluster analysis," Pattern Recognition Letters, vol. 27, no. 13, pp. 1515-1521, 2006.

[9] J. Nunez-Iglesias, R. Kennedy, T. Parag, J. Shi, and D. B. Chklovskii, "Machine learning of hierarchical clustering to segment 2D and 3D images," PLoS ONE, vol. 8, no. 8, Article ID e71715, 2013.

[10] N. M. Zaitoun and M. J. Aqel, "Survey on image segmentation techniques," Procedia Computer Science, vol. 65, pp. 797-806, 2015.

[11] A. Bouguettaya, Q. Yu, X. Liu, X. Zhou, and A. Song, "Efficient agglomerative hierarchical clustering," Expert Systems with Applications, vol. 42, no. 5, pp. 2785-2797, 2015.

[12] G. Costa, G. Manco, R. Ortale, and E. Ritacco, "Hierarchical clustering of XML documents focused on structural components," Data and Knowledge Engineering, vol. 84, pp. 26-46, 2013.

[13] L. Ozdamar and O. Demir, "A hierarchical clustering and routing procedure for large scale disaster relief logistics planning," Transportation Research PartE, vol. 48, no. 3, pp. 591-602, 2012.

[14] X. Zhu and D. Guo, "Mapping large spatial flow data with hierarchical clustering," Transactions in GIS, vol. 18, no. 3, pp. 421-435, 2014.

[15] S.-K. Lim, J.-G. Kim, and Y.-H. Shin, "Optimal three-level presort loading of commercial bulk mail in the postal service industry," Journal of the Operational Research Society, vol. 66, no. 6, pp. 1007-1022, 2015.

[16] S. Aghabozorgi and Y. W. Teh, "Stock market co-movement assessment using a three-phase clustering method," Expert Systems with Applications, vol. 41, no. 4, pp. 1301-1314, 2014.

[17] F. Murtagh and P. Contreras, "Algorithms for hierarchical clustering: an overview," Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 2, no. 1, pp. 86-97, 2012.

https://doi.org/10.1155/2017/6021708

Seung-Kil Lim, (1) June-Young Bang, (1) and Jae-Gon Kim (2)

(1) Department of Industrial and Management Engineering, Sungkyul University, 400-10 Anyang-dong Manan-gu, Anyang-si, Gyeonggi-do 14097, Republic of Korea

(2) Department of Industrial and Management Engineering, Incheon National University, 12-1 Songdo-dong, Yeonsu-gu, Incheon 22012, Republic of Korea

Correspondence should be addressed to Jae-Gon Kim; jaegkim@inu.ac.kr

Received 23 December 2016; Revised 3 March 2017; Accepted 6 March 2017; Published 11 April 2017

Academic Editor: Sergii V. Kavun

Caption: Figure 1: An example of a NLBP with N = 3 and nine original item types.
Table 1: DP calculations at stage 1.

[mathematical expression              [mathematical expression
not reproducible]                         not reproducible]

(28,0,78,0,0,0,0,0,0)             (100,258,0,480,298,400,99,555,171)
(28,0,78,0,0,0,0,0,1)             (100,258,0,480,298,400,99,555,170)
....
(48,92,78,126,58,126,19,120,11)   (80,166,0,354,240,274,80,435,160)

[mathematical expression             [mathematical expression
not reproducible]                        not reproducible]

(28,0,78,0,0,0,0,0,0)             (100+ ... + 171) x 100 = 236100
(28,0,78,0,0,0,0,0,1)             (100 + ... + 170) x 100 = 236000
....
(48,92,78,126,58,126,19,120,11)   (80 + ... + 160) x 100 = 178900

[mathematical expression          [mathematical expression
not reproducible]                    not reproducible]

(28,0,78,0,0,0,0,0,0)                      236100
(28,0,78,0,0,0,0,0,1)                      236000
....
(48,92,78,126,58,126,19,120,11)            178900

Table 2: DP calculations at stage 2.

[mathematical expression   [mathematical expression
not reproducible]             not reproducible]

(28,0,78,0,0,0,0,0,0)              (6,18,0)
                                   (7,18,0)
                                     ...
                                  (31,18,0)
(28,0,78,0,0,0,0,0,1)              (6,18,1)
                                   (7,18,1)

                                  (31,18,1)
                                     ...
(28,1,78,0,0,0,0,0,0)              (7,18,0)
                                   (8,18,0)
                                     ...
                                  (32,18,0)
                                     ...
(48,92,78,126,58,126,             (0, 0, 0)
19,120,11)                         (0,1,0)
                                     ...
                                  (44,34,0)

[mathematical expression   [mathematical expression
not reproducible]             not reproducible]

(28,0,78,0,0,0,0,0,0)             (100,0,0)
                                   (99,0,0)
                                     ...
                                   (75,0,0)
(28,0,78,0,0,0,0,0,1)             (100,0,0)
                                  (99, 0, 0)

                                  (75, 0, 0)

(28,1,78,0,0,0,0,0,0)             (100,0,0)
                                   (99,0,0)
                                     ...
                                   (75,0,0)
                                     ...
(48,92,78,126,58,126,           (344,184,150)
19,120,11)                      (344,183,150)
                                     ...
                                (300,150,150)

[mathematical expression         [mathematical expression
not reproducible]                    not reproducible]

(28,0,78,0,0,0,0,0,0)      (100 + 0 + 0) x 125 + 236100 = 248600
                           (99 + 0 + 0) x 125 + 236100 = 248475
                                            ...
                           (75 + 0 + 0) x 125 + 236100 = 245475
(28,0,78,0,0,0,0,0,1)      (100 + 0 + 0) x 125 + 236000 = 248500
                           (99 + 0 + 0) x 125 + 236000 = 248375

                           (75 + 0 + 0) x 125 + 236000 = 245375
                                            ...
(28,1,78,0,0,0,0,0,0)      (100 + 0 + 0) x 125 + 236000 = 248500
                           (99 + 0 + 0) x 125 + 236000 = 248375
                                            ...
                           (75 + 0 + 0) x 125 + 236000 = 245375
                                            ...
(48,92,78,126,58,126,
19,120,11)

[mathematical expression   [mathematical expression
not reproducible]             not reproducible]

(28,0,78,0,0,0,0,0,0)

(28,0,78,0,0,0,0,0,1)

(28,1,78,0,0,0,0,0,0)

(48,92,78,126,58,126,
19,120,11)

Table 3: DP calculations at stage 3.

[mathematical expression   [mathematical expression
not reproducible]             not reproducible]

(6,18,0)                              0

(7,18,0)                              0

(44,34,0)                             0

[mathematical expression   [mathematical expression
not reproducible]             not reproducible]

(6,18,0)                              24

(7,18,0)                              25

(44,34,0)                             78

[mathematical expression       [mathematical expression
not reproducible]                  not reproducible]

(6,18,0)                   (6 + 18 + 0) x 140 + [[PSI].sub.2]
                                        (6,18,0)
(7,18,0)                   (7 + 18 + 0) x 140 + [[PSI].sub.2]
                                        (7,18,0)
(44,34,0)                  (44 + 34 + 0) x 140 + [[PSI].sub.2]
                                       (38,61,30)

[mathematical expression   [mathematical expression
not reproducible]             not reproducible]

(6,18,0)

(7,18,0)

(44,34,0)
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Lim, Seung-Kil; Bang, June-Young; Kim, Jae-Gon
Publication:Mathematical Problems in Engineering
Article Type:Report
Date:Jan 1, 2017
Words:5147
Previous Article:Topology Detection for Output-Coupling Weighted Complex Dynamical Networks with Coupling and Transmission Delays.
Next Article:Disc Brake Vibration Model Based on Stribeck Effect and Its Characteristics under Different Braking Conditions.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters