Data centric approach for supply
chain optimization
Tatsushi Nishi
Associate Professor
Osaka University

Research Talk, March 6, EWO seminar, Carnegie Mellon University

1Outline of this talkResearch Introduction
 Cell-based heuristic algorithm for Capacitated
Multi-commodity Network Design Problem
 Simultaneous Optimization of ProductConfiguration and Supply Chain Planning
Considering Customer's Participationin Product Design
 Machine Learning Approach Identification of
objective function for Scheduling Problems
Research Talk, March 6, EWO seminar, Carnegie Mellon University

2

Introduction to Osaka University
Mathematical Science for Social Systems
Department of Systems Innovation
Graduate School of Engineering Science
Osaka University

bachelor students: 15,358
master students : 4,691
doctor students : 3,165
Total students : 23,214
International students: 2,480
Professors
Associate Prof.
Assistant Prof.

: 942: 1014: 1151

Non-academic staff : 3113
Total staffs: 6,654

3 main campus•Toyonaka campus•Suita campus•Minoo campus
Research Talk, March 6, EWO seminar, Carnegie Mellon University

3

Introduction of Engineering Science
School of Engineering
School of Science
School of Engineering Science
More basic than Engineering

Toyonaka campus (450000m2) Mathematical Science Department
・Finance and Insurance
・Data Science
・Mathematical Model
System Mathematics Research Group

Center for Mathematical Modeling
And Data Science, Osaka University
Research Talk, March 6, EWO seminar, Carnegie Mellon University

4

Brief Introduction: Associate Prof. Tatsushi Nishi
PhD Degree in Kyoto University (Chemical Engineering)
Assistant Professor of Okayama University (Electrical Engineering)
Associate Professor of Osaka University from 2006 (Mathematical Science forSocial Systems)
March 2014-2017, Visiting Professor of Beijing University of Chemical Technology
June-Sept 2015, Visiting Professor of University of Hamburg, Germany

Research areas: system optimization, automation, supply chain
planning and scheduling, combinatorial optimization,
multi-robot control, public transport, process systems engineering
Courses taught: discrete optimization, graph theory
operations research, intelligent mathematical programming
Associate Editor of IEEE Transactions on Automation Science and Engineering 2012(Impact factor: 2.428 (2015), 2.162 (2014), 3.667 (2017))
Conference Editorial Board of IEEE ICRA (top robotics conference)

Research Talk, March 6, EWO seminar, Carnegie Mellon University

5Our team・Scheduling
public transport, railway crew scheduling, airline schedulingtransportation, routing, logistics, production scheduling・Supply chain optimization
production planning, supplier selection, revenue management,
contract decision, quantity discounts or volume discounts

・Discrete event systems
Petri nets, timed automata, modeling, optimization, automated guided
vehicles, deadlock avoidance, Petri net decomposition techniqueResearch Talk, March 6, EWO seminar, Carnegie Mellon University

6Collaboration with industries• Semiconductor factory automation
Control of automated guided vehicles for transportation
Scheduling of cluster tool for silicon wafer production• Railway scheduling automation
railway crew scheduling in Japan Railway
train-set scheduling with maintenance constraints
shift scheduling• Petroleum chemical industry automation
International ship scheduling for crude oil transportation
Transportation network design
Research Talk, March 6, EWO seminar, Carnegie Mellon University

7Supply chain optimization

Vertical integration

Supply chain management： integrated optimization of materialpurchase, production, sales management
Strategiclevel (years)
Tactical level(months)
Operational
level (days)(hour)(minutes)

Economical management
Mid term planning

Material
Requirement
Planning

Supplier

Single machine

Production
Planning

Sales
Distribution Management
Planning

SchedulingDistribution

DemandManufacturer

Transporter

Customer

Horizontal integration
Multi
SinglefactoryfactoryMulticompany

Research Talk, March 6, EWO seminar, Carnegie Mellon University

8Dynamic Model Construction Platform for Collaboration and
Optimization among Enterprises in Smart Supply Chains

