Cooperative Decision Model For Rectangle Packing Problem

With the development of industrial technology, packing problem is gradually favored by the modern scholars and more and more packing algorithms present in our eyes. Due to different application scenario or design view, these packing algorithms are only applicable to one class of packing instances. That is to say, for an arbitrary packing algorithm, we can always find one instance and this algorithm can not solve it well. To avoid this case, Prof. Chunping Yan put forward one optimization method based on Internet, which allows multiple packing algorithms run at the same time, and then choose the best from all the solutions as the final solution. Although this method can achieve complementarity between each packing algorithm in some extent, but because of the lack of communication between each other, they are unable to be realized more deeply complementary advantages.To maximize complementary advantages between each packing algorithm, one cooperative decision model for rectangle packing problem is proposed based on one uniform container scenario and evaluation criterion. This model consists of two basic decision patterns:1) codetermination;2) parallel decision. The former allows all the involved packing algorithms to choose the most suitable one under current packing scenario for execution between their communications; the latter allows all the involved packing algorithms execute parallel. These two decision patterns cut both ways:one can raise the space utilization and one can shorten the decision time. Therefore, these two decisions are combined, called cooperative decision, in order to raise space utilization and meanwhile shorten the decision time.Theoretical analysis indicates, with cooperative decision, the size of container scenario is never more than the number of rectangles in each packing instance, and time complexity is never more than the worst one of all involed packing algorithms.Experiments indicates, with cooperative decision, the size of container scenario is faraway less than the number of rectangles in each packing instance, and their difference is increased with the increasing number of rectangles in each packing instance. For example, the size of container scenario with cooperative decision is not more than50for each packing instance in Hopper and Turton benchmark (2001). Generally, the cooperative decision between level packing algorithms and plane packing algorithms holds much higher space utilization, and the advantage of the cooperative decision among plane packing algorithms gradually clear. Taking the decision time into account, the number of intermediate packing scenarios is always set one third of the number of rectangles in the packing instance. In this case, the cooperative decision among plane packing algorithms is not worse than the cooperative among any packing algorithms.