Applications of Annealing
to Production Planning
Optimization
Zac Bre nnan, Jose ph David, Ke mal Azie z Rachmansyah, Rikuto Shige miIndustrial Me ntor: Dr. Ryoji Miyazaki
Acade mic Me ntor: Dr. Yuki IriePresentation Outline
1. Introduction
a. The scheduling problem
b. Our goals
2. Simulated Annealing & Job Shop Scheduling Formulation
3. Variations of Simulated Annealinga. Vector Annealing, External Constraints, Variable Pruning
4. Results
5. Observations on Quantum Annealing

Part 1Introduction

Increasing complexity from manufacturing● Mass manufacturing on asse mbly line s is low comple xity sche duling● Jobs have ide ntical production re quire me nts
08:00

09:00

10:00

Machine 1

Machine 2

Machine 3

Machine 4

Machine 5

Note: all these jobs are to create the same product

11:00

12:00

13:00

Increasing complexity from manufacturing● High-mix low-volume production incre ase s varie ty of manufacturing re quire me nts● Advance me nts in ge ne ral-purpose manufacturing such as industrial 3D Printing, lase r
cutting, and CNC le ads to more multi-purpose manufacturing machine s
08:00

09:00

10:00

11:00

12:00

13:00

Machine 1

Machine 2

Machine 3

Machine 4● Consolidation of machines and non-linear manufacturing dramatically increase complexity

Production Planning - The Job Shop Proble m● Sche duling proble m whe re multiple jobs are proce sse d on multiple machine swith ce rtain ope rational pre ce de nce rule s● Minimize makespan, the total sche dule le ngth
https://developers.google.com/optimization/scheduling/job_shop under CCA 4.0 License

Job 0: Operations 0, 1, and 2
Job 1: Operations 0, 1, and 2
Job 2: Operations 0 and 1

Our Project - Background● Simulated Annealing is a promising me thod of solving the se type s ofcombinatorial optimization proble ms○

Particularly for a “good e nough” solution, whe re ne ar-optimal solutions are acce ptable

Compute rs● NEC has de ve lope d the ir own anne aling me thods for the ir supe rcompute r SXAurora TSUBASA● D-Wave Quantum Anne aling has re ce ntly be e n made comme rcially available

Overview of the annealing process
Time for proce ss012322021214124

3Pre -proce ssJobMachine Assignme ntInput jobs
De fine constraints
Compile into QUBO

Ope ration

Anne aling
Valid sche dule

Our Project - Goals● Unde rstand the size and scope of proble ms curre ntly fe asible on SX-Auroraand D-Wave Syste ms, and whe the r it can handle suitably comple x proble ms● Compare the pe rformance of SX-Aurora TSUBASA to D-Wave and classicalsimulate d anne aling in cre ating production sche dule s● Conside r modifications of standard anne aling algorithms to improve e fficie ncy
on standard combinatorial proble ms such as Job Shop Sche dulingPart 2Simulated Annealing &JSSP Formulation

Simulated Annealing (SA)S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi (1983)● Optimization Me thod, inspire d by Anne aling proce ss in Me tallurgy○He at the mate rial ➔ Re crystallize ➔ Slowly cool it down

● Have a chance to go up base d on cost (e ne rgy) diffe re nce and te mpe rature .
● SA take sample s from the whole space , so it could e scape local minimums.

cost

https://www.smapip.is.tohoku.ac.jp/

combinations●If●IfJob Shop Scheduling Problem Formulation● De fine se t of binary variable s, whe re N isthe total # of operations and T is timespan .

https://developers.google.com/optimization/scheduling/job_shop under CCA 4.0 License

Problem Formulation: Constraints● Include as cost rathe r than re strict se arch space .
● Example : One -hot constraint○As a mathe matical e xpre ssion inMore Constraints : Orde r, Ove rlap, De adline

Constraints

Test Cases: Number of Variables, Constraints
Problem6x67x710x5 10x106x67x710x510x10# of Var23403675

3750 11500

3060

6125

5000

14500

Baseline

ComplexOne Hot

Overlap

OrderBaseline

XX

X

Complex

XXX

Trans.

DeadlineXX

Time To Solution - How to measure performance● Balance runtime with solution quality○ TTS is e xpe cte d amount of time to re turn a ne ar optimal re sult
○ t = the le ngth of a single anne aling ite ration○ R = the numbe r of anne aling ite rations to ge t a good solution
with probability pd = .99○ ps ( t ) = Probability of a valid sche dule with single run of le ngth t

Part 3
Variations ofSimulated AnnealingVector Annealing● Simulate d Anne aling done on Ve ctor Machine ssuch as SX-Aurora Tsubasa made by NEC.

● SX-Aurora Tsubasa can proce ss one -dime nsional
array of data (ve ctors) e ffe ctive ly and e fficie ntly.
○ Paralle l ope rations● Ve ctor Anne aling inspire d our classical simulate danne aling modifications, such as…
https://www.nec.com/en/global/solutions/hpc/sx/vector_engine.html

SA Modification

Cost Function

workAnnealing

1. External Constraint[M. Kumagai, K. Komatsu, F. Takano, T. Araki, M. Sato, H. Kobayashi(2021)]○○○