戦略レベル
strategic
（年単位）
戦術レベル
tactical
階 (月単位)層
融 作業レベル
operatio
合 (週単位)nal(hour)(minutes)

Artificial Intelligence

Business management
経営管理
Mid-term
planning
中期計画
Procur
資材調達
ement
計画

Production
生産計画
Planning

Distrib
配送計画
ution

Scheduling
スケジューリングTransportation

資材調達
生産
Procurement
Production

輸送計画

販売
Retaili計画
ngfunction

Behavior

Dynamic factory model #1
Demand
需要予測
forecast

Retailer
配送
販売
Distribution

横階層融合

Optimization

機能

Solvers

定義

order

(XML)

仕様記述
(XML)

deliveryfunction(XML)

Dynamic factory model #2

Dynamic model e-library

生産工程モデルSearch a model
Retrieve a template

ル
(XML)

template#1

Large scale optimization

Behavior

Machine Provider
Companies

Control method

・Real time data extraction and analysis
Visualization, cloud computing，manufacturing control loop
・Game theoretical approach for real time optimization of equilibrium solution
Novelty・Standardization of protocols (ISO), common resources for electrical-catalog

ResearchResearch Talk, March 6, EWO seminar, Carnegie Mellon University9Lagrangian Relaxation and Cut Generation
Lagrangian relaxation for production schedulingRelax machine capacity constraints
Decomposition into each single job-level subproblem (Luh et al. 1994)
Lagrangian relaxation with cut generation
Additional constraints are imposed to the related problem to derive better lower boundWe developed a novel dynamic programming recursion with tree structure
T. Nishi et al. Lagrangian relaxation with cut generation for hybrid flowshop
scheduling problems to minimize the total weighted tardiness (2010)
Computers and Operations Research, IF:2.962 (cited in scopus 39 times)
Job 6
Job 1

Job 3

Job 2
Job 4

Job 5
Original problem

𝑂(𝐻𝑀 )

Job 6
Job 1

Job 3

Job 2
Job 4

Job 5

Ordinary Lagrangian Relaxation

𝑂(𝑀𝐻)

Job 6
Job 1

Job 3

Job 2
Job 4

Job 5

Cut generation with tree structure𝑂(𝑀𝐻 + 2𝑝𝑚𝑎𝑥 |𝐶𝑖 |)10

Logic-based Benders decomposition with CMU
Master problem

Subproblemx

min f ( x, y)s. t. C 1 ( x), C 2 ( x),K, C k ( x)x  Dxmin f ( x , y )s. t. C ( x , y )y  DyCut generation
constraints

Cut ２
Relaxed solution
Process 1

Cut １

2 Process 2 AGVs
1

AGV 1

5
5

Process 2
10

2

3
5

1
0

2
4

1

AGV 2

Logic-based Benders (Hooker, 1994)

4

3

20

3
30

4

2
40

50 TIME

Fig.1 Gantt Chart

T. Nishi, Y. Hiranaka, I. Grossmann, A bilevel decomposition algorithm forsimultaneous production scheduling and conflict-free routing for automated guided vehicles
Computers and Operations Research, IF:2.962 (cited 42 times in scopus)

11

Optimization in Public Transport with Prof. VossstationA
B
C

Railway crew scheduling
st
at
io
n

A
B
C

Duty for a crew member

timetimetable
Railway rolling stock planning

Cyclic schedule with maintenanceTrain 1inspection
Train 2Train 3

Heuristics for Mathematical Programming Based Railway T. Nishi et al., A Combined Column Generation andCrew Scheduling, Awarded by Scheduling Society of Japan Heuristics for Railway Short-Term Rolling Stock Planningwith Regular Inspection Constraints, Computers andOperations Research, IF:2.962 (2017)

Research Talk, March 6, EWO seminar, Carnegie Mellon University

12

Matheuristic and Logistic Optimization
Outbound transportation

Inbound transportation
DemandTotal

Loading places

Start(midpoint)

Loading planning

Base

Unloading places
DemandUnloading planning

