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.

The factory can only run for a limited number of hours. To model this, we could add a hard constraint. For example, limiting the number of work hours in a week to 50. In reality, it is often the case that we can go beyond the time limit, but only if we pay overtime costs. So if 55 hours of work were done in a week, the first 50 would incur no extra cost, but we would pay a penalty of 100 $/hour for the final 5 hours. This is a soft constraint, because it can be violated if a penalty is payed.

Piecewise-linear objectives also arise in other contexts, for example in modelling reversible activites, piecewise-linear costs, approximating nonlinear functions, and many more.

Mathematical Model

Let us now describe a mathematical model for our problem. Let $P$ be the set of products the factory produces (e.g. different types of paper, cardboard, etc.). With each product $i$ we associate the constants:

  • $p_i$: the production rate in tons per hour.
  • $r_i$: the revenue per ton of product.
  • $l_i$: the maximum limit of product, in tons, that can be produced.

We define a continuous variable $x_i$ that is the amount of product $i$ we produce. The revenue is then given by: \[ \ \text{revenue} = \sum_{i \in P} r_i x_i. \]

Since the amount of each product we produce must be nonnegative, and we cannot exceed the maximum limit of each product that produced, we have the following constraints: \[ \ 0 \leq x_i \leq l_i, \quad \forall i \in P \]

Furthermore, there is a limit on the amount of time the factory can run. We denote this by $t_{\mathrm{lim}}$. Since $x_i$ tons of product $i$ is produced at a rate of $p_i$ tons per hour, the total amount of working time is given by: \[ \ \text{time} = \sum_{i \in P} \frac{x_i}{p_i}. \] Here we assume that the factory is only able to produce one product at a time.

To impose the time limit we could constrain the working time to be less than the time limit $t_{\mathrm{lim}}$. However, as mentioned before, we can run the factory beyond the time limit if we pay for overtime. Overtime work is more expensive, so we introduce a penalty cost of $c$ dollars per hour, in addition to the usual costs.

Therefore, if the factory runs for less than $t_{\mathrm{lim}}$ hours, we pay the base cost $b$, but if it goes beyond, we pay a penalty for the extra hours. This can be represented by a piecewise-linear cost function of time: \[ \ \text{cost}(t) = \left\{\begin{array}{ll} b & \text{if } t \leq t_{\mathrm{lim}} \\ b + c(t-t_{\mathrm{lim}}) & \text{if } t > t_{\mathrm{lim}} \end{array}\right. \]

To incorporate the overtime penalty in our model, we introduce a variable $t$ for time \[ \ t = \sum_{i \in P} \frac{x_i}{p_i}. \] The pulp and paper factory's profit is given by: \[ \ \text{profit} = \text{revenue} - \text{cost} = \sum_{i \in P} r_i x_i - \text{cost}(t). \]

Since we may want to limit the hours of overtime, we add a final constraint \[ \ t \leq t_{max}, \] where $t_{max}$ is the maximum amount of work hours.

Thus, the production planning model for the pulp and paper factory is \[ \begin{array}{ll} \text{maximize} & {\displaystyle \sum_{i \in P} r_i x_i - \text{cost}(t)} \\ \text{subject to} & {\displaystyle t = \sum_{i \in P} \frac{x_i}{p_i}}, \\ & 0 \leq x_i \leq l_i \quad \forall i \in P, \\ & t \leq t_{max}, \end{array} \] where the $\mathrm{cost(t)}$ term in the objective is a piecewise-linear function.

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.

Try Gurobi for Free

We hope this example has taught you a bit about production scheduling, piecewise-linear objectives, and using Gurobi. We encourage you to try the example out for yourself with Gurobi. To enable this, we provide easy access to a full-featured evaluation version of Gurobi.

We are always happy to discuss your needs and answer your questions. Just contact us at your convenience.