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

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.

Keywords

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