Split-delivery vehicle routing problem
T. Nishi, T. Izuno, Column generation approach to
Ship scheduling problems for international crude oil
Transportation Comp. Chem. Engng. (2014), IF: 3.113

Dynamic berth allocation
T. Nishi et al. , A dynamic programming-based
Matheuristic for the dynamic berth allocation problem
Annals of Operations Research (2018), IF 1.864

Production Process
Warehouse

Airline Crew Rostering Optimization
Stock Yard

Simultaneous Optimization of Production Planning
Warehouse Layout
G. Zhang, T. Nishi, et al., Omega (2017)
IF: 4.311, Most Downloaded Omega Article (2017)

T. Doi, T. Nishi, S. Voss, European Journal ofOperational Research (2018), IF: 3.428
EJOR Editors’Choice Article, June 201813

Petri net decomposition approach
Local optimization Local optimization
t1

P1

P3

t4

P4

t3

t2
P2

P1
t2

t5

decomposition

t1

P’3

P’’3

t4

P4

t3
P2

t5

Decomposable condition
・ The objective function J is represented by
the summation for each of subnet.
・ The final making is not specified forthe duplicated places.
Research Talk, March 6, EWO seminar, Carnegie Mellon University

14

General Conversion of IP into Petri nets
New Approach for Discrete Optimization

Integer
Programming

Conversion

Petri net model
Reachability Analysis

Original IP+ Valid Inequalities

Conversion

Valid
Inequalities

Structural analysis is conducted via Petri net representation
and reachability analysis
T. Nishi, A. Kodama, Petri net representation of 0-1 integer linear programming
problems, Information Sciences (2017) (IF: 4.305)

15

Cell-based Heuristic Algorithm for
Capacitated Multi-commodity Network
Design Problem

Research Talk, March 6, EWO seminar, Carnegie Mellon University

16Outline
1.
2.
3.
4.
5.
6.

Introduction
Dynamic Multi-commodity Network Design Problem
Cell-based Heuristic Algorithm
Improvement of Performance
Computational experiments
Summary and conclusion

Research Talk, March 6, EWO seminar, Carnegie Mellon University

17

Introduction
Networked System
Connectivity is important for social systems

Layout design in warehousing Transportation systems Communication systems

Society 5.0 promotes connection between people and physicalworld via Internet of Things. Network design is a significant issue.
Research Talk, March 6, EWO seminar, Carnegie Mellon University

18

Conventional Network Design Problem
Network design problem•

Determine a network structure (graph and flow) to minimize total costs

 Output Input Candidate of graph 𝐺 = 𝑁, 𝐴 Origin and destination

Derived graph 𝐺′ = 𝑁′, 𝐴′
Flow quantity from origin to destination

Multi-commodity Network Design Problem (Magnanti, 1984)•

To determine the selection of arcs and flow of commodities.
Commodities are routed from its origin to destination satisfying total
capacity constraints.

 Input Output
Destination 1

Origin 1

Destination 2
Origin 2

Research Talk, March 6, EWO seminar, Carnegie Mellon University

20Dynamic Multi-Commodity Network
Design Problem (DMCND)
Commodities are routed over a time horizon.
12:01

12:03

12:01
12:08

12:00

12:03

12:03
12:13

12:06

12:08

12:00

12:08
12:05

conflict

12:09

12:00

12:01

• Dynamics of commodities (conflicts and jams) are represented.
→ More exact network design can be achieved.
Connectivity• Most of real-world network has connectivity between their origin anddestination -> Connectivity of the selected arcs is important
Research Talk, March 6, EWO seminar, Carnegie Mellon University

21

Conventional works on DMCND
Few works have been developed for DMCND.
Hall et al. (2007) developed a greedy algorithm for S-T path which
has conflicts in dynamic commodities when the distance is equal.
→ Problem is not general



S

T

Conversion of DMCMD into time-space network→ Network size issues

Our objective
 Formulation of dynamic multi-commodity network design problem
 Effective local search algorithm

