Solved

Optimisation Algorithm

Posted on 2009-07-16
17
319 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 6
17 Comments
 
LVL 20

Expert Comment

by:alainbryden
ID: 24872827
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
ID: 24873746
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
ID: 24880442
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
Instantly Create Instructional Tutorials

Contextual Guidance at the moment of need helps your employees adopt to new software or processes instantly. Boost knowledge retention and employee engagement step-by-step with one easy solution.

 
LVL 20

Expert Comment

by:alainbryden
ID: 24880550
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
ID: 24882487
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
ID: 24887899
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
ID: 24887919
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

by:
Jim_Bob_Joe earned 0 total points
ID: 25008445
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
ID: 25023742
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
ID: 25023766
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
ID: 25910211
I definitely nailed this one.

--
Alain
0
 
LVL 3

Author Comment

by:Jim_Bob_Joe
ID: 25912334
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
ID: 25929452
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
ID: 31604374
Please see my response with source code for this solution.

0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

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…
If you need to start windows update installation remotely or as a scheduled task you will find this very helpful.
Get people started with the process of using Access VBA to control Outlook using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Microsoft Outlook. Using automation, an Access applic…
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…

697 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