The concept of analytic geometry, i.e., the reciprocal transformation of geometry and algebra, hints a prospect for the reciprocal transformation of the “path problem” and the “time float problem”. A reciprocal transformation can be used to solve a complex problem in one field by translating it into a simpler one in another field. In this case, owing to the generalized concept of length, various types of non-path problems such as the optimum allocation problem and equipment replacement problem can be represented as “path problems”. A “length network”, which is generalized in nature, is translated into a “time network” by changing the meanings of arcs and lengths. Furthermore, “path problems” can be represented as “time float problems” by discovering the relationships of paths in the length network and time floats in the time network. Base on the relationships, “time float problems” also can be represented as “path problems”. The relationships are keys to updating the mutual correspondence of path problems and time float problems. The relationships mirror the uniform qualities of networks in various disciplines and fields. We apply such relationships to solve optimum allocation problems, equipment replacement problems, and path problems with required lengths and to analyze anomalies in projects under generalized precedence relations. These applications test the effectiveness of our proposed approach to theoretical and applied researches in various disciplines and fields.
Accepté le :
DOI : 10.1051/ro/2016003
Mots-clés : Operations research, path, time float, abnormal critical activity, optimum allocation problem, equipment replacement problem
@article{RO_2017__51_1_43_0,
author = {Su, Zhi-xiong and Qi, Jian-xun and Wei, Han-ying},
title = {Theory and application of reciprocal transformation of {\textquotedblleft}path problem{\textquotedblright} and {\textquotedblleft}time float problem{\textquotedblright}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {43--66},
publisher = {EDP-Sciences},
volume = {51},
number = {1},
year = {2017},
doi = {10.1051/ro/2016003},
zbl = {1358.90021},
mrnumber = {3589263},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2016003/}
}
TY - JOUR AU - Su, Zhi-xiong AU - Qi, Jian-xun AU - Wei, Han-ying TI - Theory and application of reciprocal transformation of “path problem” and “time float problem” JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 43 EP - 66 VL - 51 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2016003/ DO - 10.1051/ro/2016003 LA - en ID - RO_2017__51_1_43_0 ER -
%0 Journal Article %A Su, Zhi-xiong %A Qi, Jian-xun %A Wei, Han-ying %T Theory and application of reciprocal transformation of “path problem” and “time float problem” %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 43-66 %V 51 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2016003/ %R 10.1051/ro/2016003 %G en %F RO_2017__51_1_43_0
Su, Zhi-xiong; Qi, Jian-xun; Wei, Han-ying. Theory and application of reciprocal transformation of “path problem” and “time float problem”. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 1, pp. 43-66. doi : 10.1051/ro/2016003. http://archive.numdam.org/articles/10.1051/ro/2016003/
and , Speeding up the Floyd–Warshall algorithm for the cycled shortest path problem. Appl. Math. Lett. 25 (2012) 1–5. | DOI | MR | Zbl
R. Alur, S. Kannan, K. Tian and Y. Yuan, On the complexity of shortest path problems on discounted cost graphs. In: Language and Automata Theory and Applications. Springer (2013) 44–55. | MR | Zbl
, , and , Exact algorithms for the traveling salesman problem with draft limits. Eur. J. Oper. Res. 235 (2014) 115–128. | DOI | MR | Zbl
A. Battersby, Network Analysis for Planning and Scheduling, 3 edition. Wiley, New York (1970). | Zbl
, On a routing problem. Quarterly Appl. Math. 16 (1958) 87–90. | DOI | MR | Zbl
, , and , The maximum capacity shortest path problem: generation of efficient solution sets. RAIRO: OR 36 (2002) 1–19. | DOI | Numdam | MR | Zbl
, , and , Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica 65 (2013) 129–145. | DOI | MR | Zbl
, and , Critical path in an activity network with time constraints. Eur. J. Oper. Res. 100 (1997) 122–133. | DOI | Zbl
, A note on two problems in connexion with graphs. Numer. Math. 1 (1959) 269–271. | DOI | MR | Zbl
, An algebra for the analysis of generalized activity networks. Manage. Sci. 10 (1964) 494–514. | DOI
S.E. Elmaghraby, Activity Networks: Project Planning and Control by Network Models. Wiley, New York (1977). | Zbl
and , On project representation and activity floats. Arab. J. Sci. Eng. 15 (1990) 627–637. | Zbl
and , The analysis of activity networks under generalized precedence relations (GPRs). Manage. Sci. 38 (1992) 1245–1263. | DOI | Zbl
, Activity nets: A guided tour through some recent developments. Eur. J. Oper. Res. 82 (1995) 383–408. | DOI | Zbl
, and , Ant colony extended: Experiments on the travelling salesman problem. Expert Syst. Appl. 42 (2015) 390–410. | DOI
, and , Approximating the longest cycle problem in sparse graphs. SIAM J. Comput. 31 (2002) 1596–1607. | DOI | MR | Zbl
and , Continuous fuzzy longest path problem in project networks. J. Appl. Sci. 8 (2008) 4061–4069. | DOI
, Linear scheduling model: Float characteristics. J. Constr. Eng. Manage. 127 (2001) 255–260. | DOI
, and , Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles. Comput. Oper. Res. 40 (2013) 2485–2492. | DOI | MR | Zbl
and , Optimal paths in dynamic networks with dependent random link travel times. Transp. Res. B 46 (2012) 579–598. | DOI
J.E. Kelley Jr and M.R. Walker, Critical-path planning and scheduling. In: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference, ACM (1959) 160–173.
, and , Comparing different metaheuristic approaches for the median path problem with bounded length. Eur. J. Oper. Res. 190 (2008) 587–597. | DOI | MR | Zbl
, , and , PTAS for the minimum k-path connected vertex cover problem in unit disk graphs. J. Global Optim. 56 (2013) 449–458. | DOI | MR | Zbl
P.M.V. Lima, G.C. Pereira, M.M. Morveli-Espinoza and F.M.G. Franca, Mapping and Combining Combinatorial Problems into Energy Landscapes via Pseudo-Boolean Constraints. Vol. 3704 of Lect. Notes Comput. Sci. Springer, Berlin (2005) 308–317.
and , Float types in linear schedule analysis with singularity functions. J. Constr. Eng. Manage. 135 (2009) 368–377. | DOI
, and , Integer linear models with a polynomial number of variables and constraints for some classical combinatorial optimization problems. Pesquisa Operacional 23 (2003) 161–168. | DOI
, A new formulation and approach for the black and white traveling salesman problem. Comput. Oper. Res. 53 (2015) 96–106. | DOI | MR | Zbl
and , The probabilistic longest path problem. Networks 33 (1999) 207–219. | DOI | MR | Zbl
and , Enumerating K best paths in length order in DAGs. Eur. J. Oper. Res. 221 (2012) 308–316. | DOI | MR | Zbl
, and , Multiobjective shortest path problems with lexicographic goal-based preferences. Eur. J. Oper. Res. 239 (2014) 89–101. | DOI | MR | Zbl
and , Analysis of an anomaly: The increase in time float following consumption. Sci. World J. 2014 (2014) 415870.
, A path-relinking metaheuristic for the resource levelling problem. J. Oper. Res. Soc. 64 (2012) 1071–1078. | DOI
, Graphes et ordonnancements. Revue Francaise de Recherche Operationelle 25 (1962) 323–326.
, , and , Solving the optimal power flow problem via a non-interior path following algorithm. J. Comput Inf. Syst. 9 (2013) 1191–1198.
, , and , The orderly colored longest path problema survey of applications and new algorithms. RAIRO: OR 48 (2014) 25–51. | DOI | Numdam | MR | Zbl
, Four float measures for critical path scheduling. J. Ind. Eng. 10 (1969) 19–23.
, and , A dynamic traveling salesman problem with stochastic arc costs. Oper. Res. 62 (2014) 1107–1125. | DOI | MR | Zbl
and , Depth-based short-sighted stochastic shortest path problems. Artif. Intell. 216 (2014) 179–205. | DOI | MR | Zbl
and , Criticality analysis in activity-on-node networks with Minimal time lags. Ann. Oper. Res. 102 (2001) 17–37. | DOI | MR | Zbl
W. Van Loock, S. Bellens, G. Pipeleers, J. De Schutter and J. Swevers, Time-optimal parking and flying: Solving path following problems efficiently. In: 2013 IEEE International Conference on. Mechatronics (ICM). IEEE (2013) 841–846.
, Precedence diagramming method: Some unusual characteristics and their implications for project managers. J. Oper. Manage. 1 (1981) 121–130. | DOI
and , Computing latest starting times of activities in interval-valued networks with minimal time lags. Eur. J. Oper. Res. 200 (2010) 874–880. | DOI | Zbl
and , A robust GA-based QoS routing algorithm for solving multi-constrained path problem. J. Comput. 5 (2010) 1322–1334. | DOI
, and , Solving bi-objective flow shop problem with hybrid path relinking algorithm. Appl. Soft Comput. 13 (2013) 4118–4132. | DOI
, , and , Minimum cuts and maximum flows in directed planer networks with both node and edge capacities. Chinese J. Comput. 29 (2006) 544–551. | MR
, , , , and , A biologically inspired optimization algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. J. Optim. Theory Appl. 163 (2014) 1049–1056. | DOI | MR | Zbl
, and , Improved strategy for resource allocation in repetitive projects considering the learning effect. J. Constr. Eng. Manage. 140 (2014) 04014053. | DOI
and , Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price. Comput. Oper. Res. 40 (2013) 385–394. | DOI | MR | Zbl
Cité par Sources :
