الگوریتم ژنتیک دو بعدی برای بسته بندی صندوق در تاریخ های مقرر

This paper considers a new variant of the two-dimensional bin packing problem where each rectangle is assigned a due date and each bin has a fixed processing time. Hence the objective is not only to minimize the number of bins, but also to minimize the maximum lateness of the rectangles. This problem is motivated by the cutting of stock sheets and the potential increased efficiency that might be gained by drawing on a larger pool of demand pieces by mixing orders, while also aiming to ensure a certain level of customer service. We propose a genetic algorithm for searching the solution space, which uses a new placement heuristic for decoding the gene based on the best fit heuristic designed for the strip packing problems. The genetic algorithm employs an innovative crossover operator that considers several different children from each pair of parents. Further, the dual objective is optimized hierarchically with the primary objective periodically alternating between maximum lateness and number of bins. As a result, the approach produces several non-dominated solutions with different trade-offs. Two further approaches are implemented. One is based on a previous Unified Tabu Search, suitably modified to tackle this revised problem. The other is randomized descent and serves as a benchmark for comparing the results. Comprehensive computational results are presented, which show that the Unified Tabu Search still works well in minimizing the bins, but the genetic algorithm performs slightly better. When also considering maximum lateness, the genetic algorithm is considerably better.

Cutting and packing problems have been the subject of extensive research over a number of years motivated by a wide range of real world applications. A typology of the cutting and packing literature can be found in Wäscher et al. (2007). This paper focusses on two-dimensional packing in which rectangles of specified dimensions are to be cut from identical stock sheets. It is related to the “two-dimensional, rectangular single bin size, bin packing problem”, which is known as 2DRSBSBPP in Wäscher et al. (2007). For brevity, we use the term two-dimensional bin packing problem, or 2DBPP, henceforth. However, rather than focussing only on the packing problem alone, we also examine issues of production planning and scheduling. In a classic 2DBPP, time is not considered an issue, and it is assumed that a rectangle can be allocated to any bin and the bins can be processed in any order. This is acceptable provided all the bins can be processed within a single production period. In this paper, we consider the issue of supplying the rectangles in a timely manner across multiple production periods, assuming that the capacity of the cutting process results in potential delays to the times at which the rectangles become available to the customer. More precisely, we assume that each stock sheet has a cutting time, and that each rectangle has an associated due date that specifies the time by which it should ideally be cut and available to the customer. As a result, the goal in this problem is to minimize the maximum lateness of the rectangles with respect to their due dates (DD) while using as few stock sheets as possible. This problem description captures the trade-off between using an ideal cutting with small waste which may result in some rectangles being delayed past their due dates, and using the due dates to group the rectangles for cutting which may result in more stock sheets being used than necessary. There are few examples in the literature of implementations that tackle both the packing problem and the production planning/scheduling problem. These papers mainly focus on cutting-stock problems and tend to separate the problem of determining the cutting patterns and the scheduling of the parts. Gramani and França (2006) examine a similar problem, which can be viewed as one of the lot sizing, where pieces may be cut early and incur a holding cost but are not permitted to be late. They use a network shortest path model to generate a solution and deal with the packing element by selecting from available patterns. Nonas and Thorstenson (2000) also tackle the combined cutting-stock and lot-sizing problem, and additionally include setup times. They specifically look at steel parts for the production of trucks, which involves cutting irregular shapes. Hendry et al. (1996) combine the one-dimensional cutting-stock problem with production scheduling in the copper industry. They implement a two-stage procedure, where the first stage determines the number of logs to be produced and how they should be cut to minimize trim loss. The second stage determines a daily production schedule. Reinertsen and Vossen (2010) also consider the one-dimensional cutting stock problem with due dates where they seek to minimize tardiness. They identify a number of industries where this problem is important and assert that this combined problem is why manual scheduling is still wide spread. Their integer programming formulation considers production periods where the sequence of patterns within each period is arbitrary. For glass cutting, Puchinger et al. (2004) combine the optimization of the cutting pattern with the scheduling of loading the wagons with the cut pieces. Only three wagons are open at any one time and only pieces intended for the same customer may be loaded onto the same wagon. They implement two branch and bound approaches for optimizing the strip and bin subproblems, and compare these approaches with evolutionary algorithms. Arbib et al. (2012) consider a similar problem. They use a tabu search implementation to minimize the number of stock sheets required to cut a given set of pieces, while constraining the maximum number of open stacks allowed by the downstream buffers. They test their approach on the one dimensional stock cutting problem and claim that their approach is valid for the two dimensional case. Zheng et al. (2012) consider a cutting stock problem where the cutting pattern significantly impacts the production process efficiency. Large steel coils are cut into smaller rectangle pieces using horizontal and vertical cuts, transferring between the direction of cut has a significant overhead. Their heuristic seeks to maximize the weighted sum of material usage and processing efficiency. Li (1996) also considers a two-dimensional cutting stock problem for the manufacture of laboratory table tops. The mixed integer programming formulation assumes a finite set of known cutting patterns and schedules the patterns in earliest due date (EDD) order. This paper proposes a genetic algorithm for solving the problem of cutting rectangles that have due dates, with the goal of minimizing the maximum lateness, while using as few bins as possible (henceforth, we refer to bins rather than stock sheets). We refer to this problem as the two-dimensional bin packing with due dates (2DBPP with DD). One contribution of this paper is addressing a problem that integrates the cutting and packing aspect with scheduling, hence taking account of how they impact on each other. For placing the rectangles in the bins, our genetic algorithm uses an adaptation of the best fit heuristic of Burke et al. (2004) for strip packing. This adaptation is our second contribution, where we show that the time complexity of Best Fit for Bin (BFB) packing is O(n2)O(n2), where n is the number of rectangles, and compare its performance to recognized bin packing placement heuristics. BFB is sufficiently fast to be used repeatedly within a genetic algorithm, and is comparable in performance with existing heuristics that are computationally more expensive. The third contribution is an investigation into the use of a multicrossover approach within the genetic algorithm for bin packing. The multicrossover operator generates several candidate offspring before selecting two that are to be retained. Further investigation of this technique and comprehensive computational results that show the benefit of adopting the multicrossover approach which are provided by Lee (2006). The remainder of this paper is organized as follows. In Section 2, we provide a formal description of the two-dimensional bin packing problem with rectangle due dates, and derive a lower bound on the maximum lateness. We review the relevant literature on two-dimensional bin packing in Section 3, including heuristic placement routines and local search methods. 4 and 5 describe our placement heuristic, called the Best Fit Bin and the multicrossover genetic algorithm, respectively, for the 2DBPP with DD. In Section 6, we describe two neighbourhood search algorithms that are adapted from the Unified Tabu Search approach of Lodi et al., 1999a, Lodi et al., 1999b and Lodi et al., 2004 which are used to help benchmark the performance of our approach. We present our comprehensive computational results in Section 7, and some concluding remarks in Section 8.

In this paper, a new two-dimensional rectangular, single bin size, bin packing problem is defined where the rectangles to be packed have associated due dates. The objective is twofold: to minimize the number of bins used, and to minimize the maximum lateness. This problem helps to build bridges between the fields of bin packing and production scheduling. A new heuristic placement routine for two-dimensional bin packing called Best Fit Bin (BFB) is described, and its performance is compared with the best performing placement heuristics in the bin packing literature. When considering both its computational complexity and solution quality, BFB is an attractive choice. A multicrossover genetic algorithm (MXGA) is proposed to solve the classical non-oriented 2DBPP, the new problem variant with due dates and also the bicriteria problem. Various devices have been introduced into the MXGA to further enhance the solutions generated. In comparative computational results for the classical 2DBPP, MXGA achieves better performance compared to a single crossover genetic algorithm, the Unified Tabu Search (UTS) method of Lodi et al., 1999a, Lodi et al., 1999b and Lodi et al., 2004, and to a randomized descent method. However, the relative quality of the results is not so clear cut for the 2DBPP with DD, where the MXGA has mixed success when compared with UTS.