7

I've looked into numerous solutions for the simple version of this problem, but I've found no solutions for advanced cases, short of sorting through all possible permutations.

I don't know where to begin this question, but I'll do my best.

In my case, this will be in reference to a machine shop.

In order to run a part through a set of procedures using a cnc machine, the machine must first go through a setup process. This time varies depending on what type of part was run last.
Lets say widget A requires tools 1 and 2 to be put on the machine. There were no previous tools on the machine and each tool requires a minute for it to be install correctly. This means that widget A requires a 2 minute setup time. Now, lets say widget B requires tools 3 and 2. In this case, since tool 2 can be used again, it only requires 2 tool changes (removing tool 1 and installing tool 3).

Next, you have the process time that the part actually requires to be build on the respective machine. In most machine shops, this varies depending on what machine it's being run on.

Then you have constraints like the date that a part is required by and weights to certain jobs (if a job is flagged as "rush", its requirements are weighted higher than similar orders).

Luckily, in my case, I have the majority of this data. My system has collected the time a machine takes to build a specific part as well as the setup time required between different parts. The reason I'm looking into a programmatic way of optimizing this schedule is because there are thousands of different parts and it requires a full time worker with extreme knowledge of the shop to schedule days out. Even then, calculating lead time is a nightmare and it's just a ballpark estimation in the end.

I'm curious if anyone here has dealt with similar issues and could point me to some research material that I might find interesting.

I know this is cobbled together, so I'd gladly answer any queries for additional information.

dvdnnn
  • 79
  • 2
  • 1
    *Scheduling is a hard problem.* Here is a small taste: http://www.math.mcgill.ca/vetta/CS760.dir/ahmed.pdf – Robert Harvey Aug 10 '16 at 22:24
  • I understand this is _online_ scheduling? As you say, you're planning days out, so new jobs are probably being added to an existing schedule. And with rush jobs coming in, you probably want to reschedule lower-priority jobs. It's not "plan once, then do" offline scheduling. – MSalters Aug 11 '16 at 08:23
  • Exactly. So it's become a huge pain. I've made prototypes that will go through all of the different configurations, but it's not practical with the amount of jobs that come through every day. I've even tried reducing the amount of data variation by saying part transitions that require a setup time just had a fixed 30 minutes of setup instead of changing the setup time depending on the type of transition. – dvdnnn Aug 11 '16 at 16:08
  • 1
    So once you have choosen a processing order for the pieces and an assignment which piece to process on which machine, you can easily calculate a cost function (for example, total time needed, with some additional penalties if delivery dates are not fulfilled, or pieces flagged as "rush" are delivered lately)? If you are at that point, you can try something like [Simulated annealing](https://en.wikipedia.org/wiki/Simulated_annealing) to optimize the processing order. – Doc Brown Aug 12 '16 at 12:05
  • Doc Brown is on the right track. See also this question: http://softwareengineering.stackexchange.com/questions/219748/help-suggestions-for-parallel-assembly-line-scheduling-dynamic-programming – Frank Hileman Oct 27 '16 at 17:29

2 Answers2

4

I believe the body of knowledge you are looking for is "Mathematical Programming".

In general you want to build a model to support decision making. To do this i would start with a "toy" model. This is where you take a very small example, say you only have one machine and three orders to process.

You then need to answer some fundamental questions, like

  • What time horizon do you want to optimize across (include in this decision making). For example if an order(of any priority) pops in beyond time x, i wont include it in my scheduling. If you don't have a very big queue this is not such a problem, but becomes more important if youre always receiving new jobs.
  • What are we optimizing? Do we want the minimium cost schedule? or the minimum time schedule? or the greatest flexibility (say to ad a new job in the middle somewhere, or allow for some planned maintenance...). The objectives are going to pull your schedules in different directions(solutions)

  • What, exactly, are the decisions to be made? I would assume that there are two distinct sets.

    A. The order in which to schedule the jobs

    B. The order in which to perform cuts on the individual pieces

Note: if we know B or its time/cost is fixed, then we really just need to calculate transition times between each combination of jobs to be able to solve for A.

example(3 jobs, a1, a2, a3)

a1->a2 = 5

a1->a3 = 10

a2->a1 = 3

a2->a3 = 7

a3->a1 = 2

a3->a2 = 1

we don't need fancy math to see that the "least time" path is a3->a2->a1 = 1 + 3 = 4

However, if B is dependent on A, then we need to incorporate all of the possible schedules for A in determining a joint solution for A and B that minimizes time or cost, or maximizes revenue.

If you need to solve B, this is the hard problem, as it involves calculating and determining least cost paths through the part geometry. Id go so far as to say its not likely worth your time at an attempt.

If you need to just solve A, here is a formulation I did in school and a reference

You need to set it up and feed it into a solver if it gets to be of any large size. otherwise for a toy problem you can do it brute force. id recommend the Fico Xpress solver as they have packages/assemblies or whatever you call it for C#.

somedude
  • 67
  • 3
0

Scheduling is hard.

But computing the time taken for a specific order of parts is easy.

The best approach I find is to make a best guess, possibly be brute force in your case, and allow the user to tweak. Showing them the expected time with their setup.

This gives flexibility to the system for things like the rush orders, where a human judgement may be required as well as a 'good enough' for general work suggestion.

Over time, you users may point out where they can do better than your algorithm and you will be able to improve it in those specific cases.

Ewan
  • 70,664
  • 5
  • 76
  • 161