Scheduling optimization in blending plants
Combining Constraints Programming and Machine Learning for scheduling optimization in blending plants.
Constraint Programming (CP) is an efficient technique for solving combinatorial optimization problems and is mainly built of three pillars: modeling, search, and optimization. One of the decisive challenges for combinatorial optimization researchers when solving real-world problems is designing and implementing high-quality heuristics to guide a constraint model’s search process finding the best solution, making Machine Learning particularly relevant in this part.
Machine Learning (ML) has gained a large following in recent years and has tremendous success transforming many businesses. ML and CP have developed mostly independently from each other; this article will give a brief introduction on how ML can help ease the journey of modeling and solving CP tasks in a real-world problem: which is scheduling in blending plants.
Blending is a product mixing optimization problem typically encountered in the oil industry, where base oils and intermediate additives are blended to obtain various lubricants.
A blending plant is essentially composed of :
- Base oil supply: Base oils are used to manufacture products, including lubricating greases, motor oil, and metal processing fluids.
- Additive tank farm: tanks in which the additives are stored.
- Blending kettles: base oils and additives are mixed in these kettles to produce the final lubricant. Different capacities are made according to the customer’s needs.
- Laboratory: where lubricants manufactured are analyzed to verify compliance with several chemical constraints.
- Finished product tank farm: the tanks to which the oil flows after being blended in the kettle.
- Packaging: In this step, the finished lubricants are stored in canisters or storage tanks.
- Truck Loading and Unloading.
Understanding the problem
Scheduling is an arduous and ubiquitous task in a wide range of real-world contexts, which requires consideration of several constraints and limitations.
Scheduling problems arise in practically all situations where performing a given set of actions or operations requires allocating resources and time slots subject to specific feasibility and optimization rules.
Solving scheduling problems in blending plants is often challenging because resources are usually scarce, and complex dependencies may exist between different tasks. The number of options grows exponentially with the number of lubricants to produce, making solving intractable for broader problems.
Daily, a blending plant produces a certain number of lubricants based on customer demands. The blending tasks must be divided among the blenders and performed sequentially because the plant has a limited number of blenders that can handle all the needs. Each blending job can take several hours, and the final product is analyzed in the laboratory before being packaged. If the product is not in compliance, time-consuming adjustments are required in the best cases; otherwise, the product is rejected, hence the interest in having the best product succession.
In practice, lubricant plants have a list of particular products that should not be made sequentially and other products that can be followed with an intermediate rinse to avoid contamination and lab adjustments. However, these lists are not exhaustive and may need to be modified and adapted. To deal with these difficulties, we have built a machine learning model that gives a probability of success of a blending task considering its chemical composition and characteristics and considering the previous lubricant compositions produced in the same blender. These probabilities are then passed to a constraint optimization algorithm that generates a schedule that respects the blending plant constraints and maximizes successful blending chances.
Scheduling proposition using constraints programming framework
There are several frameworks for constraint resolution. Google Optimization Tools (OR-Tools) is an open-source software suite for solving combinatorial optimization problems. Our problem was modeled using this framework in Python.
The OR-Tools framework has a constraint programming solver named CP-SAT Solver; it transforms constraints into clauses and then uses the solver to find values that give a feasible solution.
A constraint programming problem can be designed and solved with OR-tools mainly using three steps that will be detailed next in this article:
- Defining variables and initiating the model.
- Listing and adding the constraints.
- Running the solver.
Defining variables
A constraint satisfaction problem is represented by a finite set of variables, each ranging over specific domains and satisfying a finite number of constraints that restrict the allowed combination of values. A candidate solution is any assignment of variables to values. We say that a solution is feasible when it satisfies all the constraints.
Below are the principal variables used to define the problem.
- Let B represents blenders.
- Let O be the set of blending orders.
- Let D be the set of finished lubricants.
Assume that a blending presence is represented by :
The presence variable represents a boolean variable equal to 1 if the order o is produced in blender b.
- Let S be the set of blend starting times and E be the set of blend ending times.
- Finally, let I represents the set of scheduling intervals :
CP-SAT has specific variables that give shortcut code for representing time intervals.
model.NewIntervalVar(start, duration, end, name)model.NewOptionalIntervalVar(start, duration, presence,end, name)
An interval variable is a decision variable that represents a task with unknown start and end times. CP-SAT handles optional interval variables associated with a Boolean status depending on their presence or absence.
Each interval is associated with a starting time (s), ending time (e), and a blending task presence (p). These parameters can be constants or variables.
All possibles interval variables are created (copies in each blender for each task), and only intervals that satisfy constraints will be activated. For this purpose, optional intervals (NewOptionalIntervalVar) have been used instead of standard intervals (NewIntervalVar) where presence is mandatory.
To identify the intervals that the solver activates, master start and master end variables are created and linked with local start and local end variables.
When an interval is activated (presence = 1), the local start and local end variables’ values are assigned to the master variables.
constraint.OnlyEnforceIf(bool_var) means bool_var ⇒ constraintBelow are python variables used to model the problem.
To associate each order with a blender and define starting and ending times, we need to find values of variables that respect all the defined constraints.
Listing and modeling the constraints
A constraint is a rule that limits which feasible solutions are acceptable. CP-Solver can only handle integer constraints. Therefore, all constraints must be written as an integer equation. Two types of constraints can be modeled in the CP model, hard and soft constraints. All of them must be satisfied to find an optimal solution.
Hard constraints
Any feasible solution to the model must respect this type of constraint. They are vital, and the problem is unsolvable if they are not respected.
Below are hard constraints modeled in the blending scheduler use case:
▹. Constraint 1: A blending order is carried out in only one container
▹. Constraint 2: Some orders can be carried out by specifics blenders (colored or sensitive lubricant).
These two constraints are expressed in this way :
▹. The last lubricant produced must be placed first in each blender's schedule. The solver is forced to propose a compatible task with what is already done.
This constraint is defined during the variable definition phase.
▹. Constraint 3: Blending intervals must not overlap means that the end time of a task must be anterior from the next one's starting time. Thus making, a tank will not simultaneously produce two blending tasks.
To model this with OR-Tools, the NoOverlap constraint is used. It takes as input a list of interval variables and states that all intervals performed by the same blender are disjoint and cannot overlap in time.
▹. Constraint 4: Some commands have to be processed before others. The algorithm has to respect order priorities.
Soft constraints
Soft constraints are not essential to find a feasible solution. They are highly desired; the CP model should try to satisfy them as much as possible, knowing that violating a constraint incurs a penalty in the objective function.
Whereas hard constraints are added to the model using the Add function and modeled as equalities or inequalities, soft constraints are added to an objective function to maximize or minimize.
All the following constraints are conditioned by a literal (l) that will indicate if the succession is active or not.
A literal is modeled as a boolean variable in this manner :
l = self._model.NewBoolVar(“%i before %i” % (i, j))A Boolean variable is an integer variable compelled to be either 0 or 1. Hence, a literal is either a Boolean variable or its negation.
▹. Constraint 5: Maximize the probabilities of blends success given by the ML model.
A classification algorithm has been trained on lubricant blends' history to predict the probability of the production's success, considering the previous production made in the same tank.
For each past fabrication, we have:
- The chemical composition and characteristics and the same features concerning the lubricant produced before in the same blender.
- The result of the laboratory analysis, used as a target.
The function proba(i,j) will return the success probability of lubricant (j) knowing that (i) was blended before.
▹. Constraint 6: Minimize rinsings between productions.
The function rinse(i,j) gives us the penalty if rinsing is required between order (i) and (j).
Constraints 5 and 6 are modeled using a circuit constraint represented by a complete weighted graph that uses ML probabilities and rinses penalties as weight.
A circuit is represented by a set of arcs; each arc is linked to a given literal, indicating if it is selected. When the literal is true, the arc is part of the circuit. The circuit constraint serves to constrain the graph represented by a successor for each node so that the resulting edges form a Hamiltonian circuit.
Hamiltonian circuit is a circuit that visits every vertex once with no repeats. A Hamiltonian path also visits every vertex once with no repeats, but does not have to start and end at the same vertex.
A hard constraint is added to the model to force the presence of order (i) and (j) if lit is True.
self._model.AddImplication(
lit,
self._blender_presences[transition_ids[i]][d]
)self._model.AddImplication(
lit,
self._blender_presences[transition_ids[j]][d]
)
Since we have defined blends as optional tasks (depends on presence variable p), we need to add a self-looping arc on the node that corresponds to this arc.
When the variable (p) is equal to false, the corresponding task is not scheduled. This information needs to be communicated with the circuit constraint to tell it that the hamiltonian path should not visit the node.
# presence of task i in blender d is represented by p(i,d)
# p(i,d) = self._blender_presences[transition_ids[i]][d]arcs.append([i + 1, i + 1,self._blender_presences[transition_ids[i]][d].Not()])
Because a cycle is needed to form a hamiltonian path, a dummy node is added. It represents the start and the end of the schedule. Outgoing arcs indicate which task is first, and incoming arcs indicate which task is last.
# Initial arc from the dummy node (0) to a task.start_lit = self._model.NewBoolVar(“%i” % d)arcs.append([0, i + 1, start_lit])arc_literals.append(start_lit)# Final arc from an arc to the dummy node.end_lit = self._model.NewBoolVar(“%i” % d)arcs.append([i + 1, 0, end_lit])
Optimization
A schedule is optimal if it :
- Minimize the number of rinsings between tasks.
- Maximize the probability of success between jobs.
- Minimize task completion time.
To optimize the overall end time, a makespan variable is defined and linked to the end variables as follows:
ending_time_objective = self._model.NewIntVar(0, self._horizon, “makespan”)self._model.AddMaxEquality(ending_time_objective, self._end_blends)
The makespan is the duration between the start of the first job across all blenders and the end of the last job.
Currently, in OR-tools, the model can optimize only one objective function. Therefore, all soft constraints are weighted and reduced into a single objective:
to_optimize = []to_optimize.append(LinearExpr.Sum(self._scal_prods_weights))to_optimize.append(LinearExpr.Sum(self._scal_prods_ml))to_optimize.append(ending_time_objective)self._model.Minimize(LinearExpr.Sum(to_optimize))
Solver
The CP solver is the main engine for solving a problem instance. It has a very comprehensive application programming interface and offers many features.
Once all variables are defined, and all constraints are added to the model, we can run the solver. It can run in parallel mode to speed up the processing time by specifying the number of workers in its parameters. The solver will try to find the optimal solution within a given time limit. Finding an optimal solution can take far longer than finding a feasible solution. The search process can be interrupted early with Ctrl+C or max_time_in_seconds parameter. We can also print the intermediate objective value and solutions using a custom solution callback called each time any new feasible solution is found and decide if it is good enough.
self._solver = CpSolver()
self._solver.parameters.max_time_in_seconds = 10 * 60
self._solver.parameters.log_search_progress = True
self._solver.parameters.num_search_workers = 8
self._solver.SolveWithSolutionCallback(self._model,self._solution_printer)In this article, we have demonstrated the potential of Machine Learning to generate accurate heuristics that help a constraint model search process finding an optimal schedule for blending plants using the power of the Google OR tools library. I hope you found this fleeting enlightenment helpful in showing you how we solved a real-world problem using constraint programming and machine learning. Leave your comments/suggestions in the replies!
