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

Job shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science where jobs are assigned to resources at particular times. The classic job shop scheduling problem of minimizing makespan was first presented by Fischer and Thompson in 1963 and has been solving in a variety of ways since. As Industry 4.0 adoption increases so does the need to model data that bounds algorithms and guides AI training. Using Google’s Operational Research libraries I ported an existing python solution to C# to better understand job shop data modeling and improve my python skills. 

Solving a job shop problem quickly can enable real-time production schedule updates for reactive or proactive responses to disrupting factors. Machine level telemetry combined with cloud compute power can help business better predict future bottlenecks and maximize throughput if data and systems are well modeled/defined. Effective data modeling also helps standardize communication when connecting Cyber Physical Systems (CPS) to a Manufacturing Execution System (MES) enabling iterative ROI impacts while transitioning to Industry 4.0 insights and supporting parallel development of training supplemental machine learning algorithms to enhance existing planning and scheduling resources.

Google's OR-Tools is open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions. Let's take a look specifically at using OR-Tools to solve a JSP with the following constraints:

• A task must be completed before the next task in the job starts
• Only one task can be run on one machine at a time
• Once started a task must run to completion

We first need to describe the jobs as a sequential set of tasks consisting of machine and the amount of processing time required to complete.

Given the above problem set here is one possible solution

Then we find our bounds for the maximum makespan, machine count and define containers to hold the variables describing every task in a job.

After defining our task variables the following constraints must be added:

• Precedence constraints - All previous tasks in a job must be completed before the next can start
• No overlap constraints - A machine can only work on one task at a time

 Next we use the modeled data to define our objective -- find the shortest makespan or length of time between the start of the first task and completion of the last task. 

Finally we submit the model to Google's API and display the results. Which can be either an optimal schedule, multiple equal solutions or an unsolvable solution if invalid constraints are defined. In this example an improved solution resulting in a makespan of 11 vs 12 was found.

Businesses using LEAN, ANSI, ISA 95, domain driven design or any combination of process and data modeling can leverage modern free libraries to realize iterative returns during their Industry 4.0 transition while improving current production planning capabilities.

To view the full source check out JobShopController.CS in my public repo ported from Google's python solution.