Optimizing manufacturing production scheduling (MPS) using constraint programming

Production scheduling primarily deals with arranging different jobs in various machines based on the timelines for each job. There can be numerous combinations of schedules possible. Production schedules can be designed to maximize the capacity utilization, minimize idle time of the machine, earliness, overall costs etc. Manual design of a schedule can be a tedious and time consuming task. There are a lot of dependencies which the scheduler needs to tweak based on a single change. Generating a production schedule targeting a specific objective function can be done using mathematical models. Mathematical models involve formulating the production scheduling problem as an optimization model wherein there is a certain objective function which needs to be optimized based on a set of constraints. Mathematical models generally outperform manually designed schedules which involve a lot of inter-dependencies among the jobs. Due to improvement in computational power, developing a production schedule using mathematical models is relatively quick and efficient.

We partnered with a client who has multiple manufacturing facilities and requires production schedules for different sites. These production schedules are designed manually keeping in mind fluctuating demand, raw material availability and safety stock requirements. To alter an existing schedule, the schedule planner has to spend countless hours (approx 1-2 days) to make sure all the above requirements are met. Using mathematical models, this process can be automated and a schedule can be generated within a few minutes resulting in significant time saving. The requirements for each site were vastly different. Thus, the solution for each site needed to be tailored accordingly to generate the desired outcome.

Optimization deals with finding the best solution among a large set of possible solutions. Following are the common kinds of optimization problems.

An optimization problem is formulated as a mathematical model that typically consists of an objective function and a set of constraints. The constraints are a set of rules which must be followed. An objective function helps the model to choose the best solution among the possible solutions. The solution from a model can either be feasible, optimal or infeasible. A feasible solution is one which satisfies all the constraints. An optimal solution is one which is feasible and yields the best (maximum or minimum) value of the objective function.

Optimization problems can be solved using the following

2.1. Optimization problem examples

Toy example

Maximize 3x + 4y for the following set of constraints

Optimal solution is found by traversing through the boundaries of the feasible region. The optimal solution to the problem is as follows:

x = 6, y = 4, Objective function value = 34

2.2. Job sequencing problem

Problem statement

3 Jobs need to be processed in a single machine. The processing time and the due dates (in days) for each job are given in the following table. The due dates are measured from zero, the assumed start time of the first job.

Job	Processing time (day)	Due date (day)	Late penalty
1	5	25	19
2	20	22	12
3	15	35	34

The objective is to determine the job sequence that minimizes the late penalty for processing all jobs

Definition

Objective function

Constraints

1. Noninterference/No Overlap Constraints (Two jobs cannot be processed concurrently)

2. Due date constraints

The optimal solution to the problem is as follows:

Job 2 starts at 0, Job 1 starts at 20 and Job 3 starts at 25. The job sequence is 2-1-3. Completion of Job 2, 1 & 3 are 20, 25 and 40 respectively. Job 3 is getting delayed by 5 days.

Production scheduling problems are typically formulated as a mixed integer linear programming (MILP) problem.

3.1. Terminologies in a MILP model

Linear programming refers to an optimization method where the constraints are having linear relationships. The decision variables in MILP can be integer or continuous.

In the case of the Client, the production schedules were required for two sites namely Site A and Site B. Each site had different processes, constraints and ways of designing the schedule. Batch production was employed in both the sites. Each batch went through various processes/stages until completion. Both the schedules were to be optimized for maximizing the capacity utilization.

For each of the sites, all the above requirements were modeled mathematically in terms of linear relationships. The primary objective was to achieve high capacity utilization for both the sites. In the optimization model this was achieved by reducing the makespan.

The optimization model generates the sequence of batches and the start and end dates for each process of different batches. This output can be visualized in a Gantt chart.

Constraint programming is an approach similar to mathematical programming which aims to arrive at a solution rapidly given the constraints and objective function. A constraint programming model can provide multiple solutions.

There are several frameworks available for modeling a constraint programming problem. Some of them are Google Optimization Tools (OR-Tools), Pyomo, PuLP and gurobipy (Gurobi Optimization).

OR-Tools is an open source software with excellent documentation and top notch performance. The OR-Tools framework has a solver named CP-SAT Solver which transforms the constraints into clauses and finds values for decision variables. The typical steps in a constraint programming model are as follows.

The CP-SAT Solver is the critical engine for finding solutions to a model. The CP-SAT solver can give a quick feasible solution or optimal solution based on the time limit specified. Finding an optimal solution usually takes longer than a feasible solution. CP-SAT can easily scale for large problems and deduce solutions despite the complexities.

5.2. Site B mathematical model formulation

Problem statement

Each batch goes through various processes/stages during its manufacturing. For each stage, there are specific machines which can be assigned. The scheduling of the batches is dependent on the bottleneck processes. For each batch, once the bottleneck processes are scheduled through optimization, the non-bottleneck process dates can be computed through trivial calculation.

Cell manufacturing is employed at the site. Below figure shows the layout

In the main cell, there are three kinds of machine types namely M1, M2 and M3. Apart from the main cell there are 4 special cells namely P, Q, R and S. The special cells contain two types of special purpose machines namely SP1 and SP2. Below table shows the counts of machines in the site.

Each batch goes through the main cell followed by any one of the special cells. Typically the sequence of machine types/processes for a batch is M1, M2, M3, SP1 and SP2. For some batches, some of the machine types in between are not required. There are 4 M1 machines in the Main Cell. Out of 4 any 1 machine would be utilized for processing of the batch. Once a batch is assigned a particular special cell, SP1 and SP2 processing would happen in the same cell. Batches will not move across special cells during their production.

The schedule for this site is divided into two steps. In the first step, for each batch for each process the machine assigned would be deduced. In the second step, the scheduling of the batches would happen. Thus there would be two models namely Machine Assignment Model and Batch Scheduling Model.

Dashboard application for site B