Menu
The bin packing problem has been studied extensively since the 1970’s, and it is known to be applicable to many different areas, especially in operations research and computer science. In this paper, we present a variant of the classical bin packing problem, which allows the packing to exceed its bin size but at least a fraction of the last piece is within the bin, and we call it the open-end bin packing problem. This paper is focused on on-line open-end bin packing. An on-line open-end bin packing algorithm is to assign incoming pieces into the bins on-line, that is, there is no information about the sizes of the pieces in future arrivals. An on-line algorithm is optimal if it always produces a solution with the minimum number of bins used for packing. We show that no such optimal algorithm exists. We also present seven efficient on-line algorithms: Next Fit, Random Fit, Worst Fit, Best Fit, Refined Random Fit, Refined Worst Fit, and Refined Best Fit, which give sub-optimal solutions. The performances of these algorithms are studied. A case study for the application of the studied problem is presented, and this is a practical problem on maximizing the savings of using stored-value tickets issued by Kowloon-Canton Railway (KCR), which is one of the major public transportation means in Hong Kong.