0000000000073267
AUTHOR
Paweł Zieliński
The computational complexity of the relative robust shortest path problem with interval data
Abstract The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.
Criticality in the Network with Imprecise Activity Times
A review of the results obtained in the area of fuzzy network analysis is presented. The main approaches to the concept of criticality in a network with fuzzy activity times are described and classified. Against the background of this review some new results, obtained by the authors recently, are presented. The paper is an extended version of the work presented in IPMU'2000 (see [8]).
Ranking fuzzy interval numbers in the setting of random sets – further results
Abstract We present some new properties of several fuzzy order relations, defined on the set of fuzzy numbers, from among those introduced in [S. Chanas, M. Delgado, J.L. Verdegay, M.A. Vila, Information Sciences 69 (1993) 201–217]. The main result is proving that four from among the relations considered in [S. Chanas, M. Delgado, J.L. Verdegay, M.A. Vila, Information Sciences 69 (1993) 201–217] are strongly transitive (s-transitive).
On the equivalence of two optimization methods for fuzzy linear programming problems
Abstract The paper analyses the linear programming problem with fuzzy coefficients in the objective function. The set of nondominated (ND) solutions with respect to an assumed fuzzy preference relation, according to Orlovsky's concept, is supposed to be the solution of the problem. Special attention is paid to unfuzzy nondominated (UND) solutions (the solutions which are nondominated to the degree one). The main results of the paper are sufficient conditions on a fuzzy preference relation allowing to reduce the problem of determining UND solutions to that of determining the optimal solutions of a classical linear programming problem. These solutions can thus be determined by means of classi…
On the sure criticality of tasks in activity networks with imprecise durations
BB; International audience; The notion of the necessary criticality (both with respect to path and to activity) of a network with imprecisely defined (by means of intervals or fuzzy intervals) activity duration times is introduced and analyzed. It is shown, in the interval case, that both the problem of asserting whether a given path is necessarily critical and the problem of determining an arbitrary necessarily critical path (more exactly, a subnetwork covering all the necessarily critical. paths) are easy. The corresponding solution algorithms are proposed. However, the problem. of evaluating whether a given activity is necessarily critical does not seem to be such. Certain conditions are…
The computational complexity of the criticality problems in a network with interval activity times
Abstract The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.
On the hardness of evaluating criticality of activities in a planar network with duration intervals
Complexity results for problems of evaluating the criticality of activities in planar networks with duration time intervals are presented. We show that the problems of asserting whether an activity is possibly critical, and of computing bounds on the float of an activity in these networks are NP-complete and NP-hard, respectively.
Critical path analysis in the network with fuzzy activity times
A natural generalization of the criticality notion in a network with fuzzy activity times is given. It consists in direct application of the extension principle of Zadeh to the notion of criticality of a path (an activity, an event) treated as a function of the activities duration times in the network. There are shown some relations between the notion of fuzzy criticality, introduced in the paper, and the notion of interval criticality (criticality in the network with interval activity times) proposed by the authors in another paper. Two methods of calculation of the path degree of criticality (according to the proposed concept of fuzzy criticality) are presented.