摘要:

AbstractThis paper presents algorithms for finding exact and approximate solutions for the weighted feedback are set problem, determining a minimum‐cardinality set of ares that breaks all cycles in a directed graph. This is also the problem of finding a group rank ordering given the rank orders for each member of a group. The algorithms have many other applications. Mathematically, the problem is that of finding a permutation matrixPthat maximizes the sum of the elements above the principal diagonal ofP1WPwhereWis a skew‐symmetric matrix of ordern.This is a special case of the Koopmans‐Beckmann quadratic assignment problem. Computational experience is reported for a sample of randomly generated problems, including comparisons with results obtained using algorithms three other authors have developed for solving the more general quadratic assignment problem. For our sample, using randomly generated problems, the computational time required for calculating all exact solutions for each problem is approximatelyT(n)=c2.232n, wherec= 9.8764E‐ 6 andT(20) = 93 s for the Cray X‐MP/48 supercomputer. For our sample, the computational time required for calculating one approximate solution is approximatelyT(n)=an4,1, wherea= 3.0361E‐ 8 andT(250) = 206 s f

ISSN:0028-3045    

DOI:10.1002/net.3230200102

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractThe rotating workforce scheduling problem involves the construction of an efficient sequence of work and rest periods spanning over a number of weeks. This schedule must satisfy the workforce requirements during the different shifts of each day and conform to all the other conditions imposed on the work/rest periods and their sequence. We consider the modeling of the rotating workforce scheduling problem as a network flow problem. All the constraints on the problem are incorporated in the network itself, except for the staff‐covering constraints that are treated as side constraints. The optimal solution to the problem corresponds to a path in the network and is identified using a dual‐based approach. The model deals with the issues of rest‐period identification, work/rest period sequencing, and shift schedulingsimultaneouslyand is designed to handle multiple shift cases with time‐varying demands. The procedure, which is capable of solving large‐scale problems, is applied to three well‐known problems in rotating workforce scheduling. The computational results presented indicate that this procedure provides a useful method for solving large‐scale complex problems in workfor

ISSN:0028-3045    

DOI:10.1002/net.3230200103

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractFor any directed graphGwith node‐setV(G), we present anO([V(G)]3)algorithm that finds a partitionPofV(G)into directed paths and an independent setIof nodes, such that |P=|I| The existence of such aPandIis the Gallai‐Milgrm theorem. WhereGis transitive and acyclic, the well‐known Dilworth theorem that min |P| = max |I| follows immediately. WhereGis bipartitite and every edge ofGis directed from node‐setUto node‐setV, Pcorresponds to a largest mat

ISSN:0028-3045    

DOI:10.1002/net.3230200104

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractThis paper gives a tail routing algorithm that meets a flight schedule with a minimum number of aircraft. The flight segments are identical from period to period and form a partially ordered set. The algorithm takes advantage of the periodic nature of the schedule to reduce the problem size. For a domestic airline whose schedule is identical each week, one may solve two problems, each with a seven and one half day time horizon instead of one larger problem over the entire time horizon which may be several months.

ISSN:0028-3045    

DOI:10.1002/net.3230200105

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractWe consider the problem of covering a weighted graphG = (V, E) by a set of vertex‐disjoint paths, such that the total weight of these paths is maximized. This problem is clearly NP‐complete, since it contains the Hamiltonian path problem as a special case. Three approximation algorithms for this problem are presented, exhibiting a complexity‐performance trade‐off. First, we develop an algorithm for covering undirected graphs. The time complexity of this algorithm isO(|E|log|E|), and its performance‐ratio is ½. Second, we present an algorithm for covering undirected graphs, whose performance‐ratio is ⅔. This algorithm uses a maximum weight matching algorithm as a subroutine, which dominates the overall complexity of our algorithm. Finally, we develop an algorithm for covering directed graphs, whose performanceratio is ⅔. This algorithm uses a maximum weight bipartite matching algorithm as a subroutine, which dominates the overall complexity

ISSN:0028-3045    

DOI:10.1002/net.3230200106

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractThe reliability for communication in a directed network can be expressed as a summation of terms, each of which involves a success‐marginal probability, that is, the probability of an event of the form {the arcs in setSare working}. Satyanarayana and Prabhakar introduced the concept of domination in order to characterize the coefficients of one such expression. This paper observes that domination can be interpreted as a partial derivative of the reliability multinomial and extends results derived for domination to the general class of expressions involving success‐marginal probabilit

ISSN:0028-3045    

DOI:10.1002/net.3230200107

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractStalling in the simplex algorithm is defined as an exponentially long sequence of consecutive degenerate pivots without cycling. Pivot rules for the network simplex algorithm that prevent both cycling and stalling are considered. For several of these, the number of consecutive degenerate pivots is shown to be at mostk(k+ 1)/2, wherekis the number of degenerate basic variables. The relationship between these pivot rules for the network simplex algorithm and strongly polynomial simplex variants for solving the shortest path problem is also discussed.

ISSN:0028-3045    

DOI:10.1002/net.3230200108

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractIt is required to interconnectnexisting networks in the plane by new links of minimal total length. We assume that the edges of the networks are straight and that it is possible to make connections along the edges or to the vertices. The use o f Steiner points is also allowed. Though the theoretical number of solutions to the problem is uncountable, we prove that it is enough to consider a finite set of locally optimal solutions with a limit on the number of connections along edges. This makes it possible to solve the problem in finite time by methods similar to those used for the Euclidean Steiner tree problem. The problem can be generalized to include flow‐dependent costs for the various link

ISSN:0028-3045    

DOI:10.1002/net.3230200109

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractWe improve the time and space complexities of dynamic programming algorithms that compute optimal Steiner trees spanning nodes in planar networks. Our algorithms have special application to the rectilinear Steiner problem.

ISSN:0028-3045    

DOI:10.1002/net.3230200110

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230200101

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY