Utilize este identificador para referenciar este registo: https://hdl.handle.net/1822/89920

Registo completo
Campo DCValorIdioma
dc.contributor.authorMartinovic, J.por
dc.contributor.authorStrasdat, N.por
dc.contributor.authorValério de Carvalho, José Manuelpor
dc.contributor.authorFurini, F.por
dc.date.accessioned2024-03-25T09:51:10Z-
dc.date.issued2023-
dc.identifier.citationMartinovic, J., Strasdat, N., Valério de Carvalho, J., & Furini, F. (2023, June). A combinatorial flow-based formulation for temporal bin packing problems. European Journal of Operational Research. Elsevier BV. http://doi.org/10.1016/j.ejor.2022.10.012por
dc.identifier.issn0377-2217por
dc.identifier.urihttps://hdl.handle.net/1822/89920-
dc.descriptionFor clarity, the instances used in this paper have been gathered together at https://github.com/wotzlaff/tbpp-instances. However, we note that most of these instances were originally designed in Aydin et al. (2020) and Dell’Amico et al. (2020), and some of them were already available online, see https://github.com/sibirbil/TemporalBinPackingpor
dc.description.abstractWe consider two neighboring generalizations of the classical bin packing problem: the temporal bin pack ing problem (TBPP) and the temporal bin packing problem with fire-ups (TBPP-FU). In both cases, the task is to arrange a set of given jobs, characterized by a resource consumption and an activity window, on ho mogeneous servers of limited capacity. To keep operational costs but also energy consumption low, TBPP is concerned with minimizing the number of servers in use, whereas TBPP-FU additionally takes into ac count the switch-on processes required for their operation. Either way, challenging integer optimization problems are obtained, which can differ significantly from each other despite the seemingly only marginal variation of the problems. In the literature, a branch-and-price method enriched with many preprocessing steps (for TBPP) and compact formulations (for TBPP-FU), benefiting from numerous reduction methods, have emerged as, currently, the most promising solution methods. In this paper, we introduce, in a sense, a unified solution framework for both problems (and, in fact, a wide variety of further interval scheduling applications) based on graph theory. Any scientific contributions in this direction failed so far because of the exponential size of the associated networks. The approach we present in this article does not change the theoretical exponentiality itself, but it can make it controllable by clever construction of the resulting graphs. In particular, for the first time all classical benchmark instances (and even larger ones) for the two problems can be solved – in times that significantly improve those of the previous approaches.por
dc.description.sponsorshipThis work has been supported by FCT – Fundação para a Ciência e Tecnologia within the R&D Units Project Scope UIDB/00319/2020.por
dc.language.isoengpor
dc.publisherElsevier 1por
dc.relationinfo:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00319%2F2020/PTpor
dc.rightsrestrictedAccesspor
dc.subjectCombinatorial optimizationpor
dc.subjectFire upspor
dc.subjectFlow formulationpor
dc.subjectInterval schedulingpor
dc.subjectTemporal bin packingpor
dc.titleA combinatorial flow-based formulation for temporal bin packing problemspor
dc.typearticle-
dc.peerreviewedyespor
dc.relation.publisherversionhttps://www.sciencedirect.com/science/article/pii/S0377221722007810por
oaire.citationStartPage554por
oaire.citationEndPage574por
oaire.citationIssue2por
oaire.citationVolume307por
dc.identifier.eissn1872-6860por
dc.identifier.doi10.1016/j.ejor.2022.10.012por
dc.date.embargo10000-01-01-
dc.subject.fosEngenharia e Tecnologia::Outras Engenharias e Tecnologiaspor
sdum.journalEuropean Journal of Operational Researchpor
oaire.versionVoRpor
Aparece nas coleções:CAlg - Artigos em revistas internacionais / Papers in international journals

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Martinovic Strasdat Carvalho Furini 2023.pdf
Acesso restrito!
5,22 MBAdobe PDFVer/Abrir

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID