I am working for a company that manufactures windows.
The project timeline looks like this:
1. A potential customer calls for tenders
2. We then hand in a proposal/offer which matches the specifications
3. Ideally, we are accepted
4. The windows are produced

Now between 1 and 4, things can change.

1. The client requests different windows, window catches, glass, color, what not

--> This is pretty straight forward, details will change, sizes will change, etc.

2. Windows are taken apart to produce them more efficiently:

--> Example graphics below:

1.


In this one: The window is offered as a connected two-piece but both windows will be produced individually and then put together later in the process. Now it could be that we have also offered this window:



In that case, the first half on the left will be produced as one position but the two right positions will be produced individually.


2.
A more complex situation:


Here the entire window will be offered as one piece but will be produced in four different pieces.


I hope you get the point.


So, now starting with the actual software part:
Basically right now after every project is finished, there is someone who has to compare offer to actual. This can be a tedious process because he has to go through the data and compare and see where something changed, etc.

The thing is, it is not really smart work but just tedious and inefficient. We have all the data in databases there is nothing manual to be done besides figuring out which position in the offer belongs to which position in the production.

To me, this could all be solved with an algorithm. But I am uncertain as to how much time (essentially money) it would cost and how easy this would be to execute.


I, myself, have interest in learning more about data analysis, algorithms and the like. The company has a wealth of data that is currently more or less not used for analysis.


Trying to sum up what I am looking for:
- Difficulty to write an algorithm that does the comparison
- Starting points to learn more about algorithms
- Required programming languages (currently the company operates almost exclusively on Microsoft Office + VBA and SQL databases)
- General insight into algorithms, tips on how to think and structure one, etc.


I hope this all makes sense

If you are looking for something that simply shows the changes in the size of the windows, the positions, color, how often, etc, then a relatively simple database view + query will do the trick, but this would be a db design issue more than anything.

Not trying to discourage the use of a programming language, but I'm thinking you'd end up building a set of joins in said language and that isn't too smart to do when you have a very powerful tool for this kind of work. I love relational algebra just as much as the next guy, but yuck.

After getting the database reporting part down, what would adding a programming language to the machine accomplish?

It's more complex than a database view.
Windows can end up not being produced, or the opposite being produced while not being in the offer, etc.

While the final production is originally based on the offer, there is not one unique identifier to connect between the offer offer and the production.

I am looking for a way to replicate a thought process more than a simple matching.

Use a lookup table. This will allow you to express multiple productions for each offer. The rest would be a tad tricky though.

No matter how you program it, you have to have a lookup somewhere and I think it is faulty that you don't have this expressed in some way in your database. I doubt it is possible to express this implicitly using raw code.

I'm just trying to get the conversation started. Hopefully I'm proven wrong.

Yeah, I'm not taking offense or anything. I am really new to this, so I'm probably incorrect most of the time.



The database structure would allow this. We have somewhat of a system in place that connects the offer to the production. But that only works out if the offer and production are similar (same amount, window not split up, etc.).
And we definitely would need look ups in the code but they need to be smarter than just a like for like comparison.

I try to illustrate the problem with a look up in an example:
We offer two windows:
1. 6 two piece windows comprised of a 4x4 window and a 4x8 window.
2. 9 two piece windows comprised of a 4x4 window and a 4x12 window.

In this case, the production would often times split up the two offer positions into three production positions:
1. 15 4x4 windows
2. 6 4x8 windows
3. 9 4x12 windows

With a look up there is now now way to replicate this because it looks like three completely different things (if I am wrong, please show me a way because this is actually one of the main struggles).

A human being will have no problem recognizing what happens. In a database I have no idea how this could be worked out.
Now I am trying to have an algorithm that replicates the thought process.


There are different scenarios where for example two offer positions get compromised into one production position:

We offer:
1. 6 4x4 windows
2. 4 5x5 windows

The customer then wants to decrease the size of 4 of those windows, now the production position look like this:
1. 10 4x4 windows

Now the key association wouldn't work because we have more offer ids than production ids. A human being could again easily see what's going on.


I think I cannot solve those two scenarios in a look up because the parameters change fundamentally.

The offer positions and the production positions often times look very different due to changes in the process.

