Notice
This record has been edited as far as possible, missing data will be added when the version of record is issued.
Metadata only
Date
2017Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
Minimizing an arrangement increasing (AI) function with a matrix input over intra-column permutations is a difficult optimization problem of a combinatorial nature. Unlike maximization of AI functions (which is achieved by perfect positive dependence, namely, arranging all columns in an increasing order), minimization is a much more challenging problem due to the lack of a universal definition and construction of compensating arrangements in more than two dimensions. We consider AI functions with a special structure, which facilitates finding close-to-optimal solutions by employing the concept of Sigma-countermonotonicity and the (Block) Rearrangement Algorithm. We show that many classical optimization problems, including stochastic crew scheduling and assembly of reliable systems, have objective functions with this structure, and illustrate with a numerical case study. This paves a path to obtaining approximate solutions for problems that have so far been considered intractable. Show more
Publication status
publishedExternal links
Journal / series
Annals of Operations ResearchPublisher
SpringerSubject
Schur-convexity; Negative dependence; Scheduling; Systems assembly; Archimedean copulas; Rearrangement AlgorithmOrganisational unit
03288 - Embrechts, Paul (emeritus) / Embrechts, Paul (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics