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(save_tree=True)

sol = bnb.solve(problem, 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’.

If the attribute constructive is ‘neh’, the heuristic of Nawaz et al. (1983) is adopted, otherwise the strategy by Palmer (1965).

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

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)