Randomized greedy algorithm for allocating presized beams

beams.py

import random, collections

sizes = [6, 6.6, 7.2, 7.8, 8.4, 9.6, 12]

beams = [
    (6, 3.700),
    (37, 6.700),
    (4, 5.600),
    (40, 7.800),
    (2, 1.100),
    (9, 3.300),
    (2, 2.900),
    (14, 4.900),
    (1, 4.900),
    (7, 2.000),
    (4, 5.900),
    (4, 4.300),
    (1, 1.500),
    (2, 2.300),
    (4, 3.100),
    (6, 4.500),
    (6, 1.000),
    (3, 1.600),
    (4, 1.100),
    (3, 0.900),
    (3, 1.800),
    (2, 1.900),
]

sizes = [float(x) for x in sizes]
beams = [float(x) for count, size in beams for x in [size] * count]


def greedy_asc(size, beams):
    return greedy_beam(size, sorted(beams))


def greedy_des(size, beams):
    return greedy_beam(size, sorted(beams, reverse=True))


def greedy_shuffle(size, beams):
    random.shuffle(beams)
    return greedy_beam(size, beams)


def greedy_beam(size, beams):
    used = []
    for b in beams:
        if b > size:
            continue
        size -= b
        used.append(b)
    if not used:
        return 100, used
    return (size, used)


def generate_order(sizes, beams):
    beams = beams[:]
    total_wastage = 0
    order = []
    while beams:
        best = (100, 100, [])
        for s in sizes:
            for f in [greedy_asc, greedy_des, greedy_shuffle]:
                waste, used = f(s, beams)
                if waste < best[0]:
                    best = (waste, s, sorted(used))
        total_wastage += best[0]
        order.append(best)
        for b in best[2]:
            beams.remove(b)
    return (total_wastage, order)


best = (100, [])
for i in range(1000):
    if i % 50 == 0:
        print(i, "...")
    cand = generate_order(sizes, beams)
    if cand[0] < best[0]:
        best = cand
        print("candidate order %d with wastage %.1f" % (i, cand[0]))
print()

counts = collections.defaultdict(int)
summary = collections.defaultdict(int)
orders = sorted((size, waste, order) for waste, size, order in best[1])
for size, waste, order in orders:
    counts[size] += 1
    summary[
        ("beam size %.1f for beams %s with wastage %.1f" % (size, order, waste))
    ] += 1

max_order = max(len(order) for _, _, order in orders)
row = ["Beam", "", ""] + ["Cut " + chr(i + ord("A")) for i in range(max_order)]
row_len = len(row)
print(",".join(row))
for i, (size, waste, order) in enumerate(reversed(orders)):
    row = [str(i + 1), "", "%.3f m - beam cut" % size] + ["%.3f m" % o for o in order]
    while len(row) < row_len:
        row.append("")
    print(",".join(row))
print()

print("order description:")
for s, count in sorted(summary.items()):
    print(count, "x", s)
print()

print("order summary:")
for s, count in sorted(counts.items()):
    print(count, "x", s)
print()

print("total wastage %.1f" % best[0])

order.csv

output.txt

order description:
1 x beam size 12.0 for beams [1.0, 4.3, 6.7] with wastage 0.0
1 x beam size 12.0 for beams [1.8, 1.9, 2.0, 3.1, 3.1] with wastage 0.1
2 x beam size 12.0 for beams [2.0, 3.3, 6.7] with wastage 0.0
1 x beam size 12.0 for beams [3.7, 3.7, 4.5] with wastage 0.1
8 x beam size 12.0 for beams [4.9, 6.7] with wastage 0.4
1 x beam size 6.0 for beams [0.9, 1.8, 3.3] with wastage 0.0
4 x beam size 6.0 for beams [1.1, 4.9] with wastage 0.0
1 x beam size 6.0 for beams [1.5, 1.6, 2.9] with wastage 0.0
1 x beam size 6.0 for beams [2.9, 3.1] with wastage 0.0
2 x beam size 6.0 for beams [5.6] with wastage 0.4
4 x beam size 6.0 for beams [5.9] with wastage 0.1
2 x beam size 6.6 for beams [1.0, 5.6] with wastage 0.0
1 x beam size 6.6 for beams [1.1, 1.1, 4.3] with wastage 0.1
1 x beam size 6.6 for beams [2.3, 4.3] with wastage 0.0
2 x beam size 6.6 for beams [3.3, 3.3] with wastage 0.0
1 x beam size 7.2 for beams [2.3, 4.9] with wastage 0.0
24 x beam size 7.2 for beams [6.7] with wastage 0.5
1 x beam size 7.8 for beams [0.9, 0.9, 1.9, 2.0, 2.0] with wastage 0.1
1 x beam size 7.8 for beams [2.0, 2.0, 3.7] with wastage 0.1
1 x beam size 7.8 for beams [3.3, 4.5] with wastage 0.0
1 x beam size 7.8 for beams [3.7, 3.7] with wastage 0.4
40 x beam size 7.8 for beams [7.8] with wastage 0.0
1 x beam size 8.4 for beams [1.6, 3.1, 3.7] with wastage 0.0
1 x beam size 8.4 for beams [1.6, 6.7] with wastage 0.1
1 x beam size 9.6 for beams [1.0, 1.0, 3.3, 4.3] with wastage 0.0
1 x beam size 9.6 for beams [1.0, 1.8, 6.7] with wastage 0.1
1 x beam size 9.6 for beams [4.5, 4.5] with wastage 0.6
2 x beam size 9.6 for beams [4.5, 4.9] with wastage 0.2

order summary:
13 x 6.0
6 x 6.6
25 x 7.2
44 x 7.8
2 x 8.4
5 x 9.6
13 x 12.0

total wastage 18.5