Worst-case analysis of heuristic approaches for the temporal bin packing problem with fire-ups

Martinovic, John; Strasdat, Nico Article — Published Version Worst-case analysis of heuristic approaches for the temporal bin packing problem with fire-ups Annals of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Martinovic, John; Strasdat, Nico (2023) : Worst-case analysis of heuristic approaches for the temporal bin packing problem with fire-ups, Annals of Operations Research, ISSN 1572-9338, Springer US, New York, NY, Vol. 333, Iss. 1, pp. 481-499, https://doi.org/10.1007/s10479-023-05446-8 This Version is available at: https://hdl.handle.net/10419/317735 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Annals of Operations Research (2024) 333:481–499 https://doi.org/10.1007/s10479-023-05446-8 ORIGINAL RESEARCH Worst-case analysis of heuristic approaches for the temporal bin packing problem with fire-ups John Martinovic1 ·Nico Strasdat1 Accepted: 6 June 2023 / Published online: 1 July 2023 © The Author(s) 2023 Abstract We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing a weighted sum of the total number of bins required and the number of switch-on processes (so-called fire-ups) caused during operation. So far, research on the TBPP-FU has mainly focused on exact approaches and their improvement by valid cuts or variable reduction techniques. Although these studies have revealed the problem considered here to be very difficult to cope with, theoretical contributions to heuristic solution methods have not yet been presented in the available literature. Hence, in this article we investigate the worst-case behavior of some approximation algorithms, ranging from classic online algorithms to a more sophisticated look-ahead heuristic specifically designed for the TBPP-FU. In addition, we theoretically study three heuristics the ideas of which are inspired by solution methods for generalized bin packing problems in the field of logistics. As a main contribution, we constructively show that the feasible solutions obtained by all these approaches can be arbitrarily bad. By doing so, we (i) identify a new open problem in cutting and packing, and (ii) establish another previously unknown difference between the classical TBPP and the extended problem with fire-ups, rendering the latter the more difficult problem even from a heuristic point of view. Keywords Cutting and packing ·Temporal bin packing ·Fire ups ·Heuristics ·Worst-case analysis Mathematics Subject Classification 90C59 ·90C10 BJohn Martinovic [email protected] Nico Strasdat [email protected] 1Institute of Numerical Mathematics, Technische Universität Dresden, Dresden, Germany 123 482 Annals of Operations Research (2024) 333:481–499 1 Introduction The temporal bin packing problem (TBPP) generalizes the classic BPP, see Delorme et al. (2016) and Scheithauer (2018), with respect to an additional time dimension. More precisely, any item i∈I:= {1,...,n}isspecifiedbyaresource demand (or item size)ci∈Z+that has to be satisfied only during the lifespan [si,ei)of that item, where si,ei∈Z+with si<eidenote the starting and ending time, respectively. A set of given items then has to be assigned to as few bins as possible while respecting the bin capacity C∈Z+at any instant of time. It is important to note that even though the relationships to two-dimensional packing problems seem obvious, the TBPP is an independent problem in operations research. This is particularly due to the fact that the bin capacity represents a renewable resource at every instant of time, and, consequently, items do not have to occupy the same units (of the bin) over their entire lifespan, see Dell’Amico et al. (2020) and Martinovic et al. (2021)fora more detailed explanation. Although the TBPP is a fairly natural extension of the extensively studied BPP, its scientific foundations have been driven mainly by previous research on the temporal knapsack problem (TKP), see Bartlett et al. (2005), Caprara et al. (2013) and Gschwind and Irnich (2017). Consequently, the TBPP was first described rather lately in the relevant literature in an application-oriented publication from the field of computer science, see de Cauwer et al. (2016). Nonetheless, addressing the exact solution of the TBPP has been successfully advanced by two sophisticated approaches, namely a branch-and-bound algorithm (using Ryan-Foster branching together with a wide variety of different bounds), see Dell’Amico et al. (2020), and a layer-based combinatorial arcflow model of manageable exponential size, see Martinovic et al. (2023). Surprisingly, searching the relevant literature for contributions on heuristic methods for the TBPP does not immediately lead to the desired results. This is not because such approaches do not exist at all, but rather because they were already discussed in early publications on the so-called dynamic bin packing problem about 40 years ago (and thus well before the introduction of the term TBPP), see Coffman et al. (1983). As a consequence of that, it seems that any follow-up article dealing with that topic, like Chan et al. (2008,2009), has stuck to this original terminology rather than harmonizing it with the parallely evolving “temporal notations”. These publications mainly focussed on rather simple heuristics the properties of which were already well studied for the classical BPP. To be more precise, special emphasis was given to the following iterative online1algorithms: –any-fit (AF), scheduling the current item to an arbitrary open bin, see Chan et al. (2008), –first-fit (FF), assigning the current item to the lowest-indexed open bin, see Chan et al. (2008,2009) and Coffman et al. (1983) –best-fit (BF) and worst-fit (WF), trying to pack an item into the open bin with the currently largest (BF) or smallest (WF) load, respectively, see Chan et al. (2008). For all these heuristics, the quality of the feasible solutions obtained has been studied thoroughly and, in many cases, tight approximation factors could be found. In this context, it is remarkable that none of these publications is cited in the most recent TBPP literature, such as Dell’Amico et al. (2020) and Martinovic et al. (2023), suggesting that the existence of these theoretical contributions is largely unknown to the cutting and packing community. For this reason, we will briefly summarize some of the results in the next section, also to better display the differences that arise when so-called fire-ups are included. 1An online algorithm has to make its decision just with the information available when placing the current item. In particular, there is no further knowledge of which items will arrive next. 123 Annals of Operations Research (2024) 333:481–499 483 Considering fire-ups in item-to-bin assignments is a relatively new aspect of modelling and optimization introduced as the temporal bin packing problem with fire-ups (TBPP-FU) in an application from the field of cloud computing, see Aydin et al. (2020). The basic idea is that an unused server (or bin) can be temporarily put into some idle mode to save energy, see Fettweis et al. (2019), but it has to be re-activated later if necessary.2Any such transition from an empty state into active operation is counted as one fire-up and it is rather energy-intense, meaning that, as a second objective, the number of fire-ups should be kept small to operate sustainably. Roughly spoken, a low number of fire-ups relates to continuous operation of the servers or a scenario where servers can be switched off without being required again later. Typically, a weighted sum method (scaling the number of fire-ups by some parameter γ>0) is used to address both goals together in one objective function, see Aydin et al. (2020). More abstractly, using a server induces costs for the pure provision of the server resources, but additionally also “temporal costs” depending on the operation mode of this server (specified by the interaction of all items on the server). Note that the latter is different to, for instance, the cost terms appearing in generalized bin packing applications in the field of logistics, see Baldi et al. (2019) and Crainic et al. (2021), where typically the itemdependent costs (of a schedule) are only influenced by the individual item-to-bin assignment decisions (and not the overall packing pattern). A more detailed discussion of these and other fundamental differences between the temporal problems considered here and those encountered in the previously mentioned application is part of Sect. 4. Although there is a quite strong relation between the TBPP-FU and the TBPP, research has shown that important properties are lost as a consequence of the extended problem statement. In the literature, the two main differences are given by: – An optimal solution to the TBPP-FU typically uses more bins than required in an optimal configuration without considering fire-ups, see Example 2.2 in Aydin et al. (2020). Hence, solving the TBPP does not necessarily lead to an upper bound on the number of bins required in the TBPP-FU. – In general, temporal decompositions cannot be applied to the TBPP-FU, see Theorem 3 in Martinovic and Strasdat (2022), meaning that an instance typically cannot be split into independent subinstances of smaller size. So, not only the solution sets of the two problems may be completely disjoint, but also some fundamental techniques exploiting the structural properties of an instance cannot be used to obtain these solutions in case of the TBPP-FU, in general. As a consequence of that, research has mainly dealt with improving the ILP formulations (called M1 and M2) proposed in Aydin et al. (2020) by various aspects like symmetry breaking conditions and valid cuts, see Martinovic et al. (2021), as well as clique-based reduction methods or the use of heuristic information, see Martinovic et al. (2022). For the latter, the constructive look-ahead heuristic (CLH) introduced in Aydin et al. (2020) was used, since it is the only approximation algorithm, known in the literature, specifically addressing the fire-up term in the objective function. While empirically it was shown that lots of variables and constraints can be removed based on the heuristic solution, its theoretical properties have not been dealt with at all so far. In this article, we would therefore like to focus on the approximation guarantee of heuristic approaches for the TBPP-FU. As already alluded to earlier, we will start with a short repetition of standard online algorithms known from the classic TBPP, collect their main theoretical properties (→Sect.2), and show that their worst-case performance ratio is no longer bounded, 2Note that similar ideas are also discussed in the field of thermal units, see Frangioni and Gentile (2006). 123 484 Annals of Operations Research (2024) 333:481–499 when fire-ups have to be respected (→Sect.3). As a main contribution, we prove the same result for CLH thus closing an open theoretical question for the only TBPP-FU heuristic known in the literature (→Sect.3). Moreover, we also theoretically study further types of constructive heuristics the ideas of which are based on neighboring bin packing applications from the field of logistics (→Sect.4). In total, we prove that eight different heuristics for the TBPP-FU possess an unbounded approximation guarantee. Altogether, our investigations are not only the first to cover theoretical properties of heuristic approaches for the TBPPFU, but they do also establish a third fundamental difference between the problem under consideration and the underlying TBPP, that is, the hardness of finding reasonably good approximate solutions by (common) heuristics. 2 Heuristics for the TBPP: an overview and important results Let us start with the following definition: Definition 1 A tuple E=(n,C,c,s,e),wherec,s,andeare n-dimensional vectors collecting the input-data (item size, starting time, ending time) of the items, is called an instance (of the TBPP). Without loss of generality, we assume the items to be sorted with respect to non-decreasing starting times (breaking ties in an arbitrary way) and to satisfy ci≤Cto ensure solvability. For any given algorithm ALG,wedefinethe(worst case) performance ratio σ:= σ(ALG) by σ(ALG):= sup E ALG(E) OPT(E), with ALG(E)and OPT(E)denoting the heuristic and the optimal value (of E), respectively. For a fixed instance E, the optimal value OPT(E)can either be determined by theoretical arguments or by an exact formulation. For the sake of exposition, here we just mention the textbook formulation given in Dell’Amico et al. (2020) as one example. It is based on classic assignment variables xik ∈{0,1},wherexik =1 holds if and only if bin k∈K(with K denoting some index set of the bins) carries item i∈I. In addition, there are bin-dependent variables zk∈{0,1}with zk=1 if and only if bin kis used. Then, we obtain the Assignment Model for the TBPP z= k∈K zk→min s.t.  k∈K xik =1,i∈I,(1)  i∈It cixik ≤C·zk,t∈T,k∈K,(2) xik ∈{0,1},i∈I,k∈K,(3) zk∈{0,1},k∈K.(4) The objective function minimizes the total number of servers in use. Moreover, the two sets of constraints make sure that any job is executed precisely once (see (1)) and that the capacity of the servers is respected at any instant of time t∈T:= i∈I{si,ei}(see (2)). 123 Annals of Operations Research (2024) 333:481–499 485 Additionally, the latter prevent jobs from being assigned to unused servers at all. Note that Itis an index set collecting the items i∈Iwith t∈[si,ei), i.e., the items active at time t∈T. Some improvements of this textbook model as well as further (more sophisticated) exact approaches can be found in Dell’Amico et al. (2020) and Martinovic et al. (2023). Although there is a certain body of work dealing with heuristics for the TBPP, as mentioned earlier, the fact that they were all published with respect to a completely different terminology might be the reason why there is no link between the most recent literature dealing with exact approaches (partly requiring and benefiting from heuristic information) and the former theoretical results related to what was called dynamic bin packing. To close this gap, let us briefly repeat the most important results obtained at that time. The first heuristic proposed in the literature is of first-fit type, see Coffman et al. (1983), and an interval for the performance ratio is given by the following result. Theorem 1 (see Theorem 2 and Theorem 6 in Coffman et al. (1983)) We have 2.389 ≈43 18 ≤σ(FF)≤5 2+3 2log √13 −1 2≈2.897. The lower bound also holds for any arbitrary online algorithm. The proofs related to these bounds are very technical and shall therefore be omitted. Among others, establishing the lower bound requires an instance construction containing eleven steps (partly with several subcases). Note that, even if the true value of σ(FF)was not identified in that early publication, the results obtained are nevertheless quite remarkable: – First of all, we see that adding a temporal dimension to the classical BPP makes it much harder to find a feasible solution of good quality with reasonable numerical efforts. By that, we particularly mean that the known approximation factor of FF for the BPP [that is, 1.7, see Dósa and Sgall (2013)] is possibly raised by up to more than one unit. – Secondly, already this very first article dealing with heuristics for the TBPP was able to establish a lower bound for a wide variety of approximation algorithms. In Chan et al. (2008), the authors present new results for all the simple heuristics mentioned in the above list, see Sect.1, but some of their considerations are limited to unit fraction item sizes (meaning that the bin capacity Cis an integer multiple of any ci,i∈I). In the cutting and packing literature, such a scenario is sometimes also referred to as the divisible case,see Coffman et al. (1987), Marcotte (1983) and Martinovic (2022). Remark 1 Note that an upper bound for σ(AF)also holds for FF, BF, and WF, since the latter are, in a sense, “special cases” that can occur in the random bin selection process of AF. In particular, the following results are obtained: Theorem 2 (see Theorem 7 and Theorem 8 in Chan et al. (2008)) We have σ(WF)≥3and σ(BF)≥3. Interestingly, in Theorem 6 in Chan et al. (2008), the tightness of these approximation factors (of BF and WF) for instances with unit fraction item sizes was shown. In fact, the corresponding proof can be easily extended to arbitrary instances, so that even the following result holds: Theorem 3 We have σ(AF)≤3. 123 486 Annals of Operations Research (2024) 333:481–499 Fig. 1 An illustration of E(α, β) for α=10 and β=0 In the light of Remark 1, we now know that BF and WF do possess a worst-case performance ratio of 3. This is a remarkable qualitative difference to the situation for the classic BPP due to two reasons: – Firstly, we see that there is no difference between BF and WF in terms of the approximation guarantee. For the BPP, BF is known to perform better than WF, see Dósa and Sgall (2014), Johnson (1973). – Secondly, FF is better than BF for the TBPP, whereas from a worst-case perspective both of them were equivalent for the BPP, see Dósa and Sgall (2013), Dósa and Sgall (2014). As a last point, we mention that for FF the following two improvements of the lower bounds from Coffman et al. (1983) can be obtained: Theorem 4 (see Theorem 1 and Theorem 5 in Chan et al. (2008)) We have σ(FF)≥2.45. Moreover, for the subclass of unit fraction item sizes the performance ratio of FF is bounded above by a constant less than 2.5. Theorem 5 (see Theorem 1 in Chan et al. (2009)) For any online algorithm, we have σ(ALG)≥5 2. Both together imply that approximating the TBPP is harder for arbitrary item sizes than for unit fractions. However, the exact performance guarantee of FF is still not known in either case. 3 Heuristics for the TBPP-FU: a worst-case analysis Let us define a family of TBPP-FU instances E(α, β) parametrized by α, β ∈Z+with α≥1. More precisely, any such instance uses the bin capacity C=2, some scaling parameter γ>0, and is given by the following items: – two items (Type ’A’) with [sA,eA)=[1,2α) and cA=1, –βitems (Type ’B’) [sB,eB)=[1,2α) and cB=2, –αitems (Type ’C’, labelled from 1 to α) with [si,ei)=[2i−1,2i)and ci=1, i=1,...,α. Note that γdoes not affect the shape of the items, so that we do not have to specify this value when illustrating an instance. Some exemplary configurations are given in Figs.1and 2. Remark 2 Counterexamples in the field of the TBPP-FU often benefit from the interaction of relatively few long jobs and many very short jobs, see also Example 2.2 in Aydin et al. (2020), where an instance with C=4 and three different item types (either short or long) with ci∈{2,3}is used to state that an optimal solution to the TBPP-FU does not have to use the minimum number of bins possible. In fact, this is an important result, because it demonstrates the first key difference between the TBPP and the TBPP-FU from a structural (and algorithmic) point of view. 123 Annals of Operations Research (2024) 333:481–499 487 Fig. 2 An illustration of E(α, β) for α=8andβ=2 With the help of these instances, we will show that any heuristic from the literature proposed for the TBPP and the TBPP-FU can be arbitrarily bad. To this end, let us first construct an optimal solution of E(α, β). Theorem 6 For any feasible choice of (α, β) and any scaling parameter γ>0we have OPT(E(α, β) =(1+γ)·(β +2). Proof Given the items available at t=1, at least β+2 bins are required in an optimal solution. Hence, it suffices to find a feasible solution using precisely this number of bins in continuous operation (i.e., with one fire-up per bin). To achieve this, we consider the following assignment: –Anyoftheβitems of type ’B’ requires a separate bin, leaving no space for any other item to be added. – We pack one item of type ’A’ together with all the αitems of type ’C’. – The last bin just contains one item of type ’A’. Altogether, this solution uses β+2 bins each having exactly one fire-up (at the very beginning). Hence, the optimal value is given by (1+γ)·(β +2)and the claim is proved.  As a direct consequence of that, we can state: Theorem 7 For any γ>0, the worst-case performance ratio of AF, FF, BF, and WF (applied to the TBPP-FU) is unbounded. Proof Let us consider the instance E(α, 0)with some arbitrary γ>0, see also Fig. 1. Then, in any of the heuristics mentioned before the items are placed in the same way since there is precisely one possibility in every iteration. Hence, either way, we end up with one bin grouping the two items of type ’A’ (that is, one fire-up) and one bin collecting all items of type ’C’ (that is, αfire-ups). Altogether, we have ALG(E(α, 0)) =2+γ·(1+α), meaning that the ratio ALG(E)/OPT(E)is unbounded when αtends to infinity.  Remark 3 Of course, the heuristics studied so far are not tailored to tackle the TBPP-FU since only a part of the objective function (namely, the number of bins) is addressed in the iterative decisions. However, in general, this fact alone is not sufficient to explain the resulting change towards an unbounded approximation guarantee. For example, the same FF algorithm applied to the problem of busy time minimization with bounded parallelism (i.e., an objective function that no longer includes the number of bins as a cost term at all) would still yield a 4-approximation, see Flammini et al. (2010). 123 488 Annals of Operations Research (2024) 333:481–499 Remarkably, the previous theorem also holds for any other iterative online algorithm, since the reason for the bad performance is that the algorithm is not allowed to (I) open an additional bin when the existing bins are able to accommodate the currently considered item, (II) consider several items (and their expected interaction) at once and place them together on the most suitable server. In fact, these restrictions cannot be relaxed either, because an online algorithm does not know which items will follow in future (if any), and so – by way of example – there is no basis for deciding whether to add an extra bin or not. Although these critical features have not been identified or reported before, the constructive look-ahead heuristic (CLH) proposed in Aydin et al. (2020), see Algorithm 1, was intuitively equipped with some tailored modifications addressing issue (I). First of all, it is not an online algorithm since it uses a certain amount of future items (specified by q)whenmakingthe current decision. Moreover, and even more importantly, it allows to open an additional bin at every stage to possibly get around the critical situation observed in the previous example. Indeed, CLH would solve the instance displayed in Fig.1and any other instance E(α, 0) correctly. Note that heuristics focussing on issue (II) from the above list will be discussed later in Sect.4. Algorithm 1 CLH with look-ahead parameter q Input: Item list ordered by non-decreasing starting times si, parameter q∈N. 1: Initialize the “empty” assignment A(0):= ∅. 2: for i∈Ido 3: Assign item ito any open bin of A(i−1)that can accommodate it and (as another alternative) also to a new empty bin. By that we obtain the assignments A1:= A1(i),...,Ap:= Ap(i)for some p:= p(i)≤n. 4: Add the next qitems (or less, if i+q>n) to each of these allocations in a best-fit fashion and obtain the (updated) assignments  A1,..., Ap. 5: Choose one assignment from  A1,..., Apwith the lowest objective value (breaking ties with the lower index s∈{1,...,p}of the assignment), say  Aopt, and define Aopt as A(i), that is, the starting point of the next iteration. 6: end for Output: heuristic solution with objective value CLH q(E). Remark 4 Note that a deeper look into the future (i.e., a larger value of q) does not necessarily lead to an equivalent or even better result. More formally, the property CLH q(E)≥ CLH q+1(E)does not hold, in general. By way of example, let us consider the instance E defined by n=5, C=2, γ=1, and the following item characteristics c=(1,1,1,1,2), s=(1,1,2,4,5), e=(6,6,3,5,6). For q=1, CLH finds an optimal solution using two bins and three fire-ups by forming the bins B1={1,2}and B2={3,4,5}. Contrary to that, q=2 leads to a worse objective value by requiring the three bins  B1={1,3,4}, B2={2},and B3={5}, together with three fire-ups. Hence, there is no strict relation between qand the objective value obtained by Algorithm 1. By inserting sufficiently many items of type ’B’, as in Fig.2, the possibilities to successfully look into the future can be limited, especially for the crucial decision how to deal with 123 Annals of Operations Research (2024) 333:481–499 495 Fig. 3 An illustration of E(p)for p=5 In particular, this result is independent of the choice of γ>0. Proof Let us consider a family of instances E(p)characterized by p≥2 and defined in the following way: – We use a bin capacity of C=2. –Wehave2pitems (called type ’X’), consisting of pgroups of two items each. The items of group i∈{1,...,p}satisfy ci=2and[si,ei)=[2i−1,2i). –Wehave2(p−1)items (called type ’Y’), consisting of p−1 groups of two items each. The items of group i∈{1,...,p−1}satisfy ci=1and[si,ei)=[2i,2i+1). For clarity, an example with p=5 is illustrated in Fig.3. We now study the optimal and heuristic solution belonging to E(p): – Obviously, an optimal solution is given by using two servers with one X-item of each of the pgroups. Moreover, on any of the two servers the temporal gap between two successive X-items can be bridged by precisely one Y-item. This leads to two bin that are executed without interruption, i.e., we have OPT(E(p)) =2·(1+γ). – When using Algorithm 3, the first bin would be filled completely (identical to the lower half of Fig.3), because this assignment just produces one fire-up, but uses the largest possible area or the largest number of items, respectively. In any possible schedule, the remaining items will produce exactly pfire-ups and use at least one additional bin (possibly more bins, depending on the precise choice of K1and K2), so we end up with BB(E(p)) ≥2+γ·(1+p). Altogether this leads to: BB(E(p)) OPT(E(p)) ≥2+γ·(1+p) 2·(1+γ) which tends to infinity for p→∞.Thisprovestheclaim.  The last heuristic to be discussed here is based on the idea of a temporal decomposition of the considered instance. This concept of focussing on the items available at different points in time is inspired by the investigations in Sect. 6 in Crainic et al. (2021), and one possible implementation (in the sense of the TBPP-FU) can be found in Algorithm 4. Recall that TS denotes the set of starting points of a given instance. To better understand the key ideas of the heuristic, we first repeat an important definition from the TBPP literature. Definition 2 (Dell’Amico et al. (2020)) Let Ebe an instance of the TBPP and let t1<t2∈TS follow each other directly in the chronologically ordered set Tof all time instants. If t2is not also an ending time, then t1is dominated by t2. The set of all non-dominated starting times is referred to as Tnd S⊆TS. 123 496 Annals of Operations Research (2024) 333:481–499 Note that there is a bijection between the non-dominated starting times and the maximum cliques of the interval graph belonging to E, see Martinovic et al. (2023), implying a canonical order of the maximum cliques. Moreover, the latter can be efficiently determined in polynomial time, see Biedl (2005) or Algorithm 1 in Furini (2011), for an implementation with O(n2)time. The details of the clique-based heuristic called Best Clique (BC) can be found in Algorithm 4: Algorithm 4 Best Clique (BC) for the TBPP-FU Input: Instance Eof the TBPP-FU with an item list ordered by non-decreasing starting times si. 1: Compute the maximum cliques C={C1,C2,...,Cm}of E. 2: for all Cl∈Cdo 3: Solve the bin packing problem related to Cl.Letz ldenote the number of bins required to pack the items of Cl. 4: end for 5: Let lindicate the index of the clique having the largest value z l(breaking ties by the lowest running index l). Assign the items of Claccording to the solution obtained by solving the bin packing problem. 6: Starting at Cl, iteratively move to the left-neighbor clique (until there is no left neighbor anymore) and assign the unpacked items (of that respective clique) to the existing bins in a best-cost fashion (breaking ties by assigning the item in a best-fit fashion among the cost-minimal candidates, and, if a further criterion is required, choosing the lowest-indexed bin). If an item does not fit into the existing bins, a new bin has to be opened to accommodate this item. 7: Starting at Cl, iteratively move to right-neighbor clique (until there is no right neighbor anymore) and assign the unpacked items (of that respective clique) to the existing bins in a best-cost fashion (breaking ties by assigning the item in a best-fit fashion among the cost-minimal candidates and, if a further criterion is required, choosing the lowest-indexed bin). If an item does not fit into the existing bins, a new bin has to be opened to accommodate this item. Output: heuristic solution with objective value BC(E). The idea of this algorithm is to first find the most restrictive point in time (i.e., the maximum clique is likely to be responsible for opening the most bins) and to assign the items of that clique in a locally optimal way. Then, in both directions, the new items of the neighboring cliques are iteratively added to that fundament in a best-cost fashion trying to keep the number of required bins and the number of fire-ups low. Again, the local(!) costs of adding an item to some existing schedule can be 0 (item does neither open a new bin nor leads to a new fire-up on the server), γ(item leads to an additional fire-up on the server), or 1 +γ(item is placed on an empty server). As a consequence of that, a two-staged tie-break system was added to Algorithm 4. Remark 6 Given its focus on maximum cliques, the BC heuristic strongly exploits the temporal structure of a given instance (e.g., by focussing on the non-dominated starting times). Moreover, adding an item to a bin is done in a best-cost fashion, so that both aspects of the objective function (number of bins and number of fire-ups) are always present in the decision-making process. The following result shows that also the clique-based heuristic can be arbitrarily bad. Theorem 12 We have σ(BC)=sup E BC(E) OPT(E)=∞. In particular, this result is independent of the choice of γ>0. 123 Annals of Operations Research (2024) 333:481–499 497 Proof Let us consider an instance  E(α, 0)with C=2 that is similar to E(α, 0)with α≥2, but where the first item of type ’C’ (labelled i=1inFig.1) is replaced by two items (referred to as type ’D’) with ci=2and[si,ei)=[1,2). –Sinceα≥2 holds, an optimal solution requires four bins. Two of these bins contain precisely one item of type ’D’. The third bin is filled with one item of type ’A’, and the fourth bin contains the remaining items (one item of type ’A’ and all items of type ’C’). In total, this leads to four bins with one fire-up each, i.e., we have OPT( E(α, 0)) =4·(1+γ). – Obviously, any odd trepresents a non-dominated starting time (maximum clique). The clique for t=1 contains two items of types A and D each, the cliques for t= 1 contain one item of type ’C’ together with two items of type ’A’. Hence, C1leads to the largest objective value for the classic bin packing problem (z 1=3), and our starting configuration consists of one bin (k=1) with both items of type ’A’ (so this bin cannot accept any further item), and two bins (k=2,3) with one item of type ’D’ each. Since C1was the left-most clique, we can just proceed in right direction. In every iteration (that is, in any clique considered), precisely one item of type ’C’ is unassigned, and so it has to enter the given bins in a best-cost fashion. According to the tie-break rules, all these items are added to bin k=2. In the end, we have two bins with exactly one fire-up (k=1andk=3) and one bin with a total of αfire-ups (k=2). This leads to BC( E(α, 0)) =3+γ·(2+α). Hence, for α→∞the worst-case performance ratio becomes arbitrarily large, and the claim is proved.  Altogether, we have shown that neither the ideas obtained from constructive heuristics in the field of logistics lead to approaches with bounded approximation guarantee. This observation is remarkable, since we have now dealt with a wide variety of online, semionline, and offline heuristics – and none of them was theoretically able to handle fire-ups efficiently. 5 Conclusions In this article, we considered heuristic approaches from the literature for two neighboring optimization problems, the TBPP and the TBPP-FU. For the former, we briefly repeated some important results obtained from publications on dynamic bin packing, because according to our impression these contributions have not yet made their way into the most recent scientific discussion on the TBPP. For the TBPP-FU, in a first step we were able to show that the worst-case performance ratio of the former TBPP heuristics is unbounded when fire-ups have to be considered. Having identified the critical features of these algorithms, we observed that they are not present in the only heuristic specifically designed for the TBPPFU in the literature, that is, CLH from Aydin et al. (2020). However, despite the promising modifications contained in CLH, the approximation guarantee of this heuristic is unbounded, too. As an outlook, similar results were shown for further constructive heuristics the ideas of which originating from a logistics application, see Baldi et al. (2019) and Crainic et al. (2021). Remarkably, all results are independent of the scaling parameter γand the look-ahead 123 498 Annals of Operations Research (2024) 333:481–499 parameter q(resp. N). Altogether, this work represents the first systematic framework to study theoretical properties of heuristic approaches for the TBPP-FU, showing some previously unknown differences between the two temporal problems under consideration. On the other hand, our contributions inevitably lead to a new open challenge for future research in cutting and packing, that is: How to construct a (preferably simple) heuristic for the TBPP-FU, the performance ratio of which can be shown to be bounded? Funding Open Access funding enabled and organized by Projekt DEAL. Declarations Conflict of interest The authors declare that they do not have any conflicts of interest. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Aydin, N., Muter, I., & Ilker Birbil, S. (2020). Multi-objective temporal bin packing problem: An application in cloud computing. Computers & Operations Research, 121, 104959. Baldi, M. M., Manerba, D., Perboli, G., & Tadei, R. (2019). Generalized bin packing problem for parcel delivery in last-mile logistics. European Journal of Operational Research, 274(3), 990–999. Bartlett, M., Frisch, A. M., Hamadi, Y., Miguel, I., Tarim, S., & Unsworth, C. (2005). The temporal knapsack problem and its solution. Lecture Notes in Computer Science, 3524, 34–48. Biedl, T. (2005). Graph-theoretic algorithms. Lecture notes: University of Waterloo. Caprara, A., Furini, F., & Malaguti, E. (2013). Uncommon Dantzig-Wolfe reformulation for the temporal knapsack problem. INFORMS Journal on Computing, 25(3), 560–571. Chan, J.W.-T., Lam, T.-W., & Wong, P. W. H. (2008). Dynamic bin packing of unit fraction items. Theoretical Computer Science, 409, 521–529. Chan, J.W.-T., Wong, P. W. H., & Yung, F. C. C. (2009). On dynamic bin packing: an improved lower bound and resource augmentation analysis. Algorithmica, 53, 172–206. Coffman, E. G., Jr., Garey, M. R., & Johnson, D. S. (1983). Dynamic bin packing. SIAM Journal on Computing, 12(2), 227–258. Coffman, E. G., Jr., Garey, M. R., & Johnson, D. S. (1987). Bin packing with divisible item sizes. Journal of Complexity, 3(4), 406–428. Crainic, T. G., Fomeni, F. D., & Rei, W. (2021). Multi-period bin packing model and effective constructive heuristics for corridor-based logistics capacity planning. Computers & Operations Research, 132, 105308. de Cauwer, M., Mehta, D., & O’Sullivan, B. (2016). The temporal bin packing problem: An application to workload management in data centres. Proceedings of the 28th IEEE International Conference on Tools with Artificial Intelligence, pp. 157–164 Dell’Amico, M., Furini, F., & Iori, M. (2020). A branch-and-price algorithm for the temporal bin packing problem. Computers & Operations Research, 114, 104825. Delorme, M., Iori, M., & Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255, 1–20. Dósa, G.,& Sgall, J. (2013). First Fit bin packing: A tight analysis. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), pp. 538–549 Dósa, G., & Sgall, J. (2014). Optimal analysis of best fit bin packing. Lecture Notes in Computer Science, 8572, 429–441. 123 Annals of Operations Research (2024) 333:481–499 499 Fettweis, G., Dörpinghaus, M., Castrillon, J., Kumar, A., Baier, C., Bock, K., Ellinger, F., Fery, A., Fitzek, F., Härtig, H., Jamshidi, K., Kissinger, T., Lehner, W., Mertig, M., Nagel, W., Nguyen, G. T., Plettemeier, D., Schröter, M., & Strufe, T. (2019). Architecture and advanced electronics pathways towards highly adaptive energy-efficient computing. Proceedings of the IEEE, 107(1), 204–231. Flammini, M., Monaco, G., Moscardelli, L., Shachnai, H., Shalom, M., Tamir, T., & Zaks, S. (2010). Minimizing total busy time in parallel scheduling with application to optical networks. Theoretical Computer Science, 411, 3553–3562. Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. Furini, F. (2011). Decomposition and reformulation of integer linear programming problems. PhD thesis, Università di Bologna. Gschwind, T., & Irnich, S. (2017). Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities. OR Spectrum, 39, 541–556. Johnson, D. S. (1973). Near-optimal bin packing algorithms. PhD dissertation, Massachusetts Institute of Technology Marcotte, O. (1983). Topics in combinatorial packing and covering. Technical Report No. 568, Cornell University Martinovic, J. (2022). A note on the integrality gap of cutting and skiving stock instances. Why 4/3 is an upper bound for the divisible case? 4OR, 20, 85–104. Martinovic, J., Strasdat, N. (2022). Theoretical Insights and a New Class of Valid Inequalities for the Temporal Bin Packing Problem with Fire-Ups. Preprint MATH-NM-01-2022, Technische Universität Dresden (http://www.optimization-online.org/DB_HTML/2022/02/8791.html) Martinovic, J., Strasdat, N., & Selch, M. (2021). Compact integer linear programming formulations for the temporal bin packing problem with fire-ups. Computers & Operations Research, 132, 105288. Martinovic, J., Strasdat, N., Valério de Carvalho, J. M., & Furini, F. (2022). Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups. Optimization Letters, 16, 2333–2358. Martinovic, J., Strasdat, N., Valério de Carvalho, J. M., & Furini, F. (2023). A combinatorial flow-based formulation for temporal bin packing problems. European Journal of Operational Research, 307(2), 554–74. Scheithauer, G. (2018). Introduction to cutting and packing optimization–problems, modeling approaches, solution methods. International Series in Operations Research & Management Science 263, Springer, 1.Edition Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123