Two-Bar Charts Packing Problem
- PDF / 610,147 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 236 Views
Two-Bar Charts Packing Problem Adil Erzin1
· Gregory Melidi1 · Stepan Nazarenko1 · Roman Plotnikov1
Received: 1 June 2020 / Accepted: 16 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We consider a Bar Charts Packing Problem (BCPP), in which it is necessary to pack bar charts (BCs) in a strip of minimum length. The problem is, on the one hand, a generalization of the bin packing problem (BPP) and, on the other hand, a particular case of the project scheduling problem with multidisciplinary jobs and one limited nonaccumulative resource. Earlier, we proposed a polynomial algorithm that constructs the optimal packing for a given order of non-increasing BCs. This result generalizes a similar result for BPP. We focus on the Two-Bar Charts Packing Problem (2-BCPP), where each BC consists of two bars. For this case, we show that the proposed algorithm A constructs a packing in polynomial time with a length of 2O P T + 1, where O P T is the minimum possible packing length. As far as we know, this is the first nontrivial guaranteed estimate for 2-BCPP. We also conducted a numerical experiment to compare the solutions built by our approximate algorithms with the optimal solutions constructed by the CPLEX package. The experimental results confirmed the high efficiency of the developed algorithms. Keywords Bar chart · Strip packing · APX Abbreviations A Approximation algorithm with guaranteed estimate A1 Algorithm A without the first stage A_LO Algorithm A with lexicographic preordering of BCs A1_LO Algorithm A1 with lexicographic preordering of BCs BC Bar chart 2-BC Bar chart consisting of two bars BCPP Bar Charts Packing Problem 2-BCPP Two Bar Charts Packing Problem BF Algorithm Best Fit for bin packing BLP Boolean Linear Programming
B 1
Adil Erzin [email protected] Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia 630090
123
A. Erzin et al.
BPP 2-DVPP CPLEX CPLEX1 FF FFD G GA G A_LO O PT SPP
Bin packing problem Two-dimensional vector packing problem IBM ILOG CPLEX Optimization Studio CPLEX with warm start Algorithm First Fit for bin packing Algorithm First Fit Decreasing for bin packing Order-preserving greedy algorithm Greedy algorithm Algorithm G A with lexicographic preordering of BCs Minimum packing length (the optimal value of the objective function) Strip packing problem
1 Introduction When solving the problem of optimizing the investment portfolio in the oil and gas sector, we faced the following problem [8]. Suppose that the territory of the oil and gas field is divided into subregions (clusters). For each cluster, a set of projects for its development is known. The project is characterized, in particular, by annual oil production. If we see the start year of the project, we will identify the volumes of oil production in the first and all subsequent years. The production schedule for each project can be represented in a bar chart (BC). The bar’s height corresponds to the volume of production in the corresponding year. It is required to determine the year
Data Loading...