Research Talk, March 6, EWO seminar, Carnegie Mellon University

22Dynamic Multi-Commodity Network Design Problem (DMCND)

Performance indices•••

Quickest flow
Maximum flow

： Minimize the sum of total time to reach destination： Maximize the total flow quantity

Minium cost flow ：Mimimize the total costs
fixed costs + transportation costs

 Input 𝐺 = 𝑁, 𝐴, 𝐾

 OutputDesigned network 𝑮′ = 𝑵′ , 𝑨′

Selection of arcs 𝑦𝑖,𝑗 ∈ 0,1
Flow quantity 𝑥 𝑘 𝑖,𝑗,𝑡 ∈ ℝ (demand 𝑞 𝑘 , origin 𝑜𝑘 , destination 𝑑𝑘 )

 Capacity of arc 𝑐𝑖,𝑗

 Fixed costs 𝑚𝑖,𝑗 , transportation cost 𝑙𝑖,𝑗
 Time periods T = 0,1, …

1. Flow conservation constraints
2. Arc capacity constraintsk𝑥𝑖𝑗𝑡< 𝑐𝑖𝑗 𝑦𝑖𝑗 (2)

k
k
𝑥𝑖𝑗𝑡
= 𝑥𝑗𝑙𝑡+1
(1)
𝑗
𝑖

𝑙

3. Connectivity constraint of the selected arcs
(3)

Research Talk, March 6, EWO seminar, Carnegie Mellon University23

Two-stage heuristic algorithmkFour dimensions of 𝑥𝑖𝑗𝑡
and binary 𝑦𝑖,𝑗 ∈ 0,1 are too huge for computations.
k
For only 𝑥𝑖𝑗𝑡
→ Dynamic multi-commodity flow is an LP problem.

We propose a neighborhood search which repeats the generation of theselection of arcs and LP for multi-commodity flow problem.

Conventional method
Original problem

Proposed method
Initial generation of 𝐺

Time space network

Static MCND problem

Dynamic MCND problem

Slope Scale Lagrangian
perturbation heuristic

Neighborhood search

Research Talk, March 6, EWO seminar, Carnegie Mellon University

24

Cell-based heuristics
Introduction of concept of cells
Search space for the selection of arcs is too huge
⇒Cell is defined as minimal set of arcs which constitutes a loop.
Cell 2Cell 1

Cell 4Cell 1
Cell 3Single cell

k-neighborhood

Neighborhood search with K-neighborhood cell
flow
Cell 2Cell 1

Cell 4Cell 3Current selection of arcs

Cell 5Cell 7

Cell 62-cells {𝑐2 , 𝑐4 }Neighborhood using 2-cells 25

Cell-based heuristic algorithm
Properties of K-neighborhood cells
Proposition 1. All selection of arcs can be represented by cells.
→ An optimal solution can be represented by cell-based neighborhood.
Proposition 2. Cell-based neighborhood solutions always satisfy
connectivity.

The proposed algorithm can be strengthened by thefollowing components.
1.
2.
3.
4.
5.

Intensification of search using flow information.
Redundant arc elimination
Subtour elimination
Network size reduction
Variable neighborhood search
Research Talk, March 6, EWO seminar, Carnegie Mellon University

26

Application to guide path layout design of AutomatedGuided Vehicles

The layout design of AGV systems |N|=101,|A|=371

General purpose solver (CPLEX)••

Proposed methoddemandTime [s]Obj [-]

Time [s]Obj [-]

28

75.8

26189

269.7

27709

78

10801.91323781122.614159988--2423.7191011CPLEX requires more than 10000 sec.
The proposed method derive a solution with 1000 sec with 7% gap
Research Talk, March 6, EWO seminar, Carnegie Mellon University

27

Application to general graph structure
Improvement of cell based heuristics togeneral graph structure
Reduction of time-space network
Problem size
= A 𝑇−1 𝐾=3 ∗ 2 ∗ 1

Reduced size
=2

Some unreachable arcs for each time period are eliminated by backward and forward
calculations

