The benefits of state aggregation with extreme-point weighting for assemble-to-order systems

Emre Nadar, Alp Akcay, Mustafa Akan, Alan Scheller-Wolf

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

We provide a new method for solving a very general model of an assemble-toorder system: multiple products, multiple components that may be demanded in different quantities by different products, batch production, random lead times, and lost sales, modeled as a Markov decision process under the discounted cost criterion. A control policy specifies when a batch of components should be produced and whether an arriving demand for each product should be satisfied. As optimal solutions for our model are computationally intractable for even moderately sized systems, we approximate the optimal cost function by reformulating it on an aggregate state space and restricting each aggregate state to be represented by its extreme original states. Our aggregation drastically reduces the value iteration computational burden. We derive an upper bound on the distance between aggregate and optimal solutions. This guarantees that the value iteration algorithm for the original problem initialized with the aggregate solution converges to the optimal solution. We also establish the optimality of a lattice-dependent base-stock and rationing policy in the aggregate problem when certain product and component characteristics are incorporated into the aggregation/disaggregation schemes. This enables us to further alleviate the value iteration computational burden in the aggregate problem by eliminating suboptimal actions. Leveraging all of our results, we can solve the aggregate problem for systems of up to 22 components, with an average distance of 11.09% from the optimal cost in systems of up to 4 components (for which we could solve the original problem to optimality).

TaalEngels
Pagina's1040-1057
Aantal pagina's18
TijdschriftOperations Research
Volume66
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 1 jul 2018

Vingerafdruk

Agglomeration
Assemble-to-order
Order systems
Weighting
Cost functions
Byproducts
Costs
Sales
Optimal solution
Burden
Optimality

Trefwoorden

    Citeer dit

    Nadar, Emre ; Akcay, Alp ; Akan, Mustafa ; Scheller-Wolf, Alan. / The benefits of state aggregation with extreme-point weighting for assemble-to-order systems. In: Operations Research. 2018 ; Vol. 66, Nr. 4. blz. 1040-1057
    @article{71ea0093ae424e3d8b9636ad01afa82e,
    title = "The benefits of state aggregation with extreme-point weighting for assemble-to-order systems",
    abstract = "We provide a new method for solving a very general model of an assemble-toorder system: multiple products, multiple components that may be demanded in different quantities by different products, batch production, random lead times, and lost sales, modeled as a Markov decision process under the discounted cost criterion. A control policy specifies when a batch of components should be produced and whether an arriving demand for each product should be satisfied. As optimal solutions for our model are computationally intractable for even moderately sized systems, we approximate the optimal cost function by reformulating it on an aggregate state space and restricting each aggregate state to be represented by its extreme original states. Our aggregation drastically reduces the value iteration computational burden. We derive an upper bound on the distance between aggregate and optimal solutions. This guarantees that the value iteration algorithm for the original problem initialized with the aggregate solution converges to the optimal solution. We also establish the optimality of a lattice-dependent base-stock and rationing policy in the aggregate problem when certain product and component characteristics are incorporated into the aggregation/disaggregation schemes. This enables us to further alleviate the value iteration computational burden in the aggregate problem by eliminating suboptimal actions. Leveraging all of our results, we can solve the aggregate problem for systems of up to 22 components, with an average distance of 11.09{\%} from the optimal cost in systems of up to 4 components (for which we could solve the original problem to optimality).",
    keywords = "Aggregation, Approximate dynamic programming, Assemble-to-order systems, Markov decision processes",
    author = "Emre Nadar and Alp Akcay and Mustafa Akan and Alan Scheller-Wolf",
    year = "2018",
    month = "7",
    day = "1",
    doi = "10.1287/opre.2017.1710",
    language = "English",
    volume = "66",
    pages = "1040--1057",
    journal = "Operations Research",
    issn = "0030-364X",
    publisher = "INFORMS Institute for Operations Research and the Management Sciences",
    number = "4",

    }

    The benefits of state aggregation with extreme-point weighting for assemble-to-order systems. / Nadar, Emre; Akcay, Alp; Akan, Mustafa; Scheller-Wolf, Alan.

    In: Operations Research, Vol. 66, Nr. 4, 01.07.2018, blz. 1040-1057.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    TY - JOUR

    T1 - The benefits of state aggregation with extreme-point weighting for assemble-to-order systems

    AU - Nadar,Emre

    AU - Akcay,Alp

    AU - Akan,Mustafa

    AU - Scheller-Wolf,Alan

    PY - 2018/7/1

    Y1 - 2018/7/1

    N2 - We provide a new method for solving a very general model of an assemble-toorder system: multiple products, multiple components that may be demanded in different quantities by different products, batch production, random lead times, and lost sales, modeled as a Markov decision process under the discounted cost criterion. A control policy specifies when a batch of components should be produced and whether an arriving demand for each product should be satisfied. As optimal solutions for our model are computationally intractable for even moderately sized systems, we approximate the optimal cost function by reformulating it on an aggregate state space and restricting each aggregate state to be represented by its extreme original states. Our aggregation drastically reduces the value iteration computational burden. We derive an upper bound on the distance between aggregate and optimal solutions. This guarantees that the value iteration algorithm for the original problem initialized with the aggregate solution converges to the optimal solution. We also establish the optimality of a lattice-dependent base-stock and rationing policy in the aggregate problem when certain product and component characteristics are incorporated into the aggregation/disaggregation schemes. This enables us to further alleviate the value iteration computational burden in the aggregate problem by eliminating suboptimal actions. Leveraging all of our results, we can solve the aggregate problem for systems of up to 22 components, with an average distance of 11.09% from the optimal cost in systems of up to 4 components (for which we could solve the original problem to optimality).

    AB - We provide a new method for solving a very general model of an assemble-toorder system: multiple products, multiple components that may be demanded in different quantities by different products, batch production, random lead times, and lost sales, modeled as a Markov decision process under the discounted cost criterion. A control policy specifies when a batch of components should be produced and whether an arriving demand for each product should be satisfied. As optimal solutions for our model are computationally intractable for even moderately sized systems, we approximate the optimal cost function by reformulating it on an aggregate state space and restricting each aggregate state to be represented by its extreme original states. Our aggregation drastically reduces the value iteration computational burden. We derive an upper bound on the distance between aggregate and optimal solutions. This guarantees that the value iteration algorithm for the original problem initialized with the aggregate solution converges to the optimal solution. We also establish the optimality of a lattice-dependent base-stock and rationing policy in the aggregate problem when certain product and component characteristics are incorporated into the aggregation/disaggregation schemes. This enables us to further alleviate the value iteration computational burden in the aggregate problem by eliminating suboptimal actions. Leveraging all of our results, we can solve the aggregate problem for systems of up to 22 components, with an average distance of 11.09% from the optimal cost in systems of up to 4 components (for which we could solve the original problem to optimality).

    KW - Aggregation

    KW - Approximate dynamic programming

    KW - Assemble-to-order systems

    KW - Markov decision processes

    UR - http://www.scopus.com/inward/record.url?scp=85051693744&partnerID=8YFLogxK

    U2 - 10.1287/opre.2017.1710

    DO - 10.1287/opre.2017.1710

    M3 - Article

    VL - 66

    SP - 1040

    EP - 1057

    JO - Operations Research

    T2 - Operations Research

    JF - Operations Research

    SN - 0030-364X

    IS - 4

    ER -