Temporal Bin Packing with Half-Capacity Jobs

References

• Alicherry M, Bhatia R (2003) Line system design and a generalized coloring problem. Eur. Sympos. Algorithms (Springer, New York), 19–30.Google Scholar
• Aydın N, Muter İ, Birbil Şİ (2020) Multi-objective temporal bin packing problem: An application in cloud computing. Comput. Oper. Res. 121:104959.Google Scholar
• Brandao F, Pedroso JP (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Comput. Oper. Res. 69:56–67.Google Scholar
• Buchbinder N, Fairstein Y, Mellou K, Menache I, Naor J(S) (2020) Online virtual machine allocation with predictions. Preprint, submitted November 12, https://arxiv.org/abs/2011.06250.Google Scholar
• Chang J, Khuller S, Mukherjee K (2017) LP rounding and combinatorial algorithms for minimizing active and busy time. J. Scheduling 20(6):657–680.Google Scholar
• Coffman EG, Csirik J, Galambos G, Martello S, Vigo D (2013) Bin packing approximation algorithms: Survey and classification. Du D-Z, Pardalos PM, eds. Handbook of Combinatorial Optimization (Springer, New York), 455–531.Google Scholar
• De Cauwer M, Mehta D, O’Sullivan B (2016) The temporal bin packing problem: An application to workload management in data centres. 2016 IEEE 28th Internat. Conf. Tools Artificial Intelligence (ICTAI) (IEEE, Piscataway, NJ), 157–164.Google Scholar
• Dell’Amico M, Furini F, Iori M (2020) A branch-and-price algorithm for the temporal bin packing problem. Comput. Oper. Res. 114:104825.Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Google Scholar
• Dezső B, Jüttner A, Kovács P (2011) LEMON—An open source C++ graph template library. Electronic Notes Theoret. Comput. Sci. 264(5):23–45.Google Scholar
• Dósa G (2007) The tight bound of first fit decreasing bin-packing algorithm is ffd (i) ≤ 11/9opt (i)+ 6/9. Internat. Sympos. Combinatorics Algorithms Probabilistic Experiment. Methodologies (Springer, New York), 1–11.Google Scholar
• Dósa G, Sgall J (2013) First fit bin packing: A tight analysis. Proc. 30th Internat. Sympos. Theoret. Aspects Comput. Sci. (STACS 2013) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany).Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices. J. Res. National Bureau Standards B 69(125–130):55–56.Google Scholar
• Fekete SP, Schepers J (2001) New classes of fast lower bounds for bin packing problems. Math. Programming 91(1):11–31.Google Scholar
• 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. Theoret. Comput. Sci. 411(40–42):3553–3562.Google Scholar
• Furini F, Shen X (2018) Matheuristics for the temporal bin packing problem. Amodeo L, Talbi E-G, Yalaoui F, eds. Recent Developments in Metaheuristics (Springer, New York), 333–345.Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability (Freeman, San Francisco).Google Scholar
• Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Grand View Research (2022) Cloud computing market size report, 2022–2030. Grand View Research, San Francisco.Google Scholar
• Hadary O, Marshall L, Menache I, Pan A, Greeff EE, Dion D, Dorminey S, et al. (2020) Protean: VM allocation service at scale. Proc. 14th USENIX Sympos. Operating Systems Design Implementation (OSDI 20) (ACM, New York), 845–861.Google Scholar
• Hagberg A, Swart P, Chult DS (2008) Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Laboratory, Los Alamos, NM.Google Scholar
• Heßler K, Gschwind T, Irnich S (2018) Stabilized branch-and-price algorithms for vector packing problems. Eur. J. Oper. Res. 271(2):401–419.Google Scholar
• Hoberg R, Rothvoss T (2017) A logarithmic additive integrality gap for bin packing. Proc. Twenty-Eighth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2616–2625.Google Scholar
• Johnson DS (1973) Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Kantorovich LV (1960) Mathematical methods of organizing and planning production. Management Sci. 6(4):366–422.Link, Google Scholar
• Karmarkar N, Karp RM (1982) An efficient approximation scheme for the one-dimensional bin-packing problem. 23rd Annual Sympos. Foundations Comput. Sci. (SFCS 1982) (IEEE, Piscataway, NJ), 312–320.Google Scholar
• Khandekar R, Schieber B, Shachnai H, Tamir T (2010) Minimizing busy time in multiple machine real-time scheduling. IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (FSTTCS 2010) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany).Google Scholar
• Kou LT, Markowsky G (1977) Multidimensional bin packing algorithms. IBM J. Res. Development 21(5):443–448.Google Scholar
• Kumar V, Rudra A (2005) Approximation algorithms for wavelength assignment. Proc. Internat. Conf. Foundations Software Tech. Theoret. Comput. Sci. (Springer, New York), 152–163.Google Scholar
• Lee CC, Lee D-T (1985) A simple on-line bin-packing algorithm. J. ACM 32(3):562–572.Google Scholar
• Martello S, Toth P (1990) Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. 28(1):59–70.Google Scholar
• Martinovic J, Strasdat N, Selch M (2021) Compact integer linear programming formulations for the temporal bin packing problem with fire-ups. Comput. Oper. Res. 132:105288.Google Scholar
• Maruyama K, Chang SK, Tang DT (1977) A general packing algorithm for multidimensional resource requirements. Internat. J. Comput. Inform. Sci. 6(2):131–149.Google Scholar
• Mertzios GB, Shalom M, Voloshin A, Wong PWH, Zaks S (2015) Optimizing busy time parallel machines. Theoret. Comput. Sci. 562:524–541.Google Scholar
• Padberg MW, Rao MR (1982) Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7(1):67–80.Link, Google Scholar
• Panigrahy R, Talwar K, Uyeda L, Wieder U (2011) Heuristics for vector bin packing. Technical report, Microsoft Research, Redmond, WA.Google Scholar
• Pesce M (2021) Cloud computing’s coming energy crisis-the cloud’s electricity needs are growing unsustainably. IEEE Spectrum (July 21), https://spectrum.ieee.org/cloud-computings-coming-energy-crisis.Google Scholar
• Ren R, Tang X (2016) Clairvoyant dynamic bin packing for job scheduling with minimum server usage time. Proc. 28th ACM Sympos. Parallelism Algorithms Architectures (ACM, New York), 227–237.Google Scholar
• Rothvoss T (2013) Approximating bin packing within O(log OPT*log log OPT) bins. Proc. 54th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 20–29.Google Scholar
• Simchi-Levi D (1994) New worst-case results for the bin-packing problem. Naval Res. Logist. 41(4):579–585.Google Scholar
• Speitkamp B, Bichler M (2010) A mathematical programming approach for server consolidation problems in virtualized data centers. IEEE Trans. Services Comput. 3(4):266–278.Google Scholar
• Winkler P, Zhang L (2003) Wavelength assignment and generalized interval graph coloring. Proc. Fourteenth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 830–831.Google Scholar
• You F (2018) FanYouCN/BlossomSeparationPadbergRao. Accessed 2022, https://github.com/FanYouCN/BlossomSeparationPadbergRao.Google Scholar