Variable size of neighborhood
Variable neighborhood depending on the search times

Cell 2Cell 4

Partially opened outside loop
Research Talk, March 6, EWO seminar, Carnegie Mellon University28Computational experiments
Benchmark instance for capacitated fixed cost multi-commodity
network design problem (Gendron and Crainic, 1994)
General purpose
solver (CPLEX)

Proposed method

Ant Colony
Optimization

Slope Scaling andLagrangean
Perturbation

|M|

|N|

|A|

Time [s]Objective
value

Time [s]Objective
value

Time [s]Objective
value

Time [s]Objective
value

10
10
25
100

10
10
10
20

90
56
90
204

2.44
0.95
3.78
-

1014
1213
2922
-

40.9
37.9
91.9
381

1227
1325
3140
17892

65.1
68.4
200.9
-

1014
1213
2927
-

316.6
226.9
497.4
-

1113
1213
2927
-

Research Talk, March 6, EWO seminar, Carnegie Mellon University

29Summary and conclusion
We have proposed a cell-based heuristic for dynamic multicommodity network design problem.
The proposed heuristic utilizes the cell-based arc selection
and multi-commodity flow problem repeatedly. The
performance is strengthened by variable neighborhood
search and intensification of search.
The effectiveness of the proposed method is confirmed
from computational experiments.

Research Talk, March 6, EWO seminar, Carnegie Mellon University

30

Simultaneous Optimization of ProductConfiguration and Supply Chain Planning
Considering Customer's Participationin Product Design

Takuya Tsuboi and Tatsushi Nishi
Graduate School of Engineering Science
Osaka University, Japan
Research Talk, March 6, EWO seminar, Carnegie Mellon University

31

Introduction
Mass Customization = Mass Production + Customization
 Modular Production: Produce a large number of modules andmanufacture a variety of products by assembling them

→ Electric appliance, Computer, Car, Bike , Shoes, Clothes…

Ex: Nissan Common Module Family
 There are main four modules:
Engine compartment, Cockpit,
Front underbody and Rear underbody
 Each module has appropriate variations

 A variety of vehicles can be designedby assembling these modules
http://www.Nissanglobal.com/EN/NEWS/2012/_STORY/120227-01-e.html

Research Talk, March 6, EWO seminar, Carnegie Mellon University

32

Customer's participation in product design
Conventional :Product configuration is determined by manufacturer
Introduction online self-customization service

Now: Customer can determine product configuration

Shoes customization on “miadidas”(adidas)“https://shop.adidas.jp/miadidas/”Bike customization on “Built Own Your Bike”(HARLEY DAVIDSON)“https://www.harley-davidson.com/us/en/tools/bike-builder/index.html”

Research Talk, March 6, EWO seminar, Carnegie Mellon University

33

Introduction
 Challenges in Mass Customization
 Product configuration : Selection of products and modules
Configurations of products
 Supply chain planning : Operation of facilities, Selection of suppliers
Production products, Inventory, Distribution

Simultaneous optimization of product configuration and supply chain planning Customer's participation in product design(e.g. Online self-customization)

Optimization model considering customer's preferences and purchasing behavior
 Fluctuated costs and demands

Dynamic(multi-period) optimization modelResearch Talk, March 6, EWO seminar, Carnegie Mellon University

34

Introduction
 Conventional works
 Product configuration (PC) problem
 Maximization customer utility model (Frutos et al, 2004)
 Consumer choice rule (Cao et al. 2012)

integrated

Consider customer purchasing behavior

 Supply chain planning (SCP) problem
Facility location, Supplier selection …
 Simultaneous optimization of PC and SCP Comparison two-phase model and integrated model (Khalf et al. 2010 )Single period, Cost minimization only

 Stackelberg model (Yang et al. 2015 )Customer utility maximization and Cost minimization
Single period, Not consider customer purchasing behavior

Research Talk, March 6, EWO seminar, Carnegie Mellon University

35

Introduction
 Our research
