Supply Chain Modeling
Language for Optimization
-Implementation in PythonMikio KUBO
Tokyo University of
Marine Science of Technology
Agenda
• What’s the SCML
(Supply Chain Modeling Language)
• How to implement the SCML in Python
• (Applications)
What is the SCML?
Supply Chain
Optimization
Models
proposed in 2009 by M. K.
(international scheduling symposium)
SCML
Combinatorial
Optimization
Models
SCML.py
Solvers
(using metaheuristics
and/or MIP/CP
solvers)
Supply chain optimization models
•
•
•
•
•
•
•
resource constrained scheduling (RCS)
lot-sizing (LS)
logistics network design (LND)
safety stock allocation (SSA)
economic order quantity (EOQ)
inventory policy optimization (IPO)
vehicle routing (VR)
Combinatorial optimization problems
•
•
•
•
•
•
•
•
•
•
set covering problem (SC)
generalized assignment problem (GA)
rectangular packing problem (RP)
facility location problem (FL)
multi-constrained knapsack problem (MK)
graph coloring problem (GC)
graph partitioning problem (GP)
maximum stable set problem (MSS)
(constrained) bin packing problem (BP)
quadratic assignment problem (QA)
Previous SCO models
Flow models
Scheduling models
(LND, FL)
(RCS, LS, VR)
Constrained
optimization models
Multi-echelon
inventory models
(Algebraic modeling
languages)
(IPO, SSA, EOQ, LS)
Previous SCO models
Network=(Node, Arc),
Product
Activity, Resource
Flow models
Scheduling models
(LND, FL)
(RCS, LS, VR)
Constrained
optimization models
Multi-echelon
inventory models
(Algebraic modeling
languages)
(IPO, SSA, EOQ, LS)
Variable, Constraint
Product (BOM)
Activity based view of linear
programming
Dantzig-Wolfe (1963)
row
(constraint)
=resource
matrix A=[aij]
+
+
-
activity i consumes
resource j by aij
column (variable)
=activity Xj
b
system input
of resource
Problem class
P ro b le m
Gurobi (MIP)
GLPK (MIP/Free)
SCOP (CP)
C o n s tra in t
Va ria b le
R e so u rce
A c tiv ity
Entities of the SCML
•
•
•
•
•
•
•
•
•
•
•
activity
resource
product
node
arc
Basic
entities
temporal
piecewise
horizon
state
solver
etc., ...
Activity
•
Every action that requires the resources,
consumes and/or produces the product, and
derives the cost
consume
product
Fixed Cost
Variable Cost
activity
require
resource
produce
product
Resource
•
Every entity of limited availability required
and/or consumed by activities
Our focus is on the physical, human, and
financial resources.
Product
•
•
Products are consumed and/or produced by
activities
Products are items or commodities through
the network
consume
product
produce
activity
product
Product
•
•
Products are consumed and/or produced by
activities
Products are items or commodities through
the network
node
product
arc
node
product
Node and arc
• Network is defined by the set of nodes and
arcs
node
arc
node
Declaration and attributes
•
•
•
•
•
activity
resource
product
node
arc
activity declaration
activity activity-name [attributes]
attribute:
duedate integer+
weight integer+
consume product-name unit real+ ...
produce product-name unit real+ ...
...
Key concepts for implementing the
SCML in Python
• Inheritance / Composition
• Hierarchy
• Global / Local
Inheritance
Entity class
Entity has a name and attributes (defined by
arguments as a dictionary)
class Entity():
def __init__(self, name="",**args):
self.name=name
self.attributes=copy.deepcopy(args)
An activity object for LS
act1=Activity("act1",
variablecost=1, fixedcost=53,,leadtime=3,
resources={"res1":1},
consume={"parts1":1,"parts2":2},
produce={"prod1":1})
consume
Class Activity(Entity):
prod1
parts1
activity
parts2
produce
resource
Composition
Hierarchy
• Hierarchy can be defined on every entity using
attribute “children”
• Every attribute of a parent is copied to its
children (same as inheritance)
activity
children
Mode Mode
Mode
Example: an activity object for RP
item1=Activity("item1”, cost=10,
children=
“mode1":
{resources:{"width":3,"height":2}} ,
“mode2”:
{resources={"width":2,"height":3}, cost=5})
mode1
(cost=10)
mode2
(cost=5)
Global / Local
• Local products can be defined on nodes
• Local activities and resources can be defined on
arcs, i.e., arcs can own activities and resources
• Otherwise, entities are called global.
arc
node
node
produce
consume
product
activity
require
resource
product
Lot-sizing (LS) model
•
horizon, activity, resource, product
consume
product
activity
produce
resource
product
Example for solving LS in python (1)
from SCML import * #import everything from SCML module
sample=SCML()
#generate SCML class object
sample.setHorizon(5) #set the planning horizon to 5
#generate the product class objects
prod1=Product("prod1",demand=[5,5,6,7,8],
holdingcost=5,leadtime=1)
parts1=Product("parts1",holdingcost=1,leadtime=3)
parts2=Product("parts2",holdingcost=1,leadtime=1)
#generate the resource class object
res1=Resource(“res1”,capacity={(0,“inf”):25})
Example for solving LS in python (2)
#generate the activity class object
act1=Activity("act1",variablecost=1,fixedcost=53,
resources={"res1":1},
consume={"parts1":1,"parts2":2},
generate={"prod1":1})
#add the generated objects into the problem class
sample.addActivity(act1)
sample.addProducts(prod1,parts1,parts2)
sample.addResource(res1)
sample.solve(“LS”) #solve by the lot-sizing solver
Future plans
• Applications (hybrid models)
– Lot-sizing + Inventory policy optimization
– Logistics network design + Resource constrained
scheduling +Lot-sizing
• Excel interface for beginners
• A book on the SCML
(will be published in 2010-11 from Asakura
Publishers)
Descargar

Document