Sequential batching with minimum quantity commitment in N-level non-exclusive agglomerative hierarchical clustering structures

Lim, S.

Abstract: This study considers a sequential batching problem with a minimum quantity commitment (MQC) constraint in N-level non-exclusive agglomerative hierarchical clustering structures (AHCSs). In this problem, batches are created for item types included in clusters according to the sequence of the levels in a given AHCS such that the MQC constraint as well as the maximum and minimum batch size requirements are satisfied, simultaneously. The MQC constraint ensures that more items than a committed minimum quantity must be batched at a level before items not batched at the level are sent to the next level. We apply the MQC constraint to control effectively the degree of heterogeneity (DoH) in the batching results. We developed a sequential batching algorithm for minimizing the total processing cost of items using properties identified to find better solutions of large-sized practical problems. Results of computational experiments showed that the developed algorithm found very good solutions quickly and the heuristic algorithm could be used in various practical sequential batching problems with the MQC constraint such as input lot formations in semiconductor wafer fabrication facilities, determination of truckloads in delivery service industry, etc. Also, we found some meaningful insights that dense cluster, small batch size, and tight MQC constraint are effective in reducing the total processing cost. Additionally, small batch size with loose MQC constraint seem to be helpful to reduce the DoH in the batching results. Finally, we suggested that the density of cluster, batch size, and MQC tightness should be determined simultaneously because of interactions among these factors.

How to cite this paper

        APA: Lim, S. (2020). Sequential batching with minimum quantity commitment in N-level non-exclusive agglomerative hierarchical clustering structures. International Journal of Industrial Engineering Computations, 11(3), 317-340.
    

        Chicago/Turabian: Lim, S. 2020. "Sequential batching with minimum quantity commitment in N-level non-exclusive agglomerative hierarchical clustering structures." International Journal of Industrial Engineering Computations 11, no. 3 (2020): 317-340.
    

        AMA: Lim, S. Sequential batching with minimum quantity commitment in N-level non-exclusive agglomerative hierarchical clustering structures. International Journal of Industrial Engineering Computations. 2020;11(3):317-340.
    

References

Andreopoulos, B., An, A., Wang, X., & Schroeder, M. (2009). A roadmap of clustering algorithms: finding a match for a biomedical application. Briefings in Bioinformatics, 10(3), 297-314.
Arifin, A. Z., & Asano, A. (2006). Image segmentation by histogram thresholding using hierarchical cluster analysis. Pattern Recognition Letters, 27(3), 1515-1521.
Bang, J., Kim, Y., & Choi, S. (2012). Multiproduct lot merging-splitting algorithms for semiconductor wafer fabrication. IEEE Transactions on Semiconductor Manufacturing, 25(2), 200-210.
Bang, J., Lim, S., & Kim, J. (2016). Multi-dimensional dynamic programming algorithm for input lot formation in a semiconductor wafer fabrication facility (in Korean). Journal of the Society of Korea Industrial and Systems Engineering, 39(1), 73-80.
Bouguettaya, A., Yu, Q., Zhou, X., & Song, A. (2015). Efficient agglomerative hierarchical clustering. Expert Systems with Applications, 42(5), 2785-2797.
Cameron, D.A., Middleton, F.A., Chenn, A., & Olson, E.C. (2012). Hierarchical clustering of gene expression patterns in the Eomes + lineage of excitatory neurons during early neocortical development. BMC Neuroscience, 13, 90.
Chen, H., Du, B., & Huang, G.Q. (2011). Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. International Journal of Production Research, 49(19), 5755-5778.
Cheng, L., Connor, T.R., Siren, J., Aanensen, D.M., & Corander, J. (2013). Hierarchical and spatially explicit clustering of DNA sequences with BAPS software. Molecular Biology and Evolution, 30(5), 1224-1228.
Comert, E.C., Yazgan, H.R., Kir, S., & Yener, F. (2018). A cluster first-route second approach for a capacitated vehicle routing problem: a case study. International Journal of Procurement Management, 11(4), 399-419.
Coral, D.B., Santos, M.O., & Toledo, C.F.M. (2017). Clustering-based crossover in an evolutionary algorithm for the vehicle routing problem with time windows. Proceeding of IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), 830-837.
Costa, G., Manco, G., Ortale, R., & Ritacco, E. (2013). Hierarchical clustering of XML documents focused on structural components. Data & Knowledge Engineering, 84, 26-46.
Delgoshaei, A., Delgoshaei, A., & Ali, A. (2019). Evolution of clustering techniques in designing cellular manufacturing systems: A state-of-art review. International Journal of Industrial Engineering Computations, 10(2), 177-198.
Han, X., Yu, Y., & Hu, G. (2019). A dynamic newsvendor problem with goodwill-dependent demands and minimum commitment. Omega, 89, 242-256.
Hintsch, T., & Irnich, S. (2020). Exact solution of the soft-clustered vehicle-routing problem. European Journal of Operational Research, 280(1), 164-178.
Huang, H., & Ma, Y. (2019). A hybrid clustering approach for bag-of-words image categorization. Mathematical Problems in Engineering, 2019, Article ID 4275720.
Jun, C., Lee, J., & Lee, Y. (2010). A Biclustering Method for Time Series Analysis. Industrial Engineering and Management Systems, 9(2), 131-140.
Kim, J., & Lim, S. (2012). Order-lot pegging for minimizing total tardiness in semiconductor wafer fabrication process. Journal of the Operational Research Society, 63, 1258-1270.
Langfelder, P., Zhang, B., & Horvath, S. (2008). Defining clusters from a hierarchical cluster tree: the Dynamic Tree Cut package for R. Bioinformatics, 24(5), 719-720.
Lim, A., & Xu, Z. (2006). The bottleneck problem with minimum quantity commitments. Naval Research Logistics, 53(1), 91–100.
Lim, S., Kim, J., & Kim, H. (2014). Simultaneous order-lot pegging and wafer release planning for semiconductor wafer fabrication facilities. International Journal of Production Research, 52(12), 3710-3724.
Lim, S., Kim, J., & Shin, Y. (2015). Optimal three-level presort loading of commercial bulk mail in the postal service industry. Journal of the Operational Research Society, 66(6), 1007-1022.
Lim, S., Bang, J., & Kim, J. (2017). Multi-dimensional dynamic programming algorithm for