What does Packing, Refund Ladders and Depreciation for Studios conclude, in numbers, about “Time-Slot Packing: the 11/9 Bound of First Fit Decreasing, Exact Dynamic Programming and the Idle Share of Fragmented Calendars”?
Answer: Chapter 1 uses one-dimensional bin packing to show that first fit decreasing reaches a ratio of 1.2222 on an adversarial instance yet uses very few extra set-days on random order books, and that minimum-vacancy stitching raises the sold share by 0.0457 without any change in price.
Scope of the numbers: Its parameters are illustrative; all calculations are generated by its programs; the book is not individual tax, legal or investment advice. Marked boxes separate published evidence, runnable Python calculations (22 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1.2222
A. adversarial book: 30 orders, total 540 units, capacity 60 lower bound 9, OPT 9 (31+16+13 x6, 17+17+13+13 x3), FFD 11 Dosa bound 11/9*OPT+6/9 = 11.667; ratio FFD/OPT = 1.2222 B. 1500 random books of 9 orders, day = 24 half-hours NF mean studio-days 3.8660 FF mean studio-days 3.5840 FFD mean studio-days 3.4807 OPT mean studio-days 3.4453 FFD above OPT in 53 books (0.0353); worst ratio 1.5000 books breaking 11/9*OPT+6/9: 0; at OPT 2 the bound is 3.111 idle share FFD 0.1523, OPT 0.1432
Show the full program
# Chapter 1. p11: first fit decreasing against the exact optimum.
# A studio-day is a bin of 24 half-hour units (09:00 to 21:00). Orders
# whose start can float inside the day are items. Part A packs the
# classic adversarial order book (capacity 60 units of 12 minutes;
# items 31, 17, 16 and 13 units) to show FFD = 11 against OPT = 9.
# Part B draws random order books of 9 orders, packs them by next fit,
# first fit in arrival order and FFD, and finds the exact optimum by
# a subset dynamic programme. Durations are illustrative.
import math
import random
def first_fit(items, cap):
bins = []
for s in items:
for i, b in enumerate(bins):
if b + s <= cap:
bins[i] = b + s
break
else:
bins.append(s)
return len(bins)
def next_fit(items, cap):
n, room = 0, 0
for s in items:
if s > room:
n, room = n + 1, cap
room -= s
return n
def exact(items, cap):
n = len(items)
best = [None] * (1 << n)
best[0] = (1, 0)
for mask in range(1, 1 << n):
cand = None
for i in range(n):
if mask >> i & 1:
b, f = best[mask ^ (1 << i)]
s = items[i]
st = (b, f + s) if f + s <= cap else (b + 1, s)
if cand is None or st < cand:
cand = st
best[mask] = cand
return best[-1][0]
hard = [31] * 6 + [17] * 6 + [16] * 6 + [13] * 12
lb = math.ceil(math.fsum(hard) / 60)
print("A. adversarial book: 30 orders, total {} units, capacity 60".format(
int(math.fsum(hard))))
print(" lower bound {}, OPT 9 (31+16+13 x6, 17+17+13+13 x3), FFD {}"
.format(lb, first_fit(sorted(hard, reverse=True), 60)))
print(" Dosa bound 11/9*OPT+6/9 = {:.3f}; ratio FFD/OPT = {:.4f}".format(
11 / 9 * 9 + 6 / 9, 11 / 9))
rng = random.Random(20261112)
menu = [3, 4, 4, 6, 6, 8, 8, 9, 10, 12, 16]
C, N, T = 24, 9, 1500
tot = {"NF": [], "FF": [], "FFD": [], "OPT": []}
worse, vac_ffd, vac_opt, mx, viol = 0, [], [], 0.0, 0
for _ in range(T):
it = [rng.choice(menu) for _ in range(N)]
ffd = first_fit(sorted(it, reverse=True), C)
low = math.ceil(math.fsum(it) / C)
opt = ffd if ffd == low else exact(sorted(it, reverse=True), C)
tot["NF"].append(next_fit(it, C))
tot["FF"].append(first_fit(it, C))
tot["FFD"].append(ffd)
tot["OPT"].append(opt)
worse += ffd > opt
viol += ffd > 11 / 9 * opt + 6 / 9
mx = max(mx, ffd / opt)
vac_ffd.append(1 - math.fsum(it) / (ffd * C))
vac_opt.append(1 - math.fsum(it) / (opt * C))
print("B. {} random books of {} orders, day = {} half-hours".format(T, N, C))
for k in ("NF", "FF", "FFD", "OPT"):
print(" {:4s} mean studio-days {:.4f}".format(k, math.fsum(tot[k]) / T))
print(" FFD above OPT in {} books ({:.4f}); worst ratio {:.4f}".format(
worse, worse / T, mx))
print(" books breaking 11/9*OPT+6/9: {}; at OPT 2 the bound is {:.3f}"
.format(viol, 11 / 9 * 2 + 6 / 9))
print(" idle share FFD {:.4f}, OPT {:.4f}".format(
math.fsum(vac_ffd) / T, math.fsum(vac_opt) / T))Single source and citation
Fan, Y. (2026). One-Dimensional Time-Slot Packing for Multi-Format Studio Sets, Dynamic Cancellation-Option Ladders and Accelerated Depreciation of High-Wear Equipment (Version 1.0.0), Chapter 1: Time-Slot Packing: the 11/9 Bound of First Fit Decreasing, Exact Dynamic Programming and the Idle Share of Fragmented Calendars. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-173 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026173,
author = {Fan, Yafu},
title = {One-Dimensional Time-Slot Packing for Multi-Format Studio Sets, Dynamic Cancellation-Option Ladders and Accelerated Depreciation of High-Wear Equipment},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 2 · Online Arrivals: Greedy Placement, Littlewood Protection Levels and the Minimum Booking Length
- Chapter 3 · The Cancellation-Option Ladder: Pricing Each Step by the Chance of Resale, Service Escape and Seasonal Dynamic Ladders
- Chapter 4 · Overbooking as a Newsvendor Problem: the Marginal-Booking Rule, the Cost of Compensation and the Trap of Correlated No-Shows
- Chapter 5 · Accelerated Depreciation of High-Wear Equipment: Double Declining Balance, Units of Production, the Present Value of the Tax Shield and Economic Life
- Chapter 6 · Deposits and Damage Waivers: the Incentive-Compatibility Boundary under Moral Hazard and a Three-in-One Quotation Calculator
- Chapter 7 · Classical Sources: the Song Rental Office for State Houses and the Roman Contract of Hire
- Chapter 8 · Practice and Falsification: a Checklist for the Principal of a Venue, the Distilled Kit and a Pre-Registered Test