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