・We formulate new multi-period model for mass customization
 Simultaneous optimization of PC and SCP Customer model based on customer purchasing behavior
 Delayed demand satisfaction

・ We optimize both customer satisfaction and total profit byGame theoretical approach Leader : Manufacturer, Follower: Customers
 Leader : Customer, Follower: Manufacturer

・ We reformulate Bilevel problem into single-level problem
and obtain an exact Stackelberg equilibrium

Research Talk, March 6, EWO seminar, Carnegie Mellon University

36

Production system and interaction between
manufacturer and customers
Manufacturer

Customers

2. Simultaneous optimization

1. Product configuration request

Bilevel Optimization Model
Customers’
Model

P1

M1

Due dates

Product
configuration

M2

3. Send available
to promise・・・

Supply Chain
Planning
4. Customer satisfaction evaluation
Research Talk, March 6, EWO seminar, Carnegie Mellon University

37

Problem definition
 Product and module definition

 The module is a part of product and it has several functions
 Each product can be manufactured by assembling somemodules selected from candidate modules
Ex: Alternative two configurations for product 1
1.2

P11110100.7 M1

Assembly

0.5010010F2

1.1

F5

0.6 M3
0.2 M4100010010000M2101000F1

P1111010

F3

F1

F5

F2

Product

0.3 M5001000ModuleF3Function

Research Talk, March 6, EWO seminar, Carnegie Mellon University

38

Problem definition
 Supply chain planning is to determine the production volume of the
products and the procurement volume of modules , the operation of
production sites and the selection of suppliers

Modules are supplied by suppliers and transported to production sites

Products are manufactured by assembling some modules at production siteProducts are directly sold to customers

Modules are stocked as inventories

M1

M1
M2

Supplier

M1
P1

Production
Site

Customer

Research Talk, March 6, EWO seminar, Carnegie Mellon University

39

Stackelberg model between customers and manufacturer
Customers: to maximize own satisfaction
Manufacturer: to maximize total profit

Different decision makers

Derive the equilibrium solution by Game theoretical approach・We propose Bilevel optimization model that the manufacturer predicts
customers' purchasing behavior and maximize total profit Stackelberg model
Manufacturer

LeaderFollowers

Customer1

Customer 2・・・

Customer 𝐾

Research Talk, March 6, EWO seminar, Carnegie Mellon University40Formulation of Bilevel problem
Bilevel programming problem between customers and manufacturer (BP)max (TP)

Manufacturer’s objective function

s.t. 𝐶𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 1 − (13)max (𝑇𝑈𝑘 )s.t.

Manufacturer’s constraints

Customer’s objective function

𝐶𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 14𝑘 − (16𝑘 )Bilevel programming problem
can not be solved directly

Customer’s constraints

・Iterative optimization
・Single-level reformulation
・Nested evolutionally algorithm …

・In this model, the follower’s optimization problem is a LP

 Reformulate BP into a single-level programming problem
Research Talk, March 6, EWO seminar, Carnegie Mellon University

41

Reformulation method
Duality：
Theorem

In LP, if either P or D has a finite optimal value, then so does
the other, the optimal values coincide, and optimal solutions toboth P and D exist.

・Transform the followers’ optimization problems
to some constraints based on duality theorem

・Remove the objective functions of followers from BP
and add two kinds of constraint to BP

1. Dual optimality condition (→ the optimality of lower-level problem)
2. Dual feasibility condition (→ the feasibility of lower-level problem)

Proposition：Reformulated SP is equivalent to original BP
Research Talk, March 6, EWO seminar, Carnegie Mellon University42

Reformulation• Reformulation Bilevel programming problem to Single-level programming problem

Bilevel programming problem(BP)max 𝐹(𝑥)s.t. 𝐺(𝑥) ≤ 0
max 𝑓(𝑥)Add new constraints
s.t. 𝑔(𝑥) ≤ 0
based on duality theorem
Single-level programming problem(SP)max 𝐹(𝑥)s.t. 𝐺(𝑥) ≤ 0
𝐻(𝑥) ≤ 0
The reformulated single-level problem can be solved by general-purpose solver

