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