Two-bar charts packing problem

DOI10.1007/S11590-020-01657-1MaRDI QIDQ2047190zbMATH OpenOpenAlexFDO

Authors Gregory Melidi, Stepan Nazarenko, Roman Plotnikov, A. I. Erzin

Publication date 19 August 2021

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.14195

zbMATH Keywords

strip packingbar chartAPX

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

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 non-accumulative resource. Earlier, we proposed a polynomial algorithm that constructs the optimal package for a given order of non-increasing BCs. This result generalizes a similar result for BPP. For Two-Bar Charts Packing Problem (2-BCPP), when each BC consists of two bars, the algorithm we have proposed constructs a package in polynomial time, the length of which does not exceed $2OPT+1$, where $OPT$ is the minimum possible length of the packing. As far as we know, this is the first guaranteed estimate for 2-BCPP. We also conducted a numerical experiment in which we compared the solutions built by our approximate algorithms with the optimal solutions built by the CPLEX package. The experimental results confirmed the high efficiency of the developed algorithms.

Recommendations

• A 3/2-approximation for big two-bar charts packing
• A posteriori analysis of the algorithms for two-bar charts packing problem
• The problem of strip packing: An asymptotically exact approach
• A heuristic algorithm for the non-oriented 2D rectangular strip packing problem
• Complexity results for the horizontal bar packing problem

Cites work

• A 2.5 times optimal algorithm for packing in two dimensions
• A 71/60 theorem for bin packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A \((5/3+\varepsilon)\)-approximation for strip packing
• A branch-and-price algorithm for the two-dimensional vector packing problem
• A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing
• A new proof for the first-fit decreasing bin-packing algorithm
• A self-adapting genetic algorithm for project scheduling under resource constraints
• A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• A stochastic greedy algorithm for the resource-constrained project scheduling problem
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• Approximation and online algorithms for multidimensional bin packing: a survey
• Combinatorial Benders' cuts for the strip packing problem
• Experimental investigation of heuristics for resource-constrained project scheduling: an update
• Genetic algorithm for the resource-constrained project scheduling problem
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Improved Approximation for Vector Bin Packing
• On solvability of the project scheduling problem with accumulative resources of an arbitrary sign
• On some implementations of solving the resource constrained project scheduling problems
• Optimal investment in the development of oil and gas field
• Orthogonal Packings in Two Dimensions
• PSPLIB -- a project scheduling problem library
• Packing of one-dimensional bins with contiguous selection of identical items: an exact method of optimal solution
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)

Cited in

(6)

• A 4/3 OPT+2/3 approximation for big two-bar charts packing problem
• A 3/2-approximation for big two-bar charts packing
• Three-Bar Charts Packing Problem
• An improved approximation for packing big two-bar charts
• A posteriori analysis of the algorithms for two-bar charts packing problem
• Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem

Describes a project that uses

Uses Software

• PSPLIB
• CPLEX

This page was built for publication: Two-bar charts packing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2047190)