This paper presents a Q-learning-based algorithm for sequence and orientation optimization toward the 2D rectangular strip packingproblem. The width-filled skyline is used to represent the interior packing state, and...
详细信息
This paper presents a Q-learning-based algorithm for sequence and orientation optimization toward the 2D rectangular strip packingproblem. The width-filled skyline is used to represent the interior packing state, and a constructive rectangularpacking algorithm with the commonly adopted fitness evaluation for placement is designed. Then, the consecutive item packing is simulated as Markov Decision Process, where the state is defined as the set of already packed items, and the action is defined as the rectangle selected to be packed along with its orientation. We propose the reverse updating of Q-value in the paradigm of Q-learning and use the algorithm to optimize the sequence and orientation of the rectangles. The decreasing-size-choice mechanism in Q-learning is studied on randomly generated problems to optimize the setting of epsilon-greedy policy. We also test the Q-learning-based algorithm on the benchmark instances of C21, N13, N-series from NT, Cgcut and Beng. Compared with a few state-of-the-art algorithms, the computational results show that the proposed algorithm can produce good packing quality when adequate execution time allowed.
This article addresses the three-dimensional open-dimension rectangular packing problem (3D-ODRPP), which aims to pack a given set of unequal-size rectangular boxes within an enveloping rectangular space such that the...
详细信息
This article addresses the three-dimensional open-dimension rectangular packing problem (3D-ODRPP), which aims to pack a given set of unequal-size rectangular boxes within an enveloping rectangular space such that the volume of the occupied space is minimized. Even though the studied 3D-ODRPP is NP hard, the development of sophisticated global optimization methods has been stimulated. The mathematical programming formulation for the 3D-ODRPP has evolved into an effective and efficient mixed-integer linear programming (MILP) model. This study proposes an advanced exact scheme yielding a guaranteed global optimal solution given that all the instance data are non-negative rational numbers. The developed MILP retains not only fewer variables but also fewer constraints than the state-of-the-art models. The superior effectiveness and efficiency of the developed scheme are demonstrated with numerical experiments, where two sets of benchmark instances from references, real-world instances and instances with rational data are included.
In this paper we address a rectangular packing problem (RPP), which is one of the most difficult NP-complete problems. First, greedy biggest space sequencing (GBSS) is presented as a new placement strategy, which is v...
详细信息
ISBN:
(纸本)9783037850312
In this paper we address a rectangular packing problem (RPP), which is one of the most difficult NP-complete problems. First, greedy biggest space sequencing (GBSS) is presented as a new placement strategy, which is very essential to RPP. Then, borrowing from the respective advantages of the two algorithms, genetic algorithm (GA) and simulated annealing (SA), a hybrid optimization policy is developed. The hybrid GASA is subjected to a test using a set of benchmarks. Compared to other approaches from the literature the hybrid optimization strategy performs better.
This paper considers the rectangular packing problem and investigates the effectiveness of the neighborhood cultivation genetic algorithm (NCGA). NCGA, which we proposed, is a new algorithm in which the unique mechani...
详细信息
This paper considers the rectangular packing problem and investigates the effectiveness of the neighborhood cultivation genetic algorithm (NCGA). NCGA, which we proposed, is a new algorithm in which the unique mechanism of neighborhood crossover is combined with effective mechanisms for search in multi-objective GA proposed in the past. The effectiveness of the proposed method in typical test problems has already been investigated with satisfactory results in past studies. The rectangular packing problem, on the other hand, is applied to floor planning, such as chip area minimization in large-scale integrated circuits. It is a kind of discrete combinatorial problem in which it is known that the search is difficult and a very long time is required until the solution is obtained. This paper formulates the rectangular packing problem as a multi-objective problem with the vertical and horizontal lengths of the placement configuration as the objectives. The sequence-pair is used as the block placement representation, and PPEX is used as the crossover procedure. Using these processes, the effectiveness of NCGA is investigated. For comparison, three other methods-NSGA-II, SPEA2, and non-NCGA (NCGA without neighborhood crossover)- are investigated. (c) 2007 Wiley Periodicals, Inc.
暂无评论