Research Talk, March 6, EWO seminar, Carnegie Mellon University

43Computational results・Stackelberg equilibrium between the manufacturer and multiple customers
Ins 1(T=3)

Ins 2(T=3)

Ins 3(T=4)

Ins 4(T=3)

Ins 5(T=4)

Total profit

1197.75

2681.135315.896240.179184.77

Cus. 1 satisfaction

331.64338.21603.85541.51563.54Cus. 2 satisfaction

343.59335.51510.51

632.25515.40Cus. 3 satisfaction-

381.25527.46540.81525.71

Cus. 4 satisfaction

-

-

-

502.43599.56

Cus. 5 satisfaction

-

-

-

-

467.88Computation time(s)25.13

119.611619.60

4857.80(36346.15)(Problem size： P = 4, M = 9, I = 3, J = 1, ρ = 1 𝑜𝑟 2)

Research Talk, March 6, EWO seminar, Carnegie Mellon University

44

Stackelberg model between customer and manufacturer
Proposal: Bilevel optimization model that prioritize customer's
requests and maximize customer satisfaction
 Stackelberg model (Restriction: single customer)
LeaderCustomer

Follower

Manufacturer

Bilevel programming problem between customers and manufacturer (BP)max (TU)

Customer’s objective function

s.t. 𝐶𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 1 − (6)max (TP)

Customer’s constraints

Manufacturer’s objective function

s.t. 𝐶𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 7 − (16)Manufacturer’s constrains

Research Talk, March 6, EWO seminar, Carnegie Mellon University

45Computational results
 The influence of delivery delay to supply chain
The coefficient related to product configuration (A) : 1
The coefficient related to delivery delay (B) : 0, 1, 10← change

SP(・)

SP(0)

SP(1)

SP(10)

Customer Satisfaction

95.49

91.77

88.53

Product configuration utility

95.49

95.49

88.53

Delivery delay penalty

0

3.72

0

Total profit-124.69-129.07-172.20

Computational time[s]

3.67

6.24

5.28

(Problem size： 𝑇 = 3, P = 3, M = 8, I = 2, J = 1, ρ = 1)

Customer purchasing behavior affects
product configuration and supply chain planningResearch Talk, March 6, EWO seminar, Carnegie Mellon University

46

Conclusion and Future work Conclusion• We propose new multi-period model for Simultaneous optimization
 Formulate two Bilevel programming problems•

Reformulation based on duality theorem
 The effectiveness of the proposed model is confirmed
from computational experiment Future work•

We will develop an effective solution approach•

We will extend supply chain model Multiple customers are leader, manufacturer is follower

Research Talk, March 6, EWO seminar, Carnegie Mellon University

47

Integration of Data Science, AI and Optimization
Input and output data

Data Analytics
Extraction of constraints
Extraction of objective function

Data-based
Discrete Optimization

Discrete event systems

Conversion

More trustable modelSpecification

Validation

with validated results

Conversion
Research Talk, March 6, EWO seminar, Carnegie Mellon University

48

Objective
Extract objective function from input and output data of scheduling problems．

Research Talk, March 6, EWO seminar, Carnegie Mellon University

49Scheduling Problem• Single Machine Scheduling Problem
ω

d

p

JOB1

𝜔1

𝑑1

𝑝1

JOB2

𝜔2

𝑑2

𝑝2

JOB3

𝜔3

𝑑3

𝑝3

…

…

…

…

Instancemachine

M1
Integer
programing

JOB3

JOB1

JOB2

Output…
time

ω : weight d : due date p : processing time

Research Talk, March 6, EWO seminar, Carnegie Mellon University

50Construction of schedulingproblems• Variant of objective functions
Objective Function : min z① Weighted Completion Time

𝜔𝑖 𝐶𝑖

z=

② Weighted Lateness

z=

𝜔𝑖 𝐿𝑖

③ Weighted Number of Tardy Jobs

z=

