Machine Scheduling (LP)

Machine Scheduling (LP)#

This example is taken from Prof. J. E. Beasley’s OR Notes

Problem Statement#

A company makes two products (X and Y) using two machines (A and B). The objective is to maximize total inventory (stock) at the end of the week, given the following conditions:

Machining Time (in minutes)

Product ↓ / Machine →	A	B
X	50	30
Y	24	33

Initial Inventory and Demand (in units)

Product ↓	Stock	Demand
X	30	75
Y	90	95

Available Machine Time (in hours)

Machine ↓	Time
A	40
B	35

Initiate Elements#

First, declare the program

# !pip install gana # uncomment and run to install Gana, if not in environment
from gana import Prg, I, V, P, sup

p = Prg()

We will need two index sets (I): machines and products.

Note that A, B, X are reserved terms for generated matrices. So we are using lowercase for this example.

p.machines = I('a', 'b')
p.products = I('x', 'y')

Collections of elements, as opposed to ordered sets declared using I(size = n), set each element as a program attribute. Elements can also belong to multiple collection index sets. Refer to the ‘Indices’ tutorial for more information.

p.a, p.a.parent

(a, [machines])

The only variables we is production, indexed for each product. Unless explicitly specified, variables are non-negative and continuous, i.e.

\(v \in \mathbb{R}_{\geq 0}\)

p.prod = V(p.products, tag='Production (units)')

Using parameter (P) objects is optional. They do look better when printing complex programs.

Otherwise, Gana elements can be multiplied by lists or numbers directly

p.time = P(p.machines, p.products, _=[50, 24, 30, 33], tag='Processing time (minutes)')
p.tmax = P(p.machines, _=[40 * 60, 35 * 60], tag='Forecasted availability(minutes)')
p.demand = P(p.products, _=[75, 95], tag='Forecasted demand (units)')
p.stock = P(p.products, _=[30, 90], tag='Initial stock (units)')

.map for any element will reveal the mapping between indices and child elements

p.time.map

{(a, x): 50.0, (a, y): 24.0, (b, x): 30.0, (b, y): 33.0}

Writing Constraints#

Constraints can be writtent for:

Providing an upper bound on time used for each machine

Gana elements are generally illustrated using .show()

p.time_ub = (
    sum(p.time(p.machines, product) * p.prod(product) for product in p.products)
    <= p.tmax
)
p.time_ub.show()

\[\displaystyle [0]\text{ }{\mathrm{{\mathrm{time}}}}_{{machines},{x}} \cdot {\mathbf{{\mathbf{{\mathbf{prod}}}}}}_{{x}} + {\mathrm{{\mathrm{time}}}}_{{machines},{y}} \cdot {\mathbf{{\mathbf{{\mathbf{prod}}}}}}_{{y}} - {\mathrm{tmax}}_{{machines}} \leq 0\]

Ensuring that demand is met

.show(True) will illustrate the element at every index

p.demand_lb = p.prod >= p.demand - p.stock
p.demand_lb.show(True)

\[\displaystyle [2]\text{ }-{\mathbf{prod}}_{{x}} + 45.0 \leq 0\]

\[\displaystyle [3]\text{ }-{\mathbf{prod}}_{{y}} + 5.0 \leq 0\]

Setting the Objective(s)#

The objective is to maximize the sum of all products (A and B) in stock at the end of the week

p.max_stock = sup(sum(p.prod) + sum(p.stock) - sum(p.demand))

Illustrating the Program#

p.show(True)

Mathematical Program for prog

Index Sets

\[\displaystyle {machines} = \{ {{a}, {b}} \}\]

\[\displaystyle {products} = \{ {{x}, {y}} \}\]

Objective

\[\displaystyle min \hspace{0.2cm} -{\mathbf{prod}}_{{x}} - {\mathbf{prod}}_{{y}} + 50.0\]

s.t.

Inequality Constraints

\[\displaystyle [0]\text{ }50.0 \cdot {\mathbf{prod}}_{{x}} + 24.0 \cdot {\mathbf{prod}}_{{y}} - 2400.0 \leq 0\]

\[\displaystyle [1]\text{ }30.0 \cdot {\mathbf{prod}}_{{x}} + 33.0 \cdot {\mathbf{prod}}_{{y}} - 2100.0 \leq 0\]

\[\displaystyle [2]\text{ }-{\mathbf{prod}}_{{x}} + 45.0 \leq 0\]

\[\displaystyle [3]\text{ }-{\mathbf{prod}}_{{y}} + 5.0 \leq 0\]

Optimizing the Program#

For mixed integer programs (MIP), Gurobi is the default solver.

using can be used to specify a solver otherwise. Note that a .mps file is generated irrespective

p.opt()

📝  Generated prog.mps                                                       ⏱ 0.0004 s

Set parameter Username
Academic license - for non-commercial use only - expires 2026-08-01
Read MPS format model from file prog.mps
Reading time = 0.01 seconds
PROG: 4 rows, 2 columns, 6 nonzeros

📝  Generated gurobipy model. See .formulation                               ⏱ 0.0143 s

Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (win64 - Windows 11.0 (26100.2))

CPU model: 13th Gen Intel(R) Core(TM) i7-13700, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 24 logical processors, using up to 24 threads

Optimize a model with 4 rows, 2 columns and 6 nonzeros
Model fingerprint: 0xf7b401e1
Coefficient statistics:
  Matrix range     [1e+00, 5e+01]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [5e+00, 2e+03]
Presolve removed 4 rows and 2 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -5.1250000e+01   0.000000e+00   0.000000e+00      0s

Solved in 0 iterations and 0.00 seconds (0.00 work units)
Optimal objective -5.125000000e+01

📝  Generated Solution object for prog. See .solution                        ⏱ 0.0000 s
✅  prog optimized using gurobi. Display using .output()                     ⏱ 0.0202 s

Illustrating the Solution#

The overall solution can be viewed

p.output()

Solution for prog

Objective

\[\displaystyle min \hspace{0.2cm} -{\mathbf{prod}}_{{x}} - {\mathbf{prod}}_{{y}} + 50.0=-51.25\]

Variables

\[\displaystyle {\mathbf{prod}}_{{x}}=45.0\]

\[\displaystyle {\mathbf{prod}}_{{y}}=6.25\]

Solutions do each element can be viewed as well.

p.prod.output()