How can I find the shortest path solution or even begin to finding the most optimal solution to a weld robot sequencing problem? [closed]

Question

Not sure this belongs here, but I thought I'd ask: How should I come to an understanding of an optimal weld sequence for a weld robot that welds a physical item on a revolving carousel (the gray T depicted)?

Ok, so the green points need to be welded in the horizontal position (eight on each side), i.e. 180 and 0/360 position (it is currently in the 270 position). The pink points need to be welded in a 0-15% position in the direction indicated. There is no welding from below, i.e., the downward facing pink arrows need to be welded in a downward orientation, and then flipped to weld the other side. In this depiction there are two sides, downward pink arrows can all be access in the 270 position which it currently is in, upward facing arrows need to be rotated to 90 position. The robot can reach the pink arrows in the back in both these positions. The pink arrows all need what is called a "root pass", and need to cool for at least 10 seconds because they also need a "fillet cover" which if done one after the other too fast can cause imperfections. So all eight pink welds have a root and a cover that need to be staggered by at least 10 seconds. The idea here is to limit the travel on the robot, reduce the number of rotations of the carousel, and reduce the time it takes to weld the whole assembly. The depiction is not to scale, the cylinder with the hangman is the robot in its home position.

So, you can ask questions like if I go from home and start on the left downward pink on robot side and rotate to 360 weld out all the green, then weld the right downward pink on robot side would it be the same if I weld both pink downward robot side then all green, and then move on to upward pink at 90 by that time downward pink will be cool should I rotate back to 270 to cover or should I continue to the other side. I don't know, I'm just trying to formula one this so it's as fast as possible. Any thoughts?

Also, at the end it will rotate back to 270 to flip to the other side to be stripped. That is, the carousel is on a carousel.

I was hoping this was the kind of thing that didn't require dimension and could be reduced to graph or something.

Answer 1

This is a scheduling problem. There is a huge literature on problems like this.

This could be a puzzle, I suppose, if it were well formulated. As it stands, we don’t know the relative costs involved. What is the cost of a 10-second wait? What is the cost of an n-degree rotation? (Time and wear on the machine.) What is the cost of a flip?

Also, we would need to know whether you need to optimize for cost or time or some combination.

Here’s how I would approach this kind of problem. There are 32 welds that need to be done. For each pair of welds, figure out the cost of the transition from one to the other. That would be 496 calculations. Then use a dynamic programming approach to find an optimal or near-optimal sequence of operations. One tricky thing about this is checking whether the 10-second waits are satisfied in scenarios where the root pass and correspond fillet cover are separated by another operation. I’m guessing you can ignore the issue then check your answer to see whether it is satisfied. If not, you might need to add a few seconds wait here or there. In that case you might not get the absolute minimum solution, but no big deal… a solution that is nearly minimum is acceptable too, I would hope.

Good luck.