𝜔𝑖 𝑈𝑖

④ Maximum Latenessz = max 𝐿𝑖𝑖Research Talk, March 6, EWO seminar, Carnegie Mellon University

51

Neural Network
Training Phase

Instances
Preprocessing

Training
Data

Untrained
Model

Labels

Outputs(Type of Objective
Function )Research Talk, March 6, EWO seminar, Carnegie Mellon University

52

Learning Process for NN• Preprocessing
JOB1

JOB2

JOB3

…

𝜔1

𝜔2

𝜔3

…

𝑑1

𝑑2

𝑑3

…

𝑝1
𝜔1
𝑝1
𝜔1
𝑑1
1
𝑝1 𝑑1
𝜔1
𝑝1 𝑑1

𝑝2
𝜔2
𝑝2
𝜔2
𝑑2
1
𝑝2 𝑑2
𝜔2
𝑝2 𝑑2

𝑝3
𝜔3
𝑝3
𝜔3
𝑑3
1
𝑝3 𝑑3
𝜔3
𝑝3 𝑑3

…

𝑡1

𝑡2

𝑡3

…

Ranking 𝜏𝜔
𝜏𝑑
𝜏𝑝
𝜏𝜔/𝑝

…

𝜏𝜔/𝑑

…

𝜏1/𝑝𝑑

…

𝜏𝜔/𝑝𝑑

…

𝜏𝑡

t : start time

Research Talk, March 6, EWO seminar, Carnegie Mellon University

53

Learning Process for NN• ②(preprocessing)– Spearman’s rank correlation coefficient

𝜌=1−
𝜏𝑡 と 𝜏𝜔
𝜏𝑡 と 𝜏𝑑𝜏𝑡 と 𝜏𝑝𝜏𝑡 と 𝜏𝜔/𝑝𝜏𝑡 と 𝜏𝜔/𝑑𝜏𝑡 と 𝜏1/𝑝𝑑
𝜏𝑡 と 𝜏𝜔/𝑝𝑑

6

𝑁
𝑖=1

𝜏𝑥 𝑖 − 𝜏𝑦 𝑖

2𝑁3 − 𝑁

⇒ 𝜌𝜔
⇒ 𝜌𝑑
⇒ 𝜌𝑝
⇒ 𝜌𝜔/𝑝⇒ 𝜌𝜔/𝑑⇒ 𝜌1/𝑝𝑑⇒ 𝜌𝜔/𝑝𝑑

Research Talk, March 6, EWO seminar, Carnegie Mellon University

54

Learning Neural Network• Three layers Neural Network
𝑥1 = 𝜌𝜔
𝑥2 = 𝜌𝑑
𝑥3 = 𝜌𝑝
𝑥4 = 𝜌𝜔/𝑝𝑥5 = 𝜌𝜔/𝑑𝑥6 = 𝜌1/𝑝𝑑
𝑥7 = 𝜌𝜔/𝑝𝑑

Output value is the percentageof the objective function

Research Talk, March 6, EWO seminar, Carnegie Mellon University

55

Identification of the objectivefunction
Prediction Phase

New Instance
Preprocessing

Test
Data

Predictive
Model
Label (Type of

New Output

Objective Function )Research Talk, March 6, EWO seminar, Carnegie Mellon University

56Computational Results
8000 Instances (=2000×4)→ Training Data : 7200,

Test Data : 800

Transition of the accuracy with respect to episode Accuracy for each objective function
Type

Accuracy

1.

𝜔𝑖 𝐶𝑖

0.95

2.

𝜔𝑖 𝐿𝑖

0.78

3.

𝜔𝑖 𝑈𝑖

0.83

4. max 𝐿𝑖

0.93

Total

0.88

𝑖

Research Talk, March 6, EWO seminar, Carnegie Mellon University

57

Future works
1. Application to Parallel Machine Scheduling
Problem
2. Improvement of the performance of theneural network
3. Identification of constraints or problem
featuresResearch Talk, March 6, EWO seminar, Carnegie Mellon University

58