How do you schedule jobs effectively in a job shop? It's a challenge with many potential solutions, but three problems often get in the way of a good schedule.

Job shops are notoriously challenging when it comes to scheduling. As we discussed in a previous article, high-mix, low-volume manufacturers often find it hard to achieve a consistent flow of jobs.

This can be troublesome when you're considering whether to add robots, which have traditionally been best for consistent operations. Even though collaborative robots can reduce this challenge, they don't remove it completely.

But as I like to say, forewarned is forearmed! When you're aware of the potential problems of job shop environments, you can be prepared to tackle them if they arise.

Researchers have studied job shop scheduling for over 50 years. There are common issues that come up again and again. In this article, we discuss three scenarios which can cause problems in a job shop if you're not prepared from them.

•  Read more: Collaborative Robots for Job Shops: How to Make it Work

Why job shop scheduling is hard

In our previous article Job Shop vs. Flow Shop: Can Robots Work for Both? we introduced the main scheduling challenge in job shops: inconsistent flow.

Jobs are often passed between operations on the shop floor as and when they are needed, without a well-defined manufacturing schedule. This makes job shops flexible, but it also means that you can't easily tell how long a job will take to complete.

• Read more: Job Shop vs Flow Shop: Can Robots Work for Both? 

Lowercase NYC produces a maximum of 40 units of a given eyewear model before changing the CNC program for another model.

This is more than just a manager's pet peeve. It's a significant scheduling problem that's been researched for years in a few different fields. Researchers call it "The Job Shop Problem." It also has diverse applications, including flexible manufacturing, railway scheduling, air traffic control, and robotic cell scheduling.

Researchers aim to answer this question: How  can you schedule jobs effectively in a job shop?

The goal of the Job Shop Problem is to minimize "makespan," which is the total duration of the schedule for all jobs. This is different from "cycle time" which is the duration (or average duration) of just one job. The problem is represented mathematically like this:

• We have m machines (or manufacturing processes) and n jobs.
• Each job consists of k operations, each with a processing time of Pk which is bigger than 0 (Pk > 0).
• No job goes through the same process twice in a row (i.e. we assume there are no reworkings).
• An operation is only feasible if its schedule (Sk) begins after the previous operation has finished (Sk+Pk <= Sk+1).
• Find a feasible schedule (Sk) that minimizes makespan Ck.

Although it might seem simple when written out like this, the Job Shop Problem is one of the hardest scheduling problems and is classed as NP-Hard (which is a measure of the difficulty of solving a computationally complex problem).

Three common problems for job shops

Below are three of the common issues that arise in the mathematics of job shop scheduling. They are also an issue for real-world (i.e., non-theoretical) job shops.

1. Transportation or minimum delay

Transportation refers to the time taken to move products from one machine to the next. It's a challenge because it introduces an extra constraint to the schedule. The next operation can't start until the previous operation and transport time has passed. Transport times also vary depending on the distance between different machines, which makes them inconsistent.

Although we call it "transportation time," this challenge also occurs when there are other delays between steps in the process. For example, instances of transportation time in job shops might occur when:

• A robot transports products from one manufacturing process to another.
• The application requires a minimum time for heating or cooling of a product between processes, e.g. metallurgy or food production.
• Products have a minimum setting time, or chemical reactions need time to happen between operations.

In practice, almost all real-world applications include transportation time between processes. It's a good idea to include these times in your scheduling, although you may be able to omit them if they are significantly shorter than the processing times.

2. No-wait or maximum delay

The opposite of transport time is a "no-wait" constraint, where the delay between processing operations should not exceed a maximum time. The next operation must start before the maximum wait time or the product will be ruined.

The no-wait constraint usually occurs when products must maintain a workable condition, e.g. due to heat or chemical reactions. Instances of no-wait scheduling constraints include:

• Applications where operations must be finished before a chemical reaction occurs, e.g. hardening of polymers, setting of cement, etc.
• Products that must maintain a certain temperature while being worked on, e.g. hot metal, cold ice cream, etc.
• Applications where airborne contaminants could compromise product quality or integrity, e.g. food contamination, static interference of electronics, etc.
• Products on a continuously moving conveyor belt, which means that the robot or operator doesn't determine when the product enters or leaves the operation.

No-wait conditions are restrictive and can make scheduling extremely difficult. Try to reduce the number of no-wait conditions to only those that are absolutely necessary.

3. Blocking

The final constraint is "blocking," which means the operation is halted until the product is passed onto the following operation. It indicates a process where there is no "buffer" between the operations – e.g. boxes or piles of Work in Progress.

Blocking is one consequence of the lean manufacturing drive to eliminate buffers between operations. For example, imagine a robot must move a part from a CNC lathe to a milling machine without putting it down. The robot must wait for the milling machine operation to finish before it can move the part from the lathe. This is a blocking constraint.

Blocking is less restrictive than the no-wait condition. However, it can introduce some particular challenges, such as deadlocks – where each operation is waiting on the other to finish and none can continue.

How to solve job shop scheduling problems

There are many solutions to The Job Shop Problem, but they all involve somewhat lengthy and complicated mathematics that are beyond the scope of this blog post. However, it helps just to be familiar with the three common scheduling problems – transportation, no-wait, and blocking – so that you can better schedule jobs in your machine shop.

What challenges do you come across when scheduling jobs in your process? Do you have experience with these three problems? Which one is the most problematic for your business? Tell us in the comments below or join the discussion on LinkedIn, Twitter, Facebook or the DoF professional robotics community.