## 2 Literature Review
### Bin Packing Problem  
The bin packing problem (BPP) is an optimization problem aimed at determining the minimum number of containers (bins) required to pack items of different sizes, where each item has a given and fixed capacity. This problem has numerous applications, such as determining the number of containers needed for transportation, truck capacity planning, and resource management across various industries. The one-dimensional BPP is one of the most well-known problems in combinatorial optimization. Its structure and applications have been studied since the 1930s [5]. BPP is classified as an NP-hard problem, meaning no polynomial-time algorithm guarantees an optimal solution for all cases. However, BPP remains a central topic in combinatorial optimization, drawing considerable attention in recent years. [PERSON]. [6] addressed a set of 80 instances of BPP, widely regarded as algorithmically challenging, and demonstrated that effective solutions can be obtained using advanced heuristic methods. In a related context, [PERSON]. [7] explored the complexity of dimension reduction on the probability simplex, offering valuable insights into reducing computational overhead. This idea holds potential relevance for high-dimensional or multi-parameter variants of the BPP. [PERSON]. [8] contributed an alternative approach by formulating a two-dimensional cutting stock problem related to BPP using the Ising model. Their work illustrates the benefits of mapping complex combinatorial problems into physical models to explore novel solution methods. Together, these studies provide a solid foundation for the present work, both from an algorithmic perspective and broader practical implications. The problem can be extended to multiple dimensions, with the simplest and most fundamental version being the one-dimensional bin packing problem (1 BPP). In this case, each item has a single size parameter, and the objective is to pack a finite set of items into the smallest possible number of bins [9]. The process begins by establishing an upper bound (U) on the required number of bins, usually obtained via a heuristic approach. This serves both as an approximation of the optimal solution and a basis for subsequent optimization. Given the computational difficulty of solving large instances exactly, heuristic methods are typically employed to generate this initial estimate [10]. According to [11], the integer linear program (ILP), given in (1), may optimally solve small BPP problems. \[ \begin{array}{ll}&\min\ \sum\limits_{i=1}^{U}y_{i}\\ &s.t.\ \sum\limits_{j=1}^{U}w_{j}\times x_{i,j}\leq c\times y_{i}\ \ \ (i=1,2,\ldots,U)\\ &\sum\limits_{i=1}^{U}x_{i,j}=1\ \ \ \ \ \ \ \ \ \ \ \ (j=1,2,\ldots,n)\\ &y_{i}\in\{0,1\}\ \ \ (i=1,2,\ldots,U)\\ &x_{i,j}\in\{0,1\}\ \ \ (i=1,2,\ldots,U;\ j=1,2,\ldots,n)\end{array}  \tag{1}\]  
where,  
\(n\)--the number of items should be packed in the bins. \(W_{i}\)--the weight (or size) of item \(j\) (\(j=1,2,\ldots,n\)). \(c\)--the capacity of each bin. The constraints impose that any used bin's capacity is not exceeded and that each item is packed into exactly one bin. The variables \(\{x_{i},y_{i}\}\) are binary decision variables that are defined as:  
\[y_{i}=\begin{cases}1\ \ \text{if bin $i$ is used in the solution;}\\ 0\ \bound. Its input is a sorted list of items of different sizes. Its output is a partition of the items into bins of fixed capacity. For more details about the FFD, see [12] who proved that:  
\[U\leq\frac{11}{9}M^{*}+\frac{6}{9}\]  
where \(M^{*}\) is the optimal minimum number of needed bins. The bin packing problem with conflicts (BPC) is an extended version of the BPP. BPC aims to minimize the number of bins required to pack a given set of items while introducing the additional constraint that certain items cannot be placed in the same bin due to compatibility restrictions (for further details, see [13], and references therein). In our proposed model, we apply the BPP, where each production batch is treated as an \"item\" that needs to be processed on a machine (the bin).