Solving the Job Shop Problem with Google's OR-Tools

Introducing the Problem

A manufacturer of custom furniture relies on several machines to create their product. These machines can include a circular table saw for cutting wood, a CNC machine for shaping metal parts, a belt sander for creating smooth or textured surfaces, a paint and varnish applicator, an upholstery sewing machine, etc.

A job is composed of several tasks, each of which requires the use of one of these machines. The tasks must be performed in a specific order: it would not make sense to paint a part made of wood before it has been sanded, let alone before it has even been cut. By design, a machine cannot work on multiple tasks simultaneously.

The immediate benefit of optimized scheduling is the time saved for processing several jobs. An efficient use of machine time minimizes delays in the delivery of products, and it prevents machines from being underutilized which prevents wear and tear.

The Problem and its Constraints

The problem is to determine the optimal schedule that enables several jobs to be processed on multiple machines in the least amount of time. This is known as the Job Shop Problem.

The job shop problem has several constraints:

1. a machine can only work on one task at a time;

   
   

2. once a task begins on a machine, it must continue until it is finished;

   
   

3. a task can not start on a machine unless the previous task for that job is finished.

The goal is to minimize the so-called makespan, i.e., the total time that it takes to complete all tasks of every job in the queue, from the start time of the first task of a job to the end time of the last task of another job.

Problem: How do we schedule these tasks so that it takes the least amount of time to complete all jobs in the queue?

As the number of jobs, tasks, and machines grows, so too does the complexity of the problem. Thankfully, Google's OR-Tools has solutions that optimize this type of scheduling.

Solving the Problem with Data Science

Within a job, each task is denoted by a pair of numbers (m, t):

m: is the number of the machine on which the task must be processed;

t: is the units of time the task requires (e.g., hours).

For example, a job might have three tasks in order such as: (1, 3) → (5, 2) → (2, 1)

This means the first task of the job (1, 3) must be processed on machine 1 and takes 3 units of time.

The second task (5, 2) must be processed on machine 5 and takes 2 units of time.

The third and final task (2, 1) must be processed on machine 2 and takes 1 unit of time.

The input to the Job Shop Problem is multiple jobs of this type. The shop manager creates a list of jobs and their tasks whose data is fed into a series of Python scripts that find the optimal schedule.

We build several Python scripts to solve the problem:

create_model:

This function takes as inputs the jobs data, which is the set of all jobs and their tasks as described in the preceding example, and the horizon, which is the non-optimal upper bound on the total time it would take to complete all jobs and tasks. It returns a model for the jobs, a list of all tasks, and the machine intervals.

add_constraints:

This function is responsible for setting the problem's no-overlap and precedence constraints as listed above, i.e., the fact that a machine can only perform one task at a time, and that a task must be completed before the next one is started. Its inputs are the model, the jobs data, list of tasks, and machine intervals from the create_model function.

set_objective:

This function defines the objective of the optimization process, which in this case is to minimize the makespan. Its inputs are the model, the jobs data, the list of tasks, and the horizon.

create_solution_dict:

This function takes as inputs the jobs data and the list of tasks to solve the optimization problem, and outputs a dictionary that holds the solution.

create_solution_str:

This function converts the solution dictionary to a formatted solution string making it easier to read.

print_solution:

This function takes the solution string and prints it to the log file and to the terminal for the user.

plot_solution:

This function takes the solution string and plots it on a schedule.

Initially, the scripts above instantiated the data problem by using a function called build_jobs_data, where the (machine, time) coordinates of each task for each job were hard coded.

Instead of using build_jobs_data, a more user-friendly alternative was adopted:

• HTML Page: Create input fields for the user to specify the machine ID, task duration, and job sequence.

  
  

• JavaScript Logic: Capture the data from the input fields and format it into a JSON structure, then submit it for processing.

  
  

• Integration with Python: Use a local server (e.g., Flask) to handle form submissions and pass the data to the Python script create_model.

Results & Conclusions

Figure 1 shows the HTML web form that the shop manager completes. The form currently accepts a maximum of 5 jobs for illustration purposes, but the number of jobs can be set much higher as needed.

Fig.1: Web form enabling dynamic data entry for the Job Shop Problem.

When the form is submitted, the solver finds the optimal schedule and posts it as shown in Fig. 2.

Fig.2: Optimal schedule for the jobs and tasks as defined in the Web form from Fig. 1.

The optimal schedule shown in Fig. 2 takes a total time (i.e., makespan) of 11 hours. Notice that each machine only performs 1 task at a time. Also notice the fact the tasks for each job do not start until the previous task for that job has finished.

Thus, the solver successfully found a solution that optimizes the scheduling of these jobs in the least amount of time possible.

Conclusions: implementation of this solution to the job shop problem is easy and non-disruptive. It reduces machine down-time, and keeps the job chain running smoothly and efficiently. Taken together, this can save the company several hundred to several thousand dollars per job.