IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v42y2021i1d10.1007_s10878-021-00741-1.html
   My bibliography  Save this article

A 3/2-approximation for big two-bar charts packing

Author

Listed:
  • Adil Erzin

    (Sobolev Institute of Mathematics)

  • Georgii Melidi

    (Sobolev Institute of Mathematics)

  • Stepan Nazarenko

    (Sobolev Institute of Mathematics)

  • Roman Plotnikov

    (Sobolev Institute of Mathematics)

Abstract

We consider a Two-Bar Charts Packing Problem (2-BCPP), in which it is necessary to pack two-bar charts (2-BCs) in a unit-height strip of minimum length. The problem is a generalization of the Bin Packing Problem. Earlier, we proposed an $$O(n^2)$$ O ( n 2 ) –time algorithm that constructs the packing of n arbitrary 2-BCs, whose length is at most $$2\cdot OPT+1$$ 2 · O P T + 1 , where OPT is the minimum packing length. This paper proposes two new 3/2–approximate algorithms based on sequential matching. One has time complexity $$O(n^4)$$ O ( n 4 ) and is applicable when at least one bar of each 2-BC is greater than 1/2. Another has time complexity $$O(n^{3.5})$$ O ( n 3.5 ) and is applicable when, additionally, all BCs are non-increasing or non-decreasing. We prove the estimate’s tightness and conduct a simulation to compare the constructed packings with the optimal solutions or a lower bound of optimum.

Suggested Citation

  • Adil Erzin & Georgii Melidi & Stepan Nazarenko & Roman Plotnikov, 2021. "A 3/2-approximation for big two-bar charts packing," Journal of Combinatorial Optimization, Springer, vol. 42(1), pages 71-84, July.
    • Handle: RePEc:spr:jcomop:v:42:y:2021:i:1:d:10.1007_s10878-021-00741-1
    DOI: 10.1007/s10878-021-00741-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-021-00741-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-021-00741-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kolisch, Rainer & Hartmann, Sonke, 2006. "Experimental investigation of heuristics for resource-constrained project scheduling: An update," European Journal of Operational Research, Elsevier, vol. 174(1), pages 23-37, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    2. Anurag Agarwal, 2009. "Theoretical insights into the augmented-neural-network approach for combinatorial optimization," Annals of Operations Research, Springer, vol. 168(1), pages 101-117, April.
    3. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    4. Ranjbar, Mohammad & De Reyck, Bert & Kianfar, Fereydoon, 2009. "A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling," European Journal of Operational Research, Elsevier, vol. 193(1), pages 35-48, February.
    5. Alireza Etminaniesfahani & Hanyu Gu & Leila Moslemi Naeni & Amir Salehipour, 2024. "An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 41-68, July.
    6. Cédric Verbeeck & Vincent Peteghem & Mario Vanhoucke & Pieter Vansteenwegen & El-Houssaine Aghezzaf, 2017. "A metaheuristic solution approach for the time-constrained project scheduling problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 353-371, March.
    7. F. Perez & T. Gomez, 2016. "Multiobjective project portfolio selection with fuzzy constraints," Annals of Operations Research, Springer, vol. 245(1), pages 7-29, October.
    8. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    9. Li, Haitao & Womer, Norman K., 2015. "Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming," European Journal of Operational Research, Elsevier, vol. 246(1), pages 20-33.
    10. Jürgen Kuster & Dietmar Jannach & Gerhard Friedrich, 2010. "Applying Local Rescheduling in response to schedule disruptions," Annals of Operations Research, Springer, vol. 180(1), pages 265-282, November.
    11. Colvin, Matthew & Maravelias, Christos T., 2011. "R&D pipeline management: Task interdependencies and risk management," European Journal of Operational Research, Elsevier, vol. 215(3), pages 616-628, December.
    12. Zhu, Xia & Ruiz, Rubén & Li, Shiyu & Li, Xiaoping, 2017. "An effective heuristic for project scheduling with resource availability cost," European Journal of Operational Research, Elsevier, vol. 257(3), pages 746-762.
    13. Hongbo Li & Linwen Zheng & Hanyu Zhu, 2023. "Resource leveling in projects with flexible structures," Annals of Operations Research, Springer, vol. 321(1), pages 311-342, February.
    14. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    15. Lova, Antonio & Tormos, Pilar & Cervantes, Mariamar & Barber, Federico, 2009. "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes," International Journal of Production Economics, Elsevier, vol. 117(2), pages 302-316, February.
    16. Karakaya, Sırma & Balcik, Burcu, 2024. "Developing a national pandemic vaccination calendar under supply uncertainty," Omega, Elsevier, vol. 124(C).
    17. Vaseghi, Forough & Martens, Annelies & Vanhoucke, Mario, 2024. "Analysis of the impact of corrective actions for stochastic project networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 503-518.
    18. Krüger, Doreen & Scholl, Armin, 2009. "A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times," European Journal of Operational Research, Elsevier, vol. 197(2), pages 492-508, September.
    19. Yagub Alipouri & Mohammad Hassan Sebt & Abdollah Ardeshir & Mohammad Hossein Fazel Zarandi, 2020. "A mixed-integer linear programming model for solving fuzzy stochastic resource constrained project scheduling problem," Operational Research, Springer, vol. 20(1), pages 197-217, March.
    20. Gutjahr, Walter J. & Katzensteiner, Stefan & Reiter, Peter & Stummer, Christian & Denk, Michaela, 2010. "Multi-objective decision analysis for competence-oriented project portfolio selection," European Journal of Operational Research, Elsevier, vol. 205(3), pages 670-679, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:42:y:2021:i:1:d:10.1007_s10878-021-00741-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.