Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/89920
Registo completo
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.author | Martinovic, J. | por |
dc.contributor.author | Strasdat, N. | por |
dc.contributor.author | Valério de Carvalho, José Manuel | por |
dc.contributor.author | Furini, F. | por |
dc.date.accessioned | 2024-03-25T09:51:10Z | - |
dc.date.issued | 2023 | - |
dc.identifier.citation | Martinovic, 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.012 | por |
dc.identifier.issn | 0377-2217 | por |
dc.identifier.uri | https://hdl.handle.net/1822/89920 | - |
dc.description | For 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/TemporalBinPacking | por |
dc.description.abstract | We 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.sponsorship | This 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.iso | eng | por |
dc.publisher | Elsevier 1 | por |
dc.relation | info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00319%2F2020/PT | por |
dc.rights | restrictedAccess | por |
dc.subject | Combinatorial optimization | por |
dc.subject | Fire ups | por |
dc.subject | Flow formulation | por |
dc.subject | Interval scheduling | por |
dc.subject | Temporal bin packing | por |
dc.title | A combinatorial flow-based formulation for temporal bin packing problems | por |
dc.type | article | - |
dc.peerreviewed | yes | por |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0377221722007810 | por |
oaire.citationStartPage | 554 | por |
oaire.citationEndPage | 574 | por |
oaire.citationIssue | 2 | por |
oaire.citationVolume | 307 | por |
dc.identifier.eissn | 1872-6860 | por |
dc.identifier.doi | 10.1016/j.ejor.2022.10.012 | por |
dc.date.embargo | 10000-01-01 | - |
dc.subject.fos | Engenharia e Tecnologia::Outras Engenharias e Tecnologias | por |
sdum.journal | European Journal of Operational Research | por |
oaire.version | VoR | por |
Aparece nas coleções: | CAlg - Artigos em revistas internacionais / Papers in international journals |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Martinovic Strasdat Carvalho Furini 2023.pdf Acesso restrito! | 5,22 MB | Adobe PDF | Ver/Abrir |