Bin packing problem with restricted item fragmentation: Assignment of jobs in multi-product assembly environment with overtime

Authors

DOI:

https://doi.org/10.11121/ijocta.1435

Keywords:

Bin packing problem, Item fragmentation, Multi product assembly jobs, Mixed integer programming

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

Mustafa Ustuncelik, Department of Business Administration, Social Sciences University of Ankara, Ankara, Turkiye

Mustafa Ustuncelik is an Industrial Engineer and serves as a Planning and Control Assistant Manager at Hidromek Construction Equipment Company located in Thailand. He received his B.S. in Industrial Engineering from Eskisehir Osmangazi University in 2013 and his M.S. in Business Administration from Social Sciences University of Ankara in 2023.

Cagri Koc, Department of Business Administration, Social Sciences University of Ankara, Ankara, Turkiye

Cagri Koc is an Associate Professor in the Department of Business Administration at Social Sciences University of Ankara. He received his Ph.D. degree (2015) in Operational Research/Management Science from the Southampton Business School of University of Southampton. He worked as a Postdoctoral Fellow at HEC Montreal and at CIRRELT. His research mainly focuses on the application of mathematical and metaheuristic optimization techniques to logistics and supply chain management problems.

Huseyin Tunc, Department of Business Administration, Social Sciences University of Ankara, Ankara, Turkiye

Huseyin Tunc Tunc is Associate Professor in the Department of Business Administration at Social Sciences University of Ankara. He received his Ph.D. in Industrial and Systems Engineering from Mississippi State University in 2012. He joined the Social Sciences University of Ankara in 2019. He worked at Hacettepe University, Swiss Federal Institute of Technology in Lausanne (EPFL), and Mississippi State University.

References

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. DOI: https://doi.org/10.11121/ijocta.01.2021.00945

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. DOI: https://doi.org/10.11121/ijocta.01.2020.00825

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. DOI: https://doi.org/10.11121/ijocta.2022.1161

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. DOI: https://doi.org/10.11121/ijocta.01.2018.00572

Eilon, S., & Christofides, N. (1971). The loading problem. Management Science, 17(5), 259-268. DOI: https://doi.org/10.1287/mnsc.17.5.259

Jansen, K. (1999). An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization, 3(4), 363-377. DOI: https://doi.org/10.1023/A:1009871302966

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. DOI: https://doi.org/10.1016/j.cor.2006.10.021

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. DOI: https://doi.org/10.1016/j.ejor.2010.01.037

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. DOI: https://doi.org/10.1016/j.cor.2011.01.001

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. DOI: https://doi.org/10.1287/ijoc.1100.0406

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. DOI: https://doi.org/10.1016/j.ejor.2010.11.004

Bertazzi, L., Golden, B., & Wang, X. (2019). The bin packing problem with item fragmentation: a worst-case analysis. Discrete Applied Mathematics, 261, 63-77. DOI: https://doi.org/10.1016/j.dam.2018.08.023

Ekici, A. (2021). Bin packing problem with conflicts and item fragmentation. Computers & Operations Research, 126, 105113. DOI: https://doi.org/10.1016/j.cor.2020.105113

Casazza, M., & Ceselli, A. (2014). Mathematical programming algorithms for bin packing problems with item fragmentation. Computers & Operations Research, 46, 1-11. DOI: https://doi.org/10.1016/j.cor.2013.12.008

LeCun, B., Mautor, T., Quessette, F., & Weisser, M. A. (2015). Bin packing with fragmentable items: Presentation and approximations. Theoretical Computer Science, 602, 50-59. DOI: https://doi.org/10.1016/j.tcs.2015.08.005

Byholm, B., & Porres, I. (2018). Fast algorithms for fragmentable items bin packing. Journal of Heuristics, 24, 697-723. DOI: https://doi.org/10.1007/s10732-018-9375-z

Dokeroglu, T., & Cosar, A. (2014). Optimization of one-dimensional bin packing problem with island parallel grouping genetic algorithms. Computers & Industrial Engineering, 75, 176-186. DOI: https://doi.org/10.1016/j.cie.2014.06.002

Casazza, M. (2019). New formulations for variable cost and size bin packing problems with item fragmentation. Optimization Letters, 13(2), 379-398. DOI: https://doi.org/10.1007/s11590-018-1327-x

Ekici, A. (2022). Variable-sized bin packing problem with conflicts and item fragmentation. Computers & Industrial Engineering, 163, 107844. DOI: https://doi.org/10.1016/j.cie.2021.107844

Arbib, C., & Marinelli, F. (2017). Maximum lateness minimization in one-dimensional bin packing. Omega, 68, 76-84. DOI: https://doi.org/10.1016/j.omega.2016.06.003

Khanafer, A., Clautiaux, F., Hanafi, S., & Talbi, E. G. (2012). The min-conflict packing problem. Computers & Operations Research, 39(9), 2122-2132. DOI: https://doi.org/10.1016/j.cor.2011.10.021

Downloads

Published

2023-11-03
CITATION
DOI: 10.11121/ijocta.1435
Published: 2023-11-03

How to Cite

Ustuncelik, M., Koc, C., & Tunc, H. (2023). Bin packing problem with restricted item fragmentation: Assignment of jobs in multi-product assembly environment with overtime. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 14(1), 32–40. https://doi.org/10.11121/ijocta.1435

Issue

Vol. 14 No. 1 (2024): IJOCTA

Section

Research Articles

License

Copyright (c) 2023 Mustafa Ustuncelik, Cagri Koc, Huseyin Tunc

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.

Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.

The readers are free to:

  • Share — copy and redistribute the material in any medium or format
  • Adapt — remix, transform, and build upon the material
  • for any purpose, even commercially.
  • The licensor cannot revoke these freedoms as long as you follow the license terms.

under the following terms:

  • Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

 Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.

Crossref
Scopus
Google Scholar
Europe PMC