A generalized bi-criteria fuzzy integer flow sharing problem

The flow sharing problem is a class of techniques that can be used to find the optimal flow in a capacitated network, which realizes an equitable distribution of flows. This paper extends the integer flow sharing problem by considering fuzzy capacities and fuzzy weights such that the flux received at each sink node and the flow value through each arc are restricted to be multiples of some block unit. Fuzzy capacity describes the flexibility of the upper limit of flow value through each arc. Fuzzy weight represents the degree of satisfaction of the flux to a sink node. Our model has the two following criteria: to maximize the minimal degree of satisfaction among all of the fuzzy capacity constraints and to maximize the minimal degree of satisfaction among the fluxes to all of the sink nodes. Because an optimal flow pattern that simultaneously maximizes the two objectives is usually not feasible, we define non-domination in this setting and propose a pseudo-polynomial algorithm that finds some non-dominated flow patterns. Finally, a numerical example is presented to demonstrate how our algorithm works.     

The quickest flow problem

Consider a network =(G, c, ) whereG=(N, A) is a directed graph andc _ij and _ij , respectively, denote the capacity and the transmission time of arc (i, j) A. The quickest flow problem is then to determine for a given value the minimum numberT() of time units that are necessary to transmit (send) units of flow in from a given sources to a given sinks.In this paper we show that the quickest flow problem is closely related to the maximum dynamic flow problem and to linear fractional programming problems. Based on these relationships we develop several polynomial algorithms and a strongly polynomial algorithm for the quickest flow problem.Finally we report computational results on the practical behaviour of our metholds. It turns out that some of them are practically very efficient and well-suited for solving large problem instances.Partial financial support by the Air Force Office of Scientific Research under grants AFOSR-89-0512 and AFOSR-90-0008 is gratefully acknowledged by the first author.     

The equal flow problem

This paper presents a new algorithm for the solution of a network problem with equal flow side constraints. The solution technique is motivated by the desire to exploit the special structure of the side constraints and to maintain as much of the characteristics of pure network problems as possible. The proposed algorithm makes use of Lagrangean relaxation to obtain a lower bound and decomposition by right-hand-side allocation to obtain upper bounds. The lagrangean dual serves not only to provide a lower bound used to assist in termination criteria for the upper bound, but also allows an initial allocation of equal flows for the upper bound. The algorithm has been tested on problems with up to 1500 nodes and 6000 arcs. Computational experience indicates that solutions whose objective function value is well within 1% of the optimum can be obtained in 1%–65% of the MPSX time depending on the amount of imbalance inherent in the problem. Incumbent integer solutions which are within 99.99% feasible and well within 1% of the proven lower bound are obtained in a straightforward manner requiring, on the average, 30% of the MPSX time required to obtain a linear optimum.     

The hub covering flow problem

The hub covering flow problem (HCFP) seeks to find the minimal cost hub-and-spoke network by optimally locating hub nodes and assigning non-hub nodes to the hub nodes subject to a coverage constraint. The cost of establishing such a hub network is based on a fixed cost of opening hubs and the cost of transporting demand flow through the network. We also present an extension called the multi-aircraft HCFP. The results from computational experiments are presented and discussed.     

The inverse maximum dynamic flow problem

We consider the inverse maximum dynamic flow (IMDF) problem. IMDF problem can be described as: how to change the capacity vector of a dynamic network as little as possible so that a given feasible dynamic flow becomes a maximum dynamic flow. After discussing some characteristics of this problem, it is converted to a constrained minimum dynamic cut problem. Then an efficient algorithm which uses two maximum dynamic flow algorithms is proposed to solve the problem.     

The hybrid flow shop scheduling problem

The scheduling of flow shops with multiple parallel machines per stage, usually referred to as the hybrid flow shop (HFS), is a complex combinatorial problem encountered in many real world applications. Given its importance and complexity, the HFS problem has been intensively studied. This paper presents a literature review on exact, heuristic and metaheuristic methods that have been proposed for its solution. The paper briefly discusses and reviews several variants of the HFS problem, each in turn considering different assumptions, constraints and objective functions. Research opportunities in HFS are also discussed.     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

Some results on the entire function sharing problem

Our main result is as follows: let f and a be two entire functions such that \(\max \{ \rho _2 (f),\rho _2 (a)\} < \tfrac{1} {2}\) . If f and f ^(k) a CM, and if ρ(a ^(k) ? a) < ρ(f ? a), then f ^(k) ? a = c(f ? a) for some nonzero constant c. This result is applied to improve a result of Gundersen and Yang.     