Move a constraint outside the cost function.
Afte r e ve ry swe e p, “bad configurations” are swappe d
Limit the se arch space according to the constraints.

2. Variable Pruning[D. Ve nture lli, D.J.J. Marchand, G. Rojo (20 15)]○○

Some variable s are guarante e d to be ze ro.
We de le te those variable s from the cost function.

The cost function is simpler ➔ Less coefficients to balance!
The search space is smaller ➔ Faster and more accurate result!
https://www.smapip.is.tohoku.ac.jp/

Variable Pruning

Number of Pruned Variables:Our Tools
SimulatedAnnealing(neal)

Simulated Annealing with
External Constraints(Modified neal / nealmod)

VectorAnnealing(VA)

Quantum
Annealing(QA)

We can use Variable Pruning in all of these tools
MachinePersonalComputer,
Vector Machine

Personal Computer,
Vector Machine

Vector Machine

Quantum Annealer

PythonPackagedwave-neal

Modified dwave-neal

VectorAnnealing(exclusive to SXAurora)

dwave-system

Part 4

Simulated Annealing
Results

External Constraints: neal vs nealmod
6x6StandardFormulation

External Constraints: neal vs nealmod
Standard
Formulation

Time to Solution Example: 10x10 Vector Annealing

Standard
Formulation

Time to Solution Example: 10x10 Vector Annealing
Complex
Formulation

Standard
Formulation
Average TTS Reduction of 5%

Complex
Formulation

11.3%

26.8%
10.3%

32%

Preparation Time and Results

10x10

Simulated Annealing Summary● Ve ctor Anne aling outpe rforms classical Simulate d Anne aling○ Large r and more comple x proble ms● Variable Pruning has significant be ne fits
○ Multi-function machine e nvironme nts● Ge ne ralization of Exte rnal Constraint me thods● Ve ctor Anne aling can solve a JSSP with up to 15,0 0 0 variable s in are asonable time (unde r one minute ).

Part 5Observations on
Quantum AnnealingQuantum Annealing: How It Works● Variable are re pre se nte d by qubits .
● Qubits have a 50 %-50 % chance to e nd up having value 0 or 1 at the e nd ofanne aling.
● We can change the probability according to the cost function.

Graph Embedding● If we have a te rm, we must conne ct those two qubits.
● Two qubits are not always conne cte d.

Proble m graph

Embe dde d graph● Some time s we ne e d a chain of qubits to re pre se nt one variable .

QA Capabilities
More Variables

More and Longer Chains
320 qubits#Qubits ≠ #Variables
3909 qubits

3909 qubits(out of 5616)
Embedding time: ∼11s

Embedding time: ∼388s

Graph Embedding Time

Input jobs
De fine constraints
In our PC(All problems are complete graphs)

Compile into QUBO

D-Wave ’s
Compute rGraph Embe dding

D-Wave ’s
QuantumAnne ale r

Quantum Anne aling

Valid sche dule

Problem Dependency● QA is be tte r on solving ce rtain proble ms.
● For e xample , Numbe r Partitioning Proble m.

positive inte ge r

With same number of variables,QA solves Number Partitioning Problem reliably,
but QA rarely gives an optimal solution for Job Shop Scheduling Problem.

Optimal Solution Percentage● Proble m matrix and graph comple xity doe sn’t se e m to corre late with QA’s e ffe ctive ne ss.
●We suspe ct that Numbe r Partitioning Proble m have many optimal solutions.

Experiment with, total number of solutions:, forNumberPartitioning
Problem

Job Shop
Scheduling
ProblemNumber of OptimalSolutions

3356

1212376

Optimal Solution
Percentage

5.1208%0.018%

18.884%

Success Rate to Find
Optimal Solution

8.58%

0.03%

62.95%

CustomProblem Matrix

runsSmall Problem Comparison
Comparison for 2x2 Job Shop Scheduling Problem, with 16 variables
neal

Modified neal

VA

VA with
Variable
Pruning

AverageAnnealingTime

0.0011189s

0.0010309s

0.281s

0.179s

0.002sSuccess
Rate to Find
OptimalSolution

97%

99%

100%

100%

0.03%

TTS

0.001469s

0.0010309s

0.281s

0.179s30.696sQA

QA Summary
Although Quantum Annealing is very fast,● Quantum Anne aling can only solve small proble ms.
● Quantum Anne aling can give optimal solution to proble m with many optimalsolutions.
Compared to other annealing method,
Quantum Annealing is not suitable for solving Job Shop Scheduling Problem
To improve that, we think Quantum Anne ale r ne e ds:● More conne ctions be twe e n qubits. (rathe r than more qubits)● Faste r graph e mbe dding algorithm.
● Be tte r anne aling sche dule to re ach optimal solutions re liably.

Final Conclusions● Ve ctor Anne aling can solve a JSSP with up to 15,0 0 0 variable s in are asonable time (unde r one minute ).
● Variable Pruning has significant be ne fits with multi-purpose
manufacturing machine s● Exte rnal Constraints is applicable to classical SA● Due to scale and inaccuracy, Quantum Anne aling is not curre ntly
suitable for solving Job Shop Sche duling proble ms.

Thank You!
ご清聴ありがとうございました。