EUVIMEDEUVIMED entdecken
Crossref

Temporal Bin Packing with Half-Capacity Jobs

Christopher Muir, Luke Marshall, Alejandro Toriello

INFORMS Journal on Optimization · 2024-01 · 6 (1) · 46-62

DOI: 10.1287/ijoo.2023.0002 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Optimization, 2024-01. Verfasst von Christopher Muir und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 25 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed (i.e., assigned to a bin). A bin can accommodate two jobs simultaneously, and the objective is an assignment that minimizes the time-averaged number of open or active bins over the horizon; this problem is known to be NP hard. We demonstrate that a well-known “static” lower bound may have a significant gap even in relatively simple instances, which motivates us to introduce a novel combinatorial lower bound and an integer programming formulation, both based on an interpretation of the model as a series of connected matching problems. We theoretically compare the static bound, the new matching-based bounds, and various linear programming bounds. We perform a computational study using both synthetic and application-based instances and show that our bounds offer significant improvement over existing methods, particularly for sparse instances. Funding: This work was supported by the National Science Foundation [Grants CMMI-1552479 and NSF GRFP]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2023.0002 .

Zitieren

APA

Muir, C., Marshall, L., & Toriello, A. (2024). Temporal Bin Packing with Half-Capacity Jobs. INFORMS Journal on Optimization, 6(1), 46-62. https://doi.org/10.1287/ijoo.2023.0002

Vancouver

Muir C, Marshall L, Toriello A. Temporal Bin Packing with Half-Capacity Jobs. INFORMS Journal on Optimization. 2024;6(1):46-62. doi:10.1287/ijoo.2023.0002

BibTeX
@article{Muir2024,
  author = {Muir, Christopher and Marshall, Luke and Toriello, Alejandro},
  title = {Temporal Bin Packing with Half-Capacity Jobs},
  journal = {INFORMS Journal on Optimization},
  year = {2024},
  volume = {6},
  number = {1},
  pages = {46--62},
  doi = {10.1287/ijoo.2023.0002}
}
Kostenlos starten →