Abstract: - In this paper, we present an industrial challenge faced by electronic component manufacturers.

From each order, the components need to be placed on panels for shipping. Panels incur significant costs. To

control expenses, companies are compelled to optimize the placement of components on panels. Every day,

thousands of orders have to be shipped. For each order, they have to pack between a hundred and a thousand

rectangular electronic components of different sizes on panels with specifications such as free component

orientation and tight time constraints. This packaging must be optimized to minimize the number of panels used

and associated costs. The industrial challenge lies not only in space optimization but also in the speed of the

process, with solutions needing to be found in less than a minute to meet the dynamic and continuous demands of

production and shipping.

1 Introduction

An electronic components company handles

thousands of orders daily, each order consisting of

up to a thousand components. The electronic

components from each order need to be placed on

panels for shipping. These panels have an expensive

cost. The objective is to optimize the placement of

electronic components on panels to minimize the

number of panels used and, consequently, the

bin packing problem (2D-BPP), where electronic

components are rectangular objects to be packed,

and the panels are the rectangular bins intended to

contain them. Notably, some components have free

orientation, placing the scenario within the realm of

This problem, classified NP-complete, [3],

presents particular challenges, especially for

instances involving numerous objects. The literature

addresses various types of bin-packing problems

tailored to specific applications. A typology

considering the number of dimensions, bin, and

object characteristics is described in [4]. A more

recent classification is proposed in [5], aiming to

include recent issues in cutting and arrangement.

The one-dimensional bin-packing problem (1D-

programming, [8], branch-and-price-and-cut

algorithms, [9], and hybrid intelligent algorithms for

problems with multiple size restrictions, [10]. These

studies have significantly advanced the field by

providing effective methods for solving the 1D-BPP.

The two-dimensional bin packing problem (2D-

BPP) is a challenging optimization problem with

numerous applications. In [11], a classification of

2BP problems considering orientation and guillotine

constraints is proposed. An algorithm for the

determination of the guillotine restrictions is

proposed in [12]. A first model dedicated to 2D-

BPP is introduced in [13], as an extension of their

1D-BPP approach, [14], [15]. A model based on

graph theory is proposed in [16]. The study in

competitiveness on benchmark instances, is

introduced in [19] and [20], addresses just-in-time

2D-BPP, combining bin-packing and single-

machine scheduling, proposing an integrated

constraint program as a solution.

The three-dimensional bin-packing problem (3D-

BPP) has been addressed in several studies with a

unique focus. A solution, developed in [21],

proposes an approach for pallet loading problems,

considering practical constraints such as vertical

is no subset of residual objects that can fill this

Figure 1) is therefore inevitably and permanently

lost because, in the third line of the matrix M, we

have False values from column 5 to column 3 (red

arrow in the matrix M of Figure 1). That means that

bin of size 9

Let’s take this example and add an object of size

2. We now have an instance composed of a bin of

size 9 and 5 objects of sizes 4, 3, 3, 3 and 2. The

matrix M associated with this instance is visible in

Figure 2. In this example, we know as soon as we

place object 4 that there will be no loss generated at

the end in this bin. Indeed,

󰇟󰇠󰇛

󰇣

of surfaces inside the bins: maximum surfaces and

minimum surfaces.

A surface SM is maximum if and only if there is no

coordinate in bin.

For example, in Figure 3, placing the object at the

bottom-left (0,0) position produces the two

Intersections of maximum surfaces are non-

are therefore used to determine all the possible

residual maximum surfaces, while retaining the

maximum surfaces attribute.

Placing this object in its height orientation (5,8)

generates the two minimum surfaces on the x-axis :

two minimum surfaces are shown in Figure 6.

of size (12,10). The surface in grey is the surface

We make the same calculation for the minimum

surface on the y axis. Placing this object in its height

orientation (5,8) generates the two minimum

two minimum surfaces are shown in Figure 7.

orientation, i.e. width (4,3) or height (3,4).

Placing this object in its width orientation (3,4)

generates the two minimum surfaces s on the x-axis

two minimum surfaces are shown in Figure 9.

For each minimum surface, we calculate its lost

surface SP when the object is placed. Each

size (8,5). The surface in grey is the surface area of

Let’s take the example of calculating the loss

This calculation is performed for all minimum

determining in which maximum surface each object

should be packed, and in which orientation if the

object has a free orientation.

For each object, we look for the set of maximum

surfaces in which we can place the object under

consideration. For each of these maximum surfaces,

we define a new list of maximum and minimum

surfaces. So for each object, in each area that can

by making decisive object-to-position assignments

in the bins at each step. To prevent making

expensive decisions (far from the optimum), it

In the industrial context, companies need adaptable

and modifiable solutions. The solution was modeled

as a class diagram depicted in Figure 10.

The industrial problem (Shipping) is composed of

several bin packing problems, one for each order.

Each order is composed of several components and

several panels. The problem can generate solution.