Solved

Optimisation Algorithm

Posted on 2009-07-16
17
308 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
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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Check Disk (CHKDSK) on all volumes and fix if needed. 8 178
Put text in a picture ASP.NET C# 2 50
Looking for VB6 code to read SQL table export it to ascii 8 31
MsgBox 4 45
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…
This article describes some techniques which will make your VBA or Visual Basic Classic code easier to understand and maintain, whether by you, your replacement, or another Experts-Exchange expert.
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 utilization of class modules. Class modules can be a powerful tool in Microsoft Access. They allow you to create self-contained objects that encapsulate functionality. They can easily hide the complexity of a process from…

914 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

21 Experts available now in Live!

Get 1:1 Help Now