Heuristic/meta-heuristic methods for restricted bin packing problem
- PDF / 528,103 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 238 Views
Heuristic/meta-heuristic methods for restricted bin packing problem Yu Fu1 · Amarnath Banerjee1 Received: 9 November 2018 / Revised: 17 December 2019 / Accepted: 18 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper addresses a special bin packing problem in which each item can only be assigned to a subset of the bins. We name this problem as the restricted bin packing problem (RBPP). This paper is designed to explore the relationships of RBPP with classic NP-complete problems, and to resolve the restrictions of assignment through heuristic and meta-heuristic algorithms. A new heuristic algorithm named ‘Max-fit Based on Zigzag Sorting with Retained Feasibility’ is proposed. In this heuristic algorithm, a feasibility retaining rule is constructed to assure the assignment of every item; a zigzag sorting method is designed to improve the performance of the algorithm. Our heuristic algorithm is able to generate better results in comparison with existing heuristics. Greedy Randomized Adaptive Search Procedure (GRASP) and Simulated Annealing (SA) are exploited to obtain better solutions for RBPP. A new construction method based on cliques and zigzag sorting are built for GRASP and SA. The proposed methods are shown to have higher efficiency than traditional ones through numeric examples. Keywords Assignment · Zigzag sorting · GRASP · Simulated annealing · Bin packing
1 Introduction Bin packing problem (BPP), which was studied for the first time by Johnson (1974), is a classic problem to assign n items with size in (0, 1] into n bins with capacity of 1, and minimize the number of bins used. BPP is proved to be NP-complete (Blazewicz and Ecker 1983; Blazewicz et al. 1993). This paper studies the restricted bin packing
B
Amarnath Banerjee [email protected] Yu Fu [email protected]
1
Department of Industrial and Systems Engineering, Texas A&M University, College Station, USA
123
Y. Fu, A. Banerjee
problem (RBPP), which is different from BPP in the preference of the items over the bins. Unlike BPP in which any item can be assigned to any bin; in RBPP, some items cannot be assigned to some bins even if the bins have enough space. RBPP has a wide application in reality. For example: in the transportation box packing problem, the carrier may want to put items for the same destination together and save more spaces. In the time-window job shop problem, the machines may have limits on type of jobs that can be handled. In the clinic patient assignment problem, patients have preference over time blocks and physicians, and the clinic may prefer to reserve more blank time blocks for future schedule. In the TV commercial scheduling problem, advertisements have restrictions on the TV programs based time slots. The main contribution of this paper is to give insight analysis of the restricted bin packing problem and to provide algorithms which can find better solutions in shorter time in comparison with existing methods. The remainder of this paper is arranged in the followin
Data Loading...
