A Discrete–Continuous Routing Problem with Precedence Constraints

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 invol...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0081-5438
1531-8605
DOI:10.1134/S0081543818020074