Bin packing problem with restricted item fragmentation: Assignment of jobs in multi-product assembly environment with overtime
This paper studies the assignment problem of multi product assembly jobs to days. The problem aims to minimize the amount of overtime while avoiding assembly delays for jobs that can be fragmented into smaller sub-tasks. When sequence-dependent setup times are negligible, the problem considered transforms into the bin packing problem with restricted item fragmentation where jobs represent items and days stand for bins. We present a mixed integer programming model of the problem by extending earlier formulations in the literature. Computational experiments show that the mathematical model obtained optimal solutions for majority of instances tested within reasonable computation times.
[1] Gurkan, M. E., & Tunc, H. (2021). A fix-and- optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. An International Journal of Optimization and Control: Theories & Applications, 11(1), 41-51.
[2] Cetin, K., Tuzkaya, G., & Vayvay, O. (2020). A mathematical model for personnel task assignment problem and an application for banking sector. An International Journal of Optimization and Control: Theories & Applications, 10(2), 147-158.
[3] Göçgün, Y., & Bakır, N. O. (2022). Optimal matchday schedule for Turkish professional soccer league using nonlinear binary integer programming. An International Journal of Optimization and Control: Theories & Applications, 12(2), 113-127.
[4] Koç, Ç ., Erbaş, M., & Özceylan, E. (2018). A rich vehicle routing problem arising in the replenishment of automated teller machines. An International Journal of Optimization and Control: Theories & Applications, 8(2), 276-287.
[5] Eilon, S., & Christofides, N. (1971). The loading problem. Management Science, 17(5), 259-268.
[6] Jansen, K. (1999). An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization, 3(4), 363-377.
[7] Loh, K. H., Golden, B., & Wasil, E. (2008). Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & Operations Research, 35(7), 2283-2291.
[8] Khanafer, A., Clautiaux, F., & Talbi, E. G. (2010). New lower bounds for bin packing problems with conflicts. European Journal of Operational Research, 206(2), 281-288.
[9] Crainic, T. G., Perboli, G., Rei, W., & Tadei, R.(2011). Efficient lower bounds and heuristics for the variable cost and size bin packing problem. Computers & Operations Research, 38(11), 1474- 1482.
[10] Elhedhli, S., Li, L., Gzara, M., & Naoum-Sawaya, J.(2011). A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS Journal on Computing, 23(3), 404-415.
[11] Fleszar, K., & Charalambous, C. (2011). Average- weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem. European Journal of Operational Research, 210(2), 176-184.
[12] Bertazzi, L., Golden, B., & Wang, X. (2019). The bin packing problem with item fragmentation: a worst-case analysis. Discrete Applied Mathematics, 261, 63-77.
[13] Ekici,A. (2021). Bin packing problem with conflicts and item fragmentation. Computers & Operations Research, 126, 105113.
[14] Casazza, M., & Ceselli, A. (2014). Mathematical programming algorithms for bin packing problems with item fragmentation. Computers & Operations Research, 46, 1-11.
[15] LeCun, B., Mautor, T., Quessette, F., & Weisser, M. A. (2015). Bin packing with fragmentable items: Presentation and approximations. Theoretical Computer Science, 602, 50-59.
[16] Byholm, B., & Porres, I. (2018). Fast algorithms for fragmentable items bin packing. Journal of Heuristics, 24, 697-723.
[17] Dokeroglu, T., & Cosar, A. (2014). Optimization of one-dimensional bin packing problem with island parallel grouping genetic algorithms. Computers & Industrial Engineering, 75, 176-186.
[18] Casazza, M. (2019). New formulations for variable cost and size bin packing problems with item fragmentation. Optimization Letters, 13(2), 379-398.
[19] Ekici, A. (2022). Variable-sized bin packing problem with conflicts and item fragmentation. Computers & Industrial Engineering, 163, 107844.
[20] Arbib, C., & Marinelli,F. (2017). Maximum lateness minimization in one-dimensional bin packing. Omega, 68, 76-84.
[21] Khanafer, A., Clautiaux, F., Hanafi, S., & Talbi, E. G. (2012). The min-conflict packing problem. Computers & Operations Research, 39(9), 2122- 2132.