Read through your posts. I believe it is feasible, not sure of the cost. A lot would depend on if you can come up with an off the shelf solution.

It doesn't seem too bad. At a really high level I'd imagine a database would have:

1. The pieces you offer/produce
2. Offers you've made that reference the pieces they want. This would be versioned so if a user changes what they want you'd create a new version of the offer.
3. Production runs that are past the point of no return (simplistically - once the windows are produced.)

The key is that I wouldn't store in the database what a potential production run looks like. That'll be calculated as necessary based on the latest versions of each offer you're looking at (potentially all open offers that aren't associated with a final production run).

The logic of condensing multiple offers of various pieces into a production run should be pretty straightforward. You're just grouping a list of items with duplicates by their type and returning the sum for each type.

Edit: Reading through some of your other comments, this strategy should work but your logic might be a bit more complicated. You'll just need to associate offers to multiple finished production runs. And your logic for determining potential production runs will take into account when parts of an offer have already been produced.

So if you have two offers of:
5 4x4 and 10 4x12
10 4x4 and 15 1x1

The first time you calculate production runs you'd have:

15 4x4, 10 4x12, 15 1x1.

At some point your 4x4s get built. Now when you calculate your potential production runs you just take into account what you've already built and would get:

10 4x12
15 1x1

This is pretty much how the database looks like currently.
If a position from the offer is produced in the same way then the position will be copied into a production position.

This is currently all done manually. The company is decades old and this is how it has been done. The project manager looks at the offer and see how it makes the most sense to produce it: grouping offers, splitting it for multiple houses for example, takes into account delays if part of an offer position needs to be produced later, etc.

There is definitely potential to do this step automatically as well - at least to a certain extent. But the thought process is more complex due to certain things that are specific to the business. I will try to push for that in the future as well, that's why I want to learn more about algorithms in general.

The comparison would always be done when all of the production is done. It's in the last steps when we are doing the settlement with the customer we are looking at what has actually been produced and how it differs from the offer.

So you are correct that we would need to look at the offer and associate them with the production positions. Then we make a side by side comparison. This is now all done manually. Someone looks through the offer and the production list and associates the positions manually. This is tedious work and takes way too long.

In the end for example the window size is always different, so the algorithm would need to be able to be able to take that into account. There are a few caveats that exist and are easily handled with experience but would need to be included in the algorithm.

I'm still not sure what step you want to automate exactly, but any of the steps you mentioned as happening manually seem pretty easy to automate.

The general approach to switching to an automated process is to start with a very simple algorithm that produces potential production runs. Then you have a person review that and make whatever tweaks they think are necessary. Gather those tweaks over time and figure out what rules you need to add to the algorithm. At some point in time you're probably going to be confident enough in the algorithm to just drop the human from the process.

Edit: To be clear, I really don't think you need much algorithm knowledge for this problem. You should be able to write something simple with just basic programming skills.

I want to automate the step where in the end the offer positions are matched with the production positions.
I dont want to automate the production step.

I think that it's easy as well. I am just not sure how to really approach it. Because in the end the production positions are almost all different from the offer positions (sizes change, positions are redistributed, nomenclature for offer and prodution positions is different, etc.).

Currently, the only thing the production person does is enter the offer position if it fits. If not he will write nothing in it. So the only tool we have in place is a simple matcher between the positions that fit, everything else is manually adjusted to make it fit.

I think that it's easy as well, but I have not yet found a way to really approach this.


Thinking about it, an approach would look like this:
Take offer position 1 (OP1) and go through all the production positions (PP). If there is a fit it takes OP1=PPx.
If it does not find a fit it looks if the offer position could be split up into two windows (OP1.1 and OP1.2), it then takes OP1.1 and looks through the PP and sees if there is a match, repeat with OP1.2. The more complex positions would be a later step.
On each iteration the already fitted windows would be disregarded to speed up the process. Variation would be to go through every PP with every OP in case a later OP matches "better" with a PP.
All unmatched OPs and PPs would then be declared as omitted/added.

The fitting process would need to assign weights:
- size and glas type as the largest weights
- window catchers and other details medium weights
- minor details with little weight

