Solved

# Optimisation Algorithm

Posted on 2009-07-16
303 Views
Obviously im here as I need some help.

I need to come up with a algorithm to optimise 1d cutting. I need to to able to try every combination to work out which uses the least amount of bought in cut lengths.

Example
We purchase plastic tubes in 6000mm lengths and will have a cut off piece from the previous job.
We have an variable number of jobs each to be cut at variable lengths.
I need to try every combination of cuts using the off cut and then stock pieces to work out which combination uses the least amount of tubes and has the least waste.

Need any more information let me know.

Regards

Jim Bob Joe
0
Question by:Jim_Bob_Joe
• 8
• 6

LVL 20

Expert Comment

This is similar to the Operating System "Memory Allocation" problem, with the special exception that you don't seem to care about fragmentation, you just want to maximize memory use.

See the wikipedia article on dynamic memory allocation and also this page for some code examples: http://www.osdcom.info/content/view/31/39/

Common allocation algorithms are "First Fit" and "Best Fit"

I think in this case you want to use the "Best Fit" algorithm, so see below for a sample algorithm of that nature:
http://www.cs.rit.edu/~ark/lectures/gc/03_03_03.html

--
Alain
0

LVL 3

Author Comment

Alain,

Thank you for you suggestions, but i dont believe this is going to give me what i want (for one reason the first is in C???????)   :-)
As this will just fit it into 1 "space" it puts it where it can best. My problem is that i have unlimited amounts of "space"/tubes of plastic, so i need it to work out which ones fit together best to leave the least amount of tube at the end.

example
10 Jobs (1000,1500,2000,1000,2000,3000,2000,1000,500,2000)
obviously the best fit on my 6000 would be to use the whole amount = 2000,2000,2000
leaving me with 1000,1500,1000,3000,1000,500,2000
next 6000 piece would be 1000,1500,3000,500
leaving me with 1000,1000,2000
then on the last piece use 1000,1000 and 2000 and have 2000 left over to use on the start of the next job.

Hope that makes sense

Regards

Jim Bob Joe
0

LVL 20

Expert Comment

Okay, I think I see what you are looking for now. It is a little different. You're trying as best as possible to make groups of 6000 with your jobs.

This sounds like data structure memory footprint compacting. I'm going to look for the algorithm for it, I've seen it before. Its baisically when you have fixed size memory blocks (like 6000kb) and you have a bunch of variables of different sizes, and you're trying to order all your variables such that they fit into as few memory blocks as possible.

--
Alain
0

LVL 20

Expert Comment

Aha! I finally remembered the type of problem that this is:
http://en.wikipedia.org/wiki/Bin_packing_problem

Available algorithms are mentioned in the article.

--
Alain
0

LVL 3

Author Comment

Alain

This is still not what im looking for. I downloaded the PHP example from the site, roughly converted it to vb although i did notice before hand that it would not do what i want.

I have attached my VB example as per your last recommendation.

You will see that this just fills available spaces not taking into account that the sequence of jobs would be better used in a differnt combination.

It needs to try every single combination possible until it works out the best way to have the least amount of waste.

Regards

Jim Bob Joe
``````Const binSize As Double = 100

Const jobs As String = "10,20,30,40,50,60,70,80,90,100,10,20,30,40,10,40,70,20,80,10,10,40,20"

Private pointerArray()

Private hashIndex() As JobItem

Private totalCargo As Double

Private Bins()

Private JobCount As Double

Private Remaining As Double

Private BinCount As Double

Private Type JobItem

ID As Double

JobNo As String

Length As Double

Used As Byte

End Type

Private Type Bin

JobID As Double

End Type

Dim DaSplit, BinID As Double, CurrentBinTotal As Double, i As Double, CurrentBin()

totalCargo = 0

JobCount = 0

DaSplit = Split(jobs, ",")

For Each Item In DaSplit

JobCount = JobCount + 1

ReDim Preserve hashIndex(JobCount)

ReDim Preserve pointerArray(JobCount)

pointerArray(JobCount) = JobCount

hashIndex(JobCount).ID = JobCount

hashIndex(JobCount).JobNo = JobCount

hashIndex(JobCount).Length = Item

hashIndex(JobCount).Used = 0

totalCargo = totalCargo + Item

Next

'Pack

BinID = 0

Remaining = JobCount

While Remaining > 0

CurrentBinTotal = 0

BinCount = 1

ReDim CurrentBin(1)

For i = 1 To JobCount

If hashIndex(i).Used = 0 And (hashIndex(i).Length + CurrentBinTotal) <= binSize Then

hashIndex(i).Used = 1

CurrentBinTotal = CurrentBinTotal + hashIndex(i).Length

ReDim Preserve CurrentBin(BinCount)

CurrentBin(BinCount) = hashIndex(i).ID

BinCount = BinCount + 1

Remaining = Remaining - 1

End If

Next

BinID = BinID + 1

ReDim Preserve Bins(BinID)

Bins(BinID) = CurrentBin

Wend

'Output

Dim TempBinSize As Double

For i = 1 To BinID

TempBinSize = 0

For Each Item In Bins(i)

If Not IsEmpty(Item) Then

Debug.Print hashIndex(Item).ID & " - " & hashIndex(Item).Length

TempBinSize = TempBinSize + hashIndex(Item).Length

End If

Next

Debug.Print "Used: " & TempBinSize & " - Wasted: " & binSize - TempBinSize

Next

End Sub
``````
0

LVL 20

Expert Comment

The article explains that what you want is an NP complete problem, (that means it is a well known problem that is exceedingly complicated an no known algorithm can solve it in polynomial time). Therefore, it is not feasible to expect the absolute best case, you can only be guaranteed 11/9*the optimal solution+1 bins at best with the given polynomial time algorithms.

So if you're trying to avoid an n^n algorithm (trying every possible combination), the only thing you can accept is one that yields a sub-optimal solution.

Sorry, no one likes hearing the answer "it can't be done" but without trying every combination, it really can't be done.
0

LVL 20

Expert Comment

The article below outlines a sophisticated way of solving the problem exactly, using pruning.
It's a bit better than brute force, but if your jobs list becomes greater than 100, it probably won't be feasible for you to use even this.

http://ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/179.pdf
0

LVL 3

Accepted Solution

Jim_Bob_Joe earned 0 total points
Alain,

Sorry for the delay in getting back have been working on something else until i could come back to get my head round this.

Your last document suggestion made absolutely no sense to me, so unless you can translate it to vb it is no good.

I have managed to make a basic solution that does what i want and not that bad either on the few batches i have tested it with compared to an off the shelf package. I have attached the code (does need cleaning up as this is just a concept but does work) for anyone else that is looking for a similar solution.

After quite a bit more searching i found other source code but none of them were as efficient as mine, although this can be dependent on the differnt batches.

If its ok with you, unless you are able to help with that document i would like to half the points as i was unable to get a suitable solution from your answers but they did give me some ideas on making my own solution.

Regards

Jim Bob Joe

``````Dim rs As Recordset, Remaining As Long, BinCount As Long, BinTotal  As Long, rsBins As Recordset, stdLength As Long

CurrentDb.Execute "DELETE FROM tblPieces"

CurrentDb.Execute "UPDATE tblJobs SET Used = 0"

stdLength = 6000

Set rs = CurrentDb.OpenRecordset("SELECT Count(JobID) AS JobCount FROM tblJobs")

Remaining = rs!JobCount

BinCount = 1

BinTotal = 0

Set rsBins = CurrentDb.OpenRecordset("SELECT ID, Jobs, Remaining FROM tblPieces")

rsBins!ID = BinCount

While Remaining > 0

Set rs = CurrentDb.OpenRecordset("SELECT JobID, Length, Used FROM tblJobs WHERE Used = 0 AND Length <= " & (stdLength - BinTotal) & " Order By Length Desc")

If rs.RecordCount <> 0 Then

