FJSP

 MS/OS Embedded Optimization with CMA-ES: A One-Page Concept Guide

---

🧠 Problem Setting: Flexible Job Shop Scheduling (FJSP)

• Objective: Minimize Cmax (makespan) of all jobs.

• Challenge: Jobs have multiple operations; each operation has multiple machine choices (MS), and scheduling order (OS) matters.

---

🌟 Embedding MS/OS into Continuous Space

• Key Idea: Convert combinatorial MS/OS decisions into a continuous domain [0,1] to enable CMA-ES to operate.

1. Machine Selection (MS):

• Each operation chooses a machine index via a normalized real value x ∈ [0,1].

• Decode: machine_idx = int(x * num_choices).

2. Operation Sequence (OS):

• Random keys in [0,1], sorted to determine execution order.

Final Individual Vector:

[MS_1, MS_2, ..., MS_n, OS_1, OS_2, ..., OS_n] ∈ [0,1]^{2n}

---

⚖️ CMA-ES Algorithm Flow

ask → evaluate → tell loop:

1. ask(): CMA samples multiple individuals (solutions) from a multivariate Gaussian θ = (m, σ, C).

2. evaluate(): Decode each individual into MS/OS choices, simulate the schedule, compute Cmax.

3. tell(): Update mean m, covariance C, and step size σ based on fitness ranking.

---

⚡ Key Enhancements

• Plateau Detection: Monitor history of best Cmax; if improvement stagnates, increase σ.

• Guided Local Search (optional):

  • Apply VNS on MS or OS of critical path.

  • Embed only when plateau is detected.

---

🔄 Nature of the Search Space

• [0,1] Continuous Domain:

  • MS/OS are embedded in a geometric manifold.

  • CMA-ES adapts the shape of its distribution to fit the underlying optimization landscape.

• Problem Density:

  • Mk01: low degree of freedom → higher σ needed.

  • Mk10: high flexibility → smaller σ leads to better convergence.

---

🔍 Objective Function

Let

J = Jobs, P = Processing Times, M = Machines
x ∈ [0,1]^{2n} ⇒ (MS, OS) ⇒ Schedule ⇒ Cmax

Minimize:

f(x) = Cmax(x) = max_{j ∈ J} C[j][-1]

---

📊 Summary

• CMA-ES can effectively solve FJSP by mapping discrete scheduling problems into a continuous optimization space.

• Embedding MS/OS decisions into [0,1] enables natural use of evolutionary strategies.

• Search guided by adaptive σ, critical path heuristics, and statistical adaptation.

---

Keywords: CMA-ES, MS/OS embedding, Random Key, Flexible Job Shop Scheduling, Evolutionary Optimization, Cmax, Plateau Escape, Gaussian Search.