Permutation Flow-Shop

This is a variant of the Flow-shop scheduling problem (FSSP) in which the sequence of jobs is the same in every machine.

\[\begin{split}\begin{aligned} \text{min} \quad & C_{\text{max}} \\ \text{s.t.} \quad & h_{m-1,k} + \sum_{j \in J} p_{j,m-1} x_{j,k} \leq h_{m,k} & \forall ~ m \in M \setminus \{1\}; k \in K\\ & h_{m,k} + \sum_{j \in J} p_{j,m} x_{j,k} \leq h_{m,k+1} & \forall ~ m \in M; k \in K \setminus \{|K|\}\\ & \sum_{j \in J} x_{j,k} = 1 & \forall ~ k \in K\\ & \sum_{k \in K} x_{j,k} = 1 & \forall ~ j \in J\\ & h_{|M|,|K|} + \sum_{j \in J} p_{j,|M|} x_{j,|K|} \leq C_{\text{max}}\\ & h_{m,k} \geq 0 & \forall ~ m \in M; k \in K\\ & x_{j,k} \in \{0, 1\} & \forall ~ j \in J; k \in K\\ \end{aligned}\end{split}\]

In this example it is not written from scratch, but simply makes use of a very efficient implementation available together with bnbpy in the auxiliary module bnbprob.

You can compare this implementation to MILP solvers at the end of the notebook.

from bnbprob.pafssp import LazyBnB, PermFlowShop, plot_gantt
from bnbpy import plot_tree

Simple Problem

p = [
    [5, 9, 7, 4],
    [9, 3, 3, 8],
    [8, 10, 5, 6],
    [1, 8, 6, 2]
]

problem = PermFlowShop.from_p(p)
bnb = LazyBnB(problem, save_tree=True)

sol = bnb.solve(maxiter=50000)
print(sol)

Status: OPTIMAL | Cost: 43.0 | LB: 43.0

plot_gantt(sol.problem.sequence, dpi=120, seed=42, figsize=[8, 3])

plot_tree(bnb.root, figsize=[8, 8], font_size=10)

In this implmentation lower bounds are computed by the max of a single machine and a two machine relaxations.

The bounds for single and two-machine problems are described by Potts (1980), also implemented by Ladhari & Haouari (2005), therein described as ‘LB1’ and ‘LB5’.

The constructive attribute selects the warmstart strategy: ‘neh’ uses Nawaz et al. (1983), ‘quick’ uses the slope-sorting heuristic by Palmer (1965), ‘multistart’ applies randomized multi-iteration NEH, and ‘iga’ uses the Iterated Greedy Algorithm by Ruiz & Stützle (2007).

References

Ladhari, T., & Haouari, M. (2005). A computational study of the permutation flow shop problem based on a tight lower bound. Computers & Operations Research, 32(7), 1831-1847.

Nawaz, M., Enscore Jr, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.

Potts, C. N. (1980). An adaptive branching rule for the permutation flow-shop problem. European Journal of Operational Research, 5(1), 19-25.

Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Journal of the Operational Research Society, 16(1), 101-107.

Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033-2049.

Bonus - MILP Model

This is the usual Position-based MILP model as an alternative to compare performance.

import pyomo.environ as pyo

from bnbprob.pafssp.mip import positional_model

model = positional_model(p)


# HiGHS
solver = pyo.SolverFactory("appsi_highs")
solver.options["mip_heuristic_effort"] = 0.1
solver.options["time_limit"] = 120
solver.options["log_file"] = "Highs.log"
solver.solve(model, tee=True)

# Gurobi
solver = pyo.SolverFactory("gurobi", solver_io="python")
solver.options["Heuristics"] = 0.2
solver.options["Cuts"] = 2
solver.options["TimeLimit"] = 120
solver.solve(model, tee=True)