A Discrete–Continuous Routing Problem with Precedence Constraints

• Published in: Proceedings of the Steklov Institute of Mathematics 2018-04, Vol.300 (Suppl 1), p.56-71
• Main Authors: Chentsov, A. G., Chentsov, A. A.
• Format: Article
• Language: English
• Subjects: Continuity (mathematics); Cost function; Dependence; Job shops; Mathematics; Mathematics and Statistics; Megalopolises; Metric space; Precedence constraints; Production scheduling
• ISSN: 0081-5438; 1531-8605
• DOI: 10.1134/S0081543818020074

We consider the problem of visiting closed sets in a compact metric space complicated by constraints in the form of precedence constraints and a possible dependence of the cost function on a set of tasks. We study a variant of the approximate realization of the extremum by applying models that involve problems of sequential visits to megalopolises (nonempty finite sets). This variant is naturally embedded into a more general construction that implements sequential visits to nonempty closed sets (NCSs) from a finite system in a metrizable compact space. The space of NCSs is equipped with the Hausdorff metric, which is used to estimate (under the corresponding condition that the sections of the cost functions are continuous) the proximity of the extrema in the problem of sequential visits for any two systems of NCSs (it is assumed that the numbers or NCSs in the systems are the same). The constraints in the form of precedence constraints are preserved in this variant.