Solved

Optimisation Algorithm

Posted on 2009-07-16
17
303 Views
Last Modified: 2013-11-05
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
Comment
Question by:Jim_Bob_Joe
  • 8
  • 6
17 Comments
 
LVL 20

Expert Comment

by:alainbryden
Comment Utility
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

by:Jim_Bob_Joe
Comment Utility
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

by:alainbryden
Comment Utility
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

by:alainbryden
Comment Utility
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

by:Jim_Bob_Joe
Comment Utility
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
 

Private Sub Form_Load()

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

totalCargo = 0

JobCount = 0

'Add

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

Open in new window

0
 
LVL 20

Expert Comment

by:alainbryden
Comment Utility
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

by:alainbryden
Comment Utility
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
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 3

Accepted Solution

by:
Jim_Bob_Joe earned 0 total points
Comment Utility
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.AddNew

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.AddNew

                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.AddNew

                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

Open in new window

0
 
LVL 20

Expert Comment

by:alainbryden
Comment Utility
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

by:alainbryden
Comment Utility
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

by:alainbryden
Comment Utility
I definitely nailed this one.

--
Alain
0
 
LVL 3

Author Comment

by:Jim_Bob_Joe
Comment Utility
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

by:Jim_Bob_Joe
Comment Utility
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

by:Jim_Bob_Joe
Comment Utility
Please see my response with source code for this solution.

0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

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.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now