Python – Advanced Job Shop Scheduling Algorithm Question

algorithmsmachine learningpythonscheduling

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.

Best Answer

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#.

Related Solutions

Scheduling – How to Make a Cluster Run a Task Only Once

Do you have a shared database? I've done this using a database as the arbiter in the past.

Basically, each "job" is represented as a row in the database. You schedule a job by adding a row to the database with the time you want it to run then each server does:

SELECT TOP 1 *
FROM jobs
WHERE state = 'NotRun'
ORDER BY run_time ASC

That way, they'll all pick the job that is scheduled to run next. They all sleep so that they wake up when the job is actually supposed to run. Then, they all do this:

UPDATE jobs
SET state = 'Running'
WHERE job_id = :id
  AND state = 'NotRun'

Where :id is the identifier of the job you got in the step above. Because the update is atomic, only one of the servers will actually update the row, you can check the database's "number of rows updates" status code to determine whether you were the server that actually updated the row, and therefore whether you are the server that gets to run the job.

If you didn't "win" and you're not running the job, just go back to step 1 immediately. If you did "win", schedule the job to execute in another thread, then wait a couple of seconds before going back to step 1. That way, servers that didn't get the job this time are more likely to pick up a job that's scheduled to run immediately.

Scheduling Thousands of Recurring Jobs

You can use a list of triggerables, sorted ascending by the time of the next trigger. When you need to trigger something, you can always pick off the front of the list, O(1). When you need to (re)schedule something, you can fit it in the list in O(log N) time.

It would be fairly simple & straightforward, and you can leverage any form of timer API (your scheduler needs to wake up only when the front of the list needs to be triggered).

Best Answer

Related Solutions

Scheduling – How to Make a Cluster Run a Task Only Once

Scheduling Thousands of *Recurring* Jobs

Related Topic

Scheduling Thousands of Recurring Jobs