I guess this could be done in VBA (I'm proficient in that) because it shouldn't take a huge amount of time.

One of the first things I'd do is really figure out what your logical concepts are.

So if I understand correctly you might sell "Window 1" to the customer but its actually made up of multiple pieces. Internally, I'd represent the 'offers' as being made up of the individual pieces that actually match the physical things you produce.

The concept of "Window 1" is just a sales concept for talking to the customer. So an order might have "Window 1" in it, but the first thing I'd do in code when interacting with that order is convert the sales concept to the production concepts.

But yes, VBA is almost certainly going to be good enough for now. If its ends up being too slow - it's pretty easy to migrate VBA to VB which should offer more than enough performance improvements to make your solution workable.

The thing is sometimes a window is being split up sometimes it isnt. And we cant divide it up in the offer process because more offers are declined than accepted.

So the splitting up part would need to be done in the code/algorithm (not a problem I guess). But it seems like you agree with my logic behind it and I think it does make sense.

Anyone with objections?
And anyone with recommendations on literature (digital or physical) on algorithms. The basic concept behind it makes sense to me but there is probably a ton of stuff I have not thought about.

It shouldn't matter about sometimes being split or not. So for example:

"Window 1" (X) -> 1 10x10 (A) pane of glass
"Window 2" (Y) -> 2 4x4 (B), 3 4x8 (C) panes of glass.

I'd treat that as two customer concepts (X, Y) and three production concepts (A, B, C). It doesn't matter that X is 1-to-1 with A, its still a separate concept.

So then I'd say offers are phrased in terms of window ids (and stored that way), but all of your logic would always convert the window ids to the production ids as soon as possible (possibly even in the query you use).

The production IDs are manually converted because it's a more complex thought process. It needs to take into account a lot of things that a human being currently thinks of. In the future this steps needs to be automated as well but currently I see it as a bigger piece of work.

The matching process needs to replicate the logic of the person creating the offer and the one dividing it up for production and then match those.


I hope we dont talk past each other.

Yeah, I don't really understand.

Which is ok. I can't imagine though that its a hard process to program (which I think is your main question). You might have a lot of factors to consider, but given that your output is something that is physically produced it shouldn't be that hard to represent it all in software.

Not sure I quite understand the problem either, isn't this perhaps some sort of variant of the knapsack problem?

I am a bit too tired right now, but I will try to explain it again tomorrow.

I just quickly read the wiki article and it is definitely a variant of that.

If it's a knapsack problem then the only way to find the optimal solution is brute force every combination. Not sure if you're after an 'optimal' solution or just lots of solutions. But if you have all possible solutions you can search them to find the best one based on whatever your requirements are.

Computers are fast, and unless you've got hundreds of shapes this should be doable in < a few minutes per problem. But it can be hard to write (but quite fun).

FWIW when I was less experienced, I attempted to write a brute force for a similar problem for printing shapes on a defined piece of paper to save as much wastage as possible. It worked badly, and was a lot harder to do than I thought (partly due to printing limitations that made it even more difficult such as cuts must go through the entire width). But you can see the obvious value to solving those sorts of problems.

For windows it will probably be easier as I'm assuming you're dealing only with rectangles and squares on a 2 dimensional surface. And if you can do it it's probably quite valuable. You should be able to order the solutions by cost or something similar to give the best margin for the company.

You'd start by:

- Defining your problem area (where the windows should fit)
- Then filtering all the windows you could possibly use for the area based on customer demands/limitations of the product
- Then iterating every possible combination of windows in that space that fit that you can use.
- Run it on simple problems then increase the complexity. You might find it comes up with stupid designs (100 small windows) so you could then add pruning (max 6 windows per solution) or something like that.

This probably isn't the exact expression of your problem but I hope it helps! I love writing code for those sorts of problems. You should learn a lot about writing for performance, and you can improve it significantly once you start pruning. From the get go if you do want to go the brute force route, make sure you benchmark your code regularly to give you a rough idea of how long solving an actual problem will take. If you don't write it well, and depending on how many possible solutions there are, you could find it easily runs into the hours per problem.

I will get back to this tomorrow, but it will be a bit easier than this, because the "shapes" are defined by the offer positions and only need to fit the production positions.

It's more a comparison than an optimization, so I guess in that sense it does differ from the knackbag problem. It needs to find the optimal fit for each offer position in all the production positions.

I will try to make the steps more clear and maybe do a step by step example on how a human being would solve it.

I whipped this up way too fast, but I'm thinking a schema similar to this would work out for you. Just trying to express the idea and no, I wouldn't do this in real life. I didn't add the positions to this, so you'd need to add that. I'm guessing that you'd want the positions to have some size?

If you are attempting to create items that fit in a certain part of the window, then you can probably try greedy algorithms, assuming the idea is to minimize the cuts. Use the window_cuts and the missing position_size table to grab the possible combinations.

****, I had a long post that got deleted.

Basically, after reading up a bunch I am looking at dynamic programming. Greedy algos would work but they are not precise enough.

daveT,
your structure is somewhat implemented currently but I couldnt go ahead and extent it. Also the real challenge is in matching the complete windows with each other not just on size. The produced windows could function as a list of all possible windows but we would end up not matching that much because too many little details can change.
So I need a smart way to go through all the production positions and fit them to the offer on a best guess basis.

From what I'm gathering, you are looking for what is called the "bin-packing" or "best-fit" algorithm.

The main difference between bin-packing and best-fit is that bin-packing calls for best position without taking things out while best-fit calls for taking things out and reshuffling until the best solution is found. Unfortunately, neither algorithm is solved and both are NP-hard or complete (can never remember which on this stuff). Yes, dynamic programming partly attempts to solve the issues with NP problems. The main consequence with dynamic problem is the same issue you have with greedy algorithms: you're not guaranteed to find the best answer.

In order to guarantee the best answer, you have to look those algorithms that do guarantee the best answer, and unfortunately, they are brute-force algorithms. This means that as (n) gets large, you're time complexity grows fast, which is a nice way of saying that your algorithm will be slow. The point of using the database design I suggested was to minimize this (n) by automatically tossing out the items that are too large. You can probably constrain the algorithm further by saying that window-cut must be greater than equal to say 60% of the initial space.

Once again, I'm hoping that I am proven wrong on all of this, because I just wrote a dire story.

I will be able to eliminate certain parts from the algorithm:
- perfect fit between offer and production, those go out immediately
- huge differences in size

and probably some more that I cannot think of off the top of my hat.

I have to read through best-fit and bin-fit articles. I would say it's best fit but have to see.

The thing is, even if it takes a long time the operation is not done that often and takes a lot more time now. We are also looking at a maximum of roughly 100 offer positions and 100-200 production positions and that is the absolute exception. More often you have like 20 offer positions and 25-40 production positions. So this will not be an issue.

I'm kind of confused on why you need to fit the produced goods to the window offers in a "best-fit" type of strategy. In my manufacturing naivety - I assumed you were producing only windows that were ordered. Is it just because Production is often making production runs with excess capacity and you need to fit that 'excess' to new orders as they come in?


One thing to remember is that you probably don't need to worry too much about finding the absolute best solution. If people are doing this job manually now I would suspect they're also not finding the best solutions.

I think I have you confused with the term offer. The offer is done individually for each customer, it's not our product offer. It's a proposal/quote for the customer on how much it would cost.

I try to make an example:
When you build a house, you get an architect to design everything including where the windows should be, how large they should be and other details.

So a window in your living room will be 2081x1333 because that is how the architect wants it.

Now the architect has written an initial document including plans on how the property looks like. We are now replicating the windows in the house in our offer and calculate a price.

If the offer is accepted, we now start to produce the windows but often times in the offer the windows have a slightly larger size due to something that has to do with how they will be installed later.

So the window in production will be 2051x1283.
But it could also happen that the architect changes his mind, the homebuilder wants to save money and what not so we reduce the size to 1888x777. Now the produced window will be 1888x777 but the offer position has a way larger size. We assume that all the details stay the same so we would now need to match those positions although they are way different on size.

Now the same could happen to the thickness of the glass, the style of the window catch or the color of the window.


The process I am now trying to replicate is when after the job is done we have a settlement with the customer on excess charges or reductions. To prepare the meeting we go through every position in the offer and see where we did more/less than we should have.
To see that we need to match the offer positions with the production positions. This is currently being done manually.