Scribd
Upload
821 views14 pages

D1, L3 Bin Packing Algorithm

The document discusses bin packing problems and algorithms for solving them. It explains the bin packing problem, provides an example of packing boxes into bins, and describes the first-fit and first-fit decreasing algorithms. It then applies these concepts to packing vehicles onto a ferry and cutting pipes to minimize waste.

Uploaded by

mokhtarppg
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
821 views14 pages

D1, L3 Bin Packing Algorithm

The document discusses bin packing problems and algorithms for solving them. It explains the bin packing problem, provides an example of packing boxes into bins, and describes the first-fit and first-fit decreasing algorithms. It then applies these concepts to packing vehicles onto a ferry and cutting pipes to minimize waste.

Uploaded by

mokhtarppg
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 14

Decision Maths

Heuristic Algorithms

The Bin-packing problem


The Bin-packing problem deals with packing boxes of

the same width and depth but different heights into bins.

B
C

Clearly you can see that the depth and width of the bins

remains the same so we can represent the problem in


2-dimensions.

The Bin-packing problem


Its best to look at an example to understand

how the Bin-packing problem works.


Here are 10 boxes, A to J with heights
(in cm) as follows.
Box

Height

How would you pack the boxes into bins that

are 15cm high.

The Bin-packing problem


First-fit algorithm
Box

Height

15

C(4)

G(3) H(8)

I(6)

B(7)
D(9)
A(3)

E(7)

F(9)

J(4)

Bin 1 Bin 2 Bin 3 Bin 4 Bin 5

The idea is that you place the first box in the


first available space, working from the left every
time.
Here box A goes in to bin 1.
Now box B and C will also fit in to bin 1.
Box D does not fit in bin 1 so it goes in the next
space which is bin 2.
Box E will not go in bin 1 or 2 so it is placed in
bin 3.
Similar with F, it skips over Bins 1, 2 and 3 to go
in bin 4.
G cannot go in bin 1 but it does slot into bin 2.
H will skip 1 and 2 and fill up bin 3.
I skips 1, 2 and 3 to fill up 4.
J must be placed in a new bin.

The Bin-packing problem


First-fit decreasing algorithm.
Box

D
A

F
B

H
C

B
D

FI

C
G

J
H

AI

G
J

Height

9
3

9
7

8
4

7
9

6
9

4
3

4
8

3
6

3
4

15

This is exactly the same method as

I(6)

C(4) B(7)

A(3)
J(4)

D(9) F(9) H(8)


E(7)

G(3)
Bin 1 Bin 2 Bin 3 Bin 4 Bin 5

the first-fit algorithm with one


exception.
The difference this time is that the
boxes are placed in descending order
of size before the algorithm is applied.
You should use one of the sorting
algorithms from last lesson to do this.
Now we can apply the algorithm
This algorithm is not guaranteed to
give you the best (or optimal) solution.
However it is more likely to do so than
just the First-fit algorithm.

The Bin-packing problem


Full bin combinations.

Box

Height

This is not an algorithmic process but

15

I(6)

G(3)
A(3)

B(7)

J(4)
C(4)

D(9) F(9) H(8)


E(7)

Bin 1 Bin 2 Bin 3 Bin 4 Bin 5

more common sense.


You literally make sure that each bin is
used to its full potential.
If you start by placing box D in bin 1 (No
particular reason).
Now box I can also go in bin 1 and it will
fill all the space because 9 + 6 = 15.
What other combinations will create full
bins?
This is actually the optimal solution for
this particular problem.

The Ferry Loading problem


This bin-packing problem can now be

applied to lots of practical real life


situations.
You can change what the boxes and bins
represent.
We are going to look at how to load
vehicles on to a ferry.
Here the lanes on the ferry will be the bins
and the vehicles will be the boxes.

The Ferry Loading problem


A small car-ferry has three lanes, each 20m long.
The following vehicles are waiting to be loaded.
Oil tanker
Truck
Coach
Car

13m
7m

Van

3m

Truck
12m
4m

6m
Car
Lorry

4m
11m

Use the first-fit decreasing algorithm to load all these vehicles

on to the trip.
Can all the vehicles be taken on the trip?
Box

Height

13

12

11

The Ferry Loading problem


First we need to sort the numbers.
Insertion sort algorithm

Box

Height

13

12

11

13
3
7
6
12
4
4
11

13

13
3

13
7
3

13
7
6
3

13
12
7
6
3

13
12
7
6
4
3

13
12
7
6
4
4
3

13
12
11
7
6
4
4
3

Box

Height

13

12

11

The Ferry Loading problem


Solution
Box

Height

13

12

11

First-fit decreasing
C(7)

G(4)

Full Bin combinations


C(7)

D(6)

D(6) F(4)

F(4)

A(13) E(12)

B(3) G(4)

A(13)

H(11)

H(11) E(12)

B(3)
Lane 1 Lane 2 lane 3

Lane 1 Lane 2 lane 3

The Disc storage problem


A software company has a new program that they

want to sell on CD`s.


Broken down the program looks like this.
Program

G H

Size (mb)

600 200 450 250 300 250 150 200 100 150 50

L
100

Each of the CD`s they will use can hold 700mb.


How many CD`s will the company need if they plan on

producing 50 000 copies of the program.


Program

C E

D F

H G J

Size (mb)

600 450 300 250 250 200 200 150 150 100 100 50

The Disc storage problem


Solution
Program

Size (mb)

600 450 300 250 250 200 200 150 150 100 100 50

G
D
I
(250)
J
F
(250) H
A
(600) C
(200)
E
(450)
B
(300)
(200)
Disc 1 Disc 2 Disc 3 Disc 4

G J

This can be solved using full bin

combinations or by the first-fit


decreasing algorithm.
Here the solution is done using the
first fit decreasing algorithm.
The program will fit exactly on to 4
CD`s.
The company will need
4 x 50 000 = 200 000 CD`s.

The Plumbing Problem


A plumber is using lengths of pipes 12 feet long and

wishes to cut these lengths.


Length
(ft)

Number

What is the best way of achieving this so that he

wastes as little pipe as possible.

The Plumbing Problem


Length
(ft)

Number

D(4) E(4)

First change the table to assign each length of pipe

a name.
Now you can apply the first-fit decreasing algorithm.
You can now easily see the full bin combinations.

Pipe

A B C D E F G H I

K L

Length

K(2) J(3)
F(4) I(3)

A(7) B(7) C(6)

H(3)
G(3) L(2)

Pole 1 Pole 2 pole 3 Pole 4 Pole 5

7 6

K(2) L(2) J(3)


F(4)
I(3) H(3)
G(3)
E(4)
A(7) B(7) C(6)

D(4)

Pole 1 Pole 2 pole 3 Pole 4

You might also like