Notice: Trying to get property of non-object in /var/www/examples/production-scheduling/index.php on line 49

Notice: Trying to get property of non-object in /var/www/examples/production-scheduling/index.php on line 78

Notice: Trying to get property of non-object in /var/www/examples/production-scheduling/index.php on line 92

Production scheduling

with piecewise-linear objectives and Gurobi

In this example we'll solve a simple production scheduling problem and demonstrate the use of piecewise-linear objectives in Gurobi.

We'll construct a mathematical model of the business problem, implement this model in Gurobi's Python interface, and compute and visualize an optimal solution.

Although your own business may not involve production scheduling, the same basic techniques used in this example can be used for many other applications.

Problem Description

Before presenting the example, we briefly review piecewise-linear functions. Piecewise-linear functions can be used to approximate arbitrary (nonlinear) functions. As an example, the function $\ f(x) = -(x - 2.5)^2 + \sin (kx) + 3$ and its piecewise-linear approximation are shown on the visualization below. You can vary the number of sample points $n$ and the parameter $k$ to see how the piecewise-linear approximation changes.

The function $f(x)$ is not convex. But $f(x)$ can still be minimized/maximized with Gurobi by invoking piecewise-linear objectives. The problem will be transformed to a MIP and solved. If $f(x)$ is convex, the model is directly solved as an LP.

Piecewise-linear objectives arise naturally in many different applications. In this example, we will see how piecewise-linear objectives are used to solve problems that include soft constraints.

We consider a pulp and paper factory which uses wood as a raw material to produce different types of paper, cardboard and pulp. Each product has a cost and can be produced at a certain rate. The goal is then to decide, given the demand, the amount of each item to produce to maximize the profit.

Implementation

Below is the full implementation of the model (and the associated data) in Gurobi's Python interface:

from gurobipy import * def cost(x, limithours, penalty): if x < limithours: return basecost else: return basecost + (x-limithours)*penalty # Example data rate = [50,40]; revenue = [25,32]; limit = [1200,920]; limithours = 20; maxhours = 40; penalty = 100; basecost = 500; n = len(rate) # number of products m = Model() # Add variables x = {} for i in range(n): x[i] = m.addVar(ub = limit[i], vtype=GRB.CONTINUOUS, name="x%d" % i) t = m.addVar(vtype=GRB.CONTINUOUS, name="t") m.update() # Add constraints m.addConstr(t == quicksum( x[j]/rate[j] for j in range(n))) m.addConstr(t <= maxhours) # Set objective m.setObjective( quicksum(revenue[i]*x[i] for i in range(n)), GRB.MAXIMIZE) # Set piecewise linear objective nPts = 101 ti = [] costi = [] lb = 0 ub = maxhours; for i in range(nPts): ti.append(lb + (ub - lb) * i / (nPts - 1)) costi.append(-cost(ti[i], limithours, penalty)) m.setPWLObj(t, ti, costi) m.optimize()

Live Demo

Below is a visualization of our problem.

Each product is represented by a circle, with the given production rate, revenue and production limit written below.

You can modify the piecewise-linear penalty function by dragging the points on the graph.

Click "Compute" to find the optimal production schedule. If a product is built, the circle representing it will be filled.