Approaches to sharing knowledge in group problem structuring

Problem-structuring techniques are an integral aspect of ‘Soft-OR’. SSM, SAST, Strategic Choice, and JOURNEY Making, all depend for their success on a group developing a shared view of a problem through some form of explicit modelling. The negotiated problem structure becomes the basis for problem resolution. Implicit to this process is an assumption that members of the group share and build their knowledge about the problem domain. This paper explores the extent to which this assumption is reasonable. The research is based on detailed records from the use of JOURNEY Making, where it has used special purpose Group Support software to aid the group problem structuring. This software continuously tracks the contributions of each member of the group and thus the extent to which they appear to be ‘connecting’ and augmenting their own knowledge with that of other members of the group. Software records of problem resolution in real organisational settings are used to explore the sharing of knowledge among senior managers. These explorations suggest a typology of knowledge sharing. The implications of this typology for problem structuring and an agenda for future research are considered.     

Uniqueness problem of meromorphic functions sharing small functions

In this paper, a uniqueness theorem of meromorphic functions which share four small functions is given.

     

Multicommodity flow problem

The problem of nonmixing multicommodity flow is investigated. The theorem on the number of nonmixing flows of different commodities passing simultaneously through an oriented network is proved.Translated from Dinamicheskie Sistemy, No. 5, pp. 95–97, 1986.     

The two-machine total completion time flow shop problem

In this paper we study the NP-hard scheduling problem of minimizing total completion time in a two-machine flow shop. Five known lower bounds are discussed and two new ones are presented. A new dominance criterion is also proposed. Several versions of a branch and bound method are derived by applying, both individually and combined, these lower bounds. A heuristic procedure is also presented that uses a constructive O(n²) time method, which computes a good starting solution, together with a neighborhood search based on pairwise interchanges. Computational results show that the exact method can handle problems of up to 30 jobs in size within a reasonable amount of time and that the heuristic procedure has an average error of less than 0.5% from the optimal value and less than 2.7% from the lower bound.     

The fractional minimal cost flow problem on network

A problem and a new algorithm are given for the linear fractional minimal cost flow problem on network. Using a new check number and combining the characteristic of network to extend the traditional theories of minimum cost flow problem, discussed the relation between it and its dual problem. Optimality conditions are derived and a Network Simplex Algorithm is proposed that leads to optimal solution assuming certain properties. Finally, an numerical example test is also developed.     

The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

Bike sharing systems: Solving the static rebalancing problem

This paper deals with a new problem that is a generalization of the many to many pickup and delivery problem and which is motivated by operating self-service bike sharing systems. There is only one commodity, initially distributed among the vertices of a graph, and a capacitated single vehicle aims to redistribute the commodity in order to reach a target distribution. Each vertex can be visited several times and also can be used as a buffer in which the commodity is stored for a later visit. This problem is NP-hard, since it contains several NP-hard problems as special cases (the TSP being maybe the most obvious one). Even finding a tractable exact formulation remains problematic.This paper presents efficient algorithms for solving instances of reasonable size, and contains several theoretical results related to these algorithms. A branch-and-cut algorithm is proposed for solving a relaxation of the problem. An upper bound of the optimal solution of the problem is obtained by a tabu search, which is based on some theoretical properties of the solution, once fixed the sequence of the visited vertices. The possibility of using the information provided by the relaxation receives a special attention, both from a theoretical and a practical point of view. It is proven that to build a feasible solution of the problem by using the one obtained by the relaxation is an NP-hard problem. Nevertheless, a tabu search initialized with the optimal solution of the relaxation often shows that it is the optimal one.The algorithms have been tested on a set of instances coming from the literature, proving their effectiveness.     

Inverse minimum flow problem

In this paper we consider the inverse minimum flow (ImF) problem, where lower and upper bounds for the flow must be changed as little as possible so that a given feasible flow becomes a minimum flow. A linear time and space method to decide if the problem has solution is presented. Strongly and weakly polynomial algorithms for solving the ImF problem are proposed. Some particular cases are studied and a numerical example is given.     

The maximum integer multiterminal flow problem in directed graphs

Given an arc-capacitated digraph and k terminal vertices, the directed maximum integer multiterminal flow problem is to route the maximum number of flow units between the terminals. We introduce a new parameter k_L?k for this problem and study its complexity with respect to k_L.