A Parallel Hyper-heuristic Approach for the Two-dimensional Rectangular Strip-packing Problem

Abstract

In this paper, we present a parallel hyper-heuristic approach for two-dimensional rectangular strip-packing problems (2DSP). This is an island model with a special master-slave structure, and in all the islands we run a memetic algorithm-based hyper-heuristic (HH). The basic technique of this HH is a memory-based evolutionary technique, the “extended virtual loser” (EVL). The memory-based technique memorises the past events, e.g., past successes of the evolutionary process or bad values of the variables; thus, we can influence the operations of the evolutionary algorithms using thismemory. The EVL technique learns the bad values of the variables based on the worst solutions of the population and computes probabilities to control the mutation steps. With the help of the EVL technique, we can use a mutation-omitting recombination operator and obtain a learning mechanism for the selection of heuristics. In the HH, the selection of the low-level heuristics is modified with mutations based on the EVL technique using a local search. The island model achieved good performance. The test instances show that the proposed algorithm is efficient for the rectangular strip-packing problem.