BinTotal = BinTotal + rs!length

rsBins!jobs = rsBins!jobs & rs!JobID & ","

Remaining = Remaining - 1

rs.Edit

rs!used = 1

rs.Update

If BinTotal = stdLength Then

BinCount = BinCount + 1

rsBins!Remaining = 0

rsBins!jobs = Left(rsBins!jobs, Len(rsBins!jobs) - 1)

If Remaining > 0 Then

rsBins.Update

rsBins!ID = BinCount

BinTotal = 0

End If

End If

Else

If BinTotal = 0 Then

MsgBox "Its all gone wrong"

Exit Sub

Else

BinCount = BinCount + 1

rsBins!jobs = Left(rsBins!jobs, Len(rsBins!jobs) - 1)

rsBins!Remaining = (stdLength - BinTotal)

If Remaining > 0 Then

rsBins.Update

rsBins!ID = BinCount

BinTotal = 0

End If

End If

End If

Wend

rsBins!Remaining = (stdLength - BinTotal)

rsBins!jobs = Left(rsBins!jobs, Len(rsBins!jobs) - 1)

rsBins.Update
``````
0

LVL 20

Expert Comment

It looks like you ended up using the "Best Fit Decreasing" Bin Packing Algorithm mentioned in my first and third post.

You sort your remaining lengths from biggest to smallest and then insert the first one that can fit into the remaining space in the current bin, correct?

Note that, as I said, this is one of the simplest available solutions, but it's still sub-optimal.

For instance, if you have lengths 3000, 2000, 2000, 2000, 1500, 1500
your algorithm will sort:
3000 | 2000 | (1000 unused)
2000 | 2000 | 2000 | (0 unused)
1500 | (4500 unused)

When the optimal solution would have been
3000 | 1500 | 1500 | (0 unused)
2000 | 2000 | 2000 | (0 unused)

Test it out, I think you'll find the sub-optimal solution will result.

Honestly though, it often isn't worth trying to implement the more complicated solution from my last post. If you have a good standard distribution of job lengths and a large sample size, you should find that even the sub-optimal solution isn't that bad.

--
Alain
0

LVL 20

Expert Comment

Sorry, what I meant to write in my most recent post is that with lengths lengths 3000, 2000, 2000, 2000, 1500, 1500, you should expect your algorithm to sort:
3000 | 2000 | (1000 unused)
2000 | 2000 | 1500 | (500 unused)
1500 | (4500 unused)

--
Alain
0

LVL 20

Expert Comment

I definitely nailed this one.

--
Alain
0

LVL 3

Author Comment

I would not go as far as to say you nailed it as you will see from my last comment your solutions you passed me to made no sense and did not work which is why i posted my own code.

I will however accept your solutions as you did at least try to help and i want the question to stay with my answer above for others to see.

Jim
0

LVL 3

Author Comment

Well i dont want any points back, i dont need to give them to myself.

Alain put efforts in to try and find a solution. Just none of them were what i wanted.

Regards

Jim
0

LVL 3

Author Closing Comment

Please see my response with source code for this solution.

0

## Join & Write a Comment Already a member? Login.

### Suggested Solutions

Title # Comments Views Activity
Excel object stays open 19 65
Validating VB6 Function 19 49
VBA error replacing data 6 34
How to make an ADE file by code? 11 35
The debugging module of the VB 6 IDE can be accessed by way of the Debug menu item. That menu item can normally be found in the IDE's main menu line as shown in this picture.   There is also a companion Debug Toolbar that looks like the followin…
When designing a form there are several BorderStyles to choose from, all of which can be classified as either 'Fixed' or 'Sizable' and I'd guess that 'Fixed Single' or one of the other fixed types is the most popular choice. I assume it's the most p…
Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
This lesson covers basic error handling code in Microsoft Excel using VBA. This is the first lesson in a 3-part series that uses code to loop through an Excel spreadsheet in VBA and then fix errors, taking advantage of error handling code. This l…

#### 743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!