Search

The paper presents a new approach to solving a class of combinatorial economic allocation problems. One member of this class is known as the quadratic assignment problem. Besides presenting an algorithm to solve this problem, we will discuss in general terms the techniques for treating combinatorial problems. A novel feature of the paper is the development of the statistical properties of the criterion function. These statistical properties are used in conjunction with a general enumerative procedure to form the main parts of the algorithm. Using the idea of confidence level enumeration, an extension of the algorithm is proposed which should allow for the effective treatment of large scale combinatorial problems. Finally we present some computational results in order to illustrate the effectiveness of the general approach. [ABSTRACT FROM AUTHOR]

This paper brings together two topics from regression analysis. One is the topic of stepwise regression, a set of commonly used procedures for exploring alternative formulations of the regression model. The other topic is regression by minimizing the sum of the absolute errors about the regression line (MSAE). This technique has been found, in a variety of circumstances, to be more attractive than the traditional least-squares method. The paper presents a procedure for selecting from among m regressors the best sets of k, k-1, ... and m regressors according to the MSAE criterion (k This character cannot be converted in ASCII text) m). Building upon the well known linear-programming formulation of the MSAE problem, the paper develops a partial enumerative search scheme, in which a set of distinct, but related, combinatorial optimization problems (corresponding to determination of 'best k,' 'best k+1,' etc.) are, in effect, solved simultaneously. [ABSTRACT FROM AUTHOR]

Status consistency research has been severely criticized for its inability to reconcile certain problems of theory and method. As the validity of these criticisms has become evident, researchers have turned from classic research designs to more powerful methods. One popular approach has incorporated typological procedures based on two-factor profiles of status inconsistents. In this paper, a serious fault of the two-factor technique is delineated, and the analysis of differences between types is shown to be without substance. Researchers are provided with a simple procedure for avoiding this pitfall before research is initiated, and elementary combinatorial analysis is utilized to derive a proper procedure. Two research designs, a 2 × 4 and a 3 × 4, receive special attention because of their popularity and complexity, respectively. [ABSTRACT FROM AUTHOR]

Heuristic algorithms have frequently been developed in the attempt to solve combinatorial problems such as those that frequently exist in plant-layout planning, sequencing, scheduling, and routing situations. In these algorithms there has been no basis available to evaluate the progress of the heuristic results in relation to an optimum. This paper outlines and provides examples of the application of extreme value distributions and, more particularly, the Weibull distribution as mechanisms for estimating optimum limits. Given such estimates, the paper further illustrates the development of decision rules applicable to the decision of continuing or halting the heuristic analysis. [ABSTRACT FROM AUTHOR]

This paper models satellite communications systems by means of bipartite graphs. It assumes stochastic inputs and time delay is the factor of interest. The paper formulates the model and describes the routing and digital transmission schemes, assuming the network links to be synchronized. Messages may be transmitted only in the synchronized time slots, on a first-come first-served basis. The queuing problem is discussed for the single branch and for the satellite network cases, and approximate solutions are obtained for the case of satellites with finite memories. [ABSTRACT FROM AUTHOR]

This paper develops the steady-state solution for the queuing system with s parallel servers when arrivals are serviced in batches of size Q. The service time for all servers is exponentially distributed and the customer inter arrival times are Erlantan of degree u. [ABSTRACT FROM AUTHOR]

This paper extends the work of White and Christie, reported in OPERATION RESEARCH, vol 6, pp 79-95 (January-February, 1958), on preemptive priority queuing. A random walk procedure yields recursive relations between the state probabilities in the steady state. Recursive relations for the moments of the length of the lower priority queue follow. Combined with the use of moment generating functions, this approach provides moments of the waiting time for elements of the lower priority class that arrive when the system is in a given state, i e, the two queues are of given lengths. The moments of waiting time and time in the system are also obtained recursively for the steady state Routines for computing and checking are provided. [ABSTRACT FROM AUTHOR]

Many people have proposed objective functions, or optimizers, which guide one to schedule a multi-product single stage production system. In this paper we present a whole new class of optimizers, or solution concepts, which generalizes most of the well-known optimizers to date. Our combinatoric formulations are related to a new class of solution concepts for n-person games developed by Charnes-Kortsnek. By constructing a combinatoric linear programming problem, where some of the variables are determined by an arbitrary set of permutations, we encompass classical optimizers in one formulation including such concepts as (1) minimizing maximum lateness or tardiness, (2) maximizing minimum lateness or tardiness, (3) minimizing mean lateness or flow time, and (4) random sequencing. More generally, we characterize a new class of optimizers as optimal solutions to specially constructed combinatoric programming problems, including optimizers which are integer in character. [ABSTRACT FROM AUTHOR]

As interest grows rapidly in industry on the potentialities of mathematical programming techniques, it appears worthwhile to have a paper devoted to some of the more promoting developments which may speed up the transition from interest to use. Three topics have been selected (in three sections that follow) which have recently come into prominence: uncertainty, combinatorial problems, and large scale systems. The reader will find in the course of their dissensions that a survey--though perhaps not a systematic survey--has been made of current techniques in the linear programming field. [ABSTRACT FROM AUTHOR]

This paper presents an implicit enumeration algorithm for redrawing school attendance boundaries in order to meet integration requirements. The basis of the approach is the division of the city into smaller areas or zones corresponding to neighborhoods. These zones are assigned to schools with the objective of minimizing the required bussing while meeting the school capacity and racial mix constraints. An entire zone is assigned to one school, thus preserving the neighborhood school concept. Viewing the possible zone-school assignments as a combinatorial problem, a general enumerative procedure is combined with probability theory to form the implicit enumeration algorithm. An explanation of the algorithm along with computational results of an application of the method to an existing school system is presented. [ABSTRACT FROM AUTHOR]

This paper is concerned with the relation between 0–1 integer programs and graphs. An equivalence is established between solving 0–1 integer programs with quadratic or linear objective functions and solving a cut problem on a related graph. [ABSTRACT FROM AUTHOR]

This paper analyzes a Markovian queing system with balking and two heterogeneous servers determines the capacity of the slower server and obtains the optimal service rates that minimize the average characteristics of the heterogeneous system. The heterogeneous system is compared with a corresponding homogeneous system and a condition showing the efficiency of the heterogeneous system is obtained, this condition revolving only the traffic intensity and the service rates. A cost model is discussed and various tables and graphs representing the average characteristics of both the systems are given. [ABSTRACT FROM AUTHOR]

Let G be a directed graph such that ever5 edge v of G is associated with a positive integer, called the index of v. Then G is called a network graph if, at every vertex t of G, the sum of the indices of the edges terminating at v is equal to that of the edges incident from v. This paper obtains several theorems giving necessary and sufficient conditions for a directed graph to be a network graph, and applied the results to solving some problems of smoothing traffic flow. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm that will yield the minimum make-span sequence for n-jobs requiring processing through M-machines when no passing is allowed. Theoretical development utilizing combinatorial analysis and proof of sequence optimality precedes the algorithm and an example problem. [ABSTRACT FROM AUTHOR]

In this paper two sequencing problems are investigated that arise in the course of allocating one or more constrained resources to two or more tasks. The general problem considered is one of determining the optimal sequence of tasks and the optimal scheduling of resource usage where the objective is to minimize the time by which all tasks are completed. The fundamental solution technique utilized involves a combination of dynamic programming and combinatorial analysis techniques. In the single resource case the two problems are shown to be graphical `duals' of each other thereby allowing an iterative solution to the second problem. [ABSTRACT FROM AUTHOR]

In this paper the method of generating functions is applied to a queue where the moments of arrival follow a Poisson distribution, but where at each of these moments several persons may arrive simultaneously. Assuming an Erlang distribution for the service times and first-come first- served discipline for the arriving groups, explicit formulas are obtained for the limiting values of the mean number of persons in the queue and in the system, and the mean time that a group of persons who arrive together must wait before one of them is served. [ABSTRACT FROM AUTHOR]

This paper presents a study of several aspects of the theory of car queues. In it we consider a situation in which there is traffic on a main highway and a queue of cars on a side road waiting to merge. First we consider a case in which the lead driver chooses to merge on the basis of whether the gap in main highway traffic exceeds a service time that is chosen from a probability density. An expression for the generating function of the steady-state distribution and the waiting-time distribution are derived. Secondly, the critical input to the side road is determined such that for all larger inputs the queue is transient. In particular we consider the effect of the move up time (of the second car in a queue) on this parameter. Finally, we present the results of a study by simulation techniques for the analysis of traffic queuing models. A discussion of the use of importance sampling in improving simulation studies is given, and a comparison made between theoretical and simulation results. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm that will yield an optimum sequence for n jobs requiring processing through M machines when no passing is allowed. Theoretical development utilizing combinatorial analysis precedes the algorithm and an example problem. [ABSTRACT FROM AUTHOR]

Existing theoretical and empirical evidence indicates that, except for small samples, the null and non-null distributions of the variance ratios involved in the analysis of the randomized block design, based upon normal theory agree reasonably well with those under permutation theory. The present paper investigated the combined effect of block-treatment interaction and block-variance heterogeneity upon this agreement. Using a normal theory alpha cut-off point, the empirical probability of type I error under a permutation basis was markedly reduced by this combination of factors, and empirical power was also reduced. Additionally, the combined effect of kurtosis and block-variance heterogeneity was studied. The results indicated that kurtosis of the basic data had negligible effect upon either the null or non-null distribution of the variance ratios involved. [ABSTRACT FROM AUTHOR]

In a preceding paper Jacobsen [3] shows that marginal allocation solves a class of discrete, single constraint, min-max allocation problems. A dual approach to this problem is presented, based on a generalization of Jacobsen's P condition, which should prove more efficient when many marginal improvement iterations would be required. A variant of sequential search by bisection is applied, possibly augmented by an accelerated marginal allocation scheme, in which finite convergence to an optimum solution is guaranteed. [ABSTRACT FROM AUTHOR]

The uses of regression analysis to estimate market yield curves for U. S. Government securities are considered in this paper. Several possible regression models for this purpose are examined. It is found that models which regress either the before-tax yield or the after-tax yield of governments on the number of days remaining to maturity and the square of the logarithm of the number of days remaining to maturity can fruitfully be applied to actual market data in determining yield curves. [ABSTRACT FROM AUTHOR]

A wide variety of branch and bound algorithms have recently been described in the literature. This paper provides a generalized description of such algorithms. An objective is to demonstrate the wide applicability of branch and bound to combinatorial problems in general. Two existing algorithms are used as illustrations and a discussion of computational efficiency is included. [ABSTRACT FROM AUTHOR]

This paper discusses the problem of assigning locations to indivisible facilities and its relation to the quadratic assignment problem. It also develops two suboptimal algorithms, one dealing with the general quadratic assignment problem and the other with an interesting special case. Qualitative and quantitative comparisons with existing suboptimal algorithms are presented. [ABSTRACT FROM AUTHOR]

This article informs that in a crossover design it is possible that certain differential effects will become evident in the course of the study. Although the group levels are equal to begin with, they may become unequal after one or more treatments have been given because of the appearance of a differential residual effect among the treatments. Furthermore, the effect of treatments may depend on the sequence of previous treatments in such a way as to produce a differential carryover effect. In the case of two treatments, only two treatment permutations are possible. This design has been discussed in the article in some detail because of its use in periodontal studies involving a placebo and an active compound.

Hillier has described a method of selecting offsets to minimize delay in certain networks controlled by fixed-time signals. In this paper an attempt is made to extend the method by relaxing somewhat the restriction on the form of the network. The problem is expressed in terms of the theory of graphs, and an iterative process is developed for finding a set of offsets that minimizes delay over the whole network. At each stage, the part of the network already covered is extended by adding one or more links, and for the method to be viable these links must be chosen so that a certain set of intersections remains small. A method of selection of links that minimizes this set of intersections at each stage is developed. The selection of links and calculation of offsets have been programmed in Fortran. Having found one delay-minimizing set of offsets, some others that give the same total delay can be found if they exist. [ABSTRACT FROM AUTHOR]

Dealt with in this paper is the analysis of phenomena involving simultaneous responses among members of small groups during a finite number of discrete time intervals. An exact combinatorial test obtained by conditioning on the sufficient statistics under a null hypothesis is proposed. A specific application of this test is given for the analysis of asthma attack data of asthmatic individuals. [ABSTRACT FROM AUTHOR]

This article focuses on the applicability of mathematical theory of graphs in sports sociology. The studies presented in this paper might have demonstrated that methods of graph theory can be, to the advantage of the exactness and conceptualization of structural properties and factors, successfully employed in sport sociology. A sport sociologist cannot dispense with this instrument anymore, if he does not want to deprive himself of possibilities to give his models and theory a precise formulation. But not only a better means of presentation is at stake here; in fact, certain connections, properties and statements, generally understood as empirical ones, turn out be structural-mathematical consequences of the model itself that can be revealed as statements of such a logico-mathematical category only by the employment of graph theory. There is another argument, confirming the usefulness of wider employment of graph theory in sociology of sport: in three very distinct branches of this scientific discipline the following structures and methods of the same theory of graphs can be successfully applied: in the analysis of sports organizations, in investigations of round-robin matches, and in studies on the group dynamics of teams.

The article cites a study which examines the frequency of error obtain in a test. The purpose of the study was to find out how often errors exist in various combinations and how the combinations organized. The study was based on the data collected by the researchers in the grammar schools in San Jose California regarding the reliability of the standard score as a measure of additional ability. The errors of the 238 papers coming from the students in the investigation was studied and analyzed. Tabulation method was used in the listing of error. The result indicates that there was an erratic distribution in one or two distributions and that the number of errors increases as the number of combination increases.

This paper studies the transient behavior of a first-come-first-served queuing problem with service in batches of variable size, Poisson input, and exponential service time distribution. Further, when the queue length increases to N, a fixed pre-assigned positive number, a special service channel capable of serving a group of N units and possessing exponential service time distribution is made available and is canceled at the termination of service if the queue length becomes less than N. Also a limited waiting space K is assumed for the waiting line. The Laplace transforms of various probability generating functions are obtained and the corresponding results for the steady state are derived. Finally, some particular cases are discussed. [ABSTRACT FROM AUTHOR]

Several authors, including MORSE, ANCKER AND GAFARIAN, and COX AND SMITH have studied single-server queuing models in which the arrival rate is a decreasing function of queue length. This paper analyzes a multiserver generalization of the model given by Cox and Smith. A generating function is derived for the equilibrium distribution of queue length, and from it are derived expressions for the probability of finding all servers busy on arrival, and for the mean number of customers in the system and waiting for service to begin. Also, an expression is obtained for the proportional loss in custom caused by discouragement. Finally, the distribution of waiting time is obtained using characteristic functions and the mean waiting time is calculated. The variations of these quantities with traffic intensity and number of servers are illustrated graphically. [ABSTRACT FROM AUTHOR]

Problem-solving procedures based on the methods of combinatorial programming are presented for solving a class of integer programming problems in which all elements are zero or one. All of the procedures seek first a feasible solution and then successively better and better feasible solutions until ultimately one is discovered which is shown to be optimal. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problemsolving process, a number of problems involving several hundred integer variables have been solved in a matter of seconds. [ABSTRACT FROM AUTHOR]

A simplified description of a new computing procedure for the Hitchcock- Koopmans transportation problem is given, together with a step by step solution of an illustrative example. The procedure is based on Kuhn's combinatorial algorithm for the assignment problem and a simple "labeling process" for solving maximal flow problems in networks. The proposed computation appears to be considerably more efficient than the specialized form of the simplex method which is in common use. [ABSTRACT FROM AUTHOR]

The article deals with a study which determined when and to what extent can the cost of an alternative project substitute for or provide limits to benefit measurement. The paper arranges to set up what appears to be a very limited model in which researchers consider two governmental projects and two private projects. The study assumes about the right alternatives, compatible project combinations, correct institutional rules to govern the selection of projects and what quantities and qualities of services are provided by individual projects.

The scientist, who has observed in his research that the event "S" was followed by the event "B" or that the class of events "S" was followed by the events belonging to the class B, may formulate on the basis of such findings two different types of conclusions: he may simply assert that in his population or on a much larger scale "S" is followed by "B;" he may also say that in his population or on a much broader scale "S" is the cause of "B," or-in other terms "B is the effect of "S." between all these notions. Both philosophers and research workers seem to agree on the operational definition of causal relation, namely that the causal connections between the events are those connections which under conditions of a controlled experiment lead to the observable sequences of events "S" and "B" prescribed by the given design of the experiment. As researcher know, the experimental manipulations of variables preceding in time a given effect "B" permit them to obtain such combinations of variables characterizing the initial conditions for the given effect "B," which are hardly obtainable and observable in natural situations.

This paper is a report of further analysis of small group data secured in a 1950 field project. The consistent regularities displayed by the series of distributions of free-forming small group size suggested the possibility that the empirical distributions could be fitted by a statistical model and thereby converted to more general form. Free-forming small groups are those whose members are relatively free to maintain or break off contact with one another, that is, they are ones where informal controls on behavior are at work and spontaneity is at a maximum. Field observations were conducted in Eugene and Portland, Oregon in the winter and spring, 1950 in the course of which 15,486 observations of free-forming small groups were made and arranged by type of group, place and time in 18 empirical distributions. A further word may be said about the differential chi-square results of the negative binomial and Poisson fittings. It would be expected therefore, that this model would fit those distributions deriving from social situations where the relationships governing the combinations of individuals were relatively stable.

This paper deals with a model in which Poisson events in fixed time periods are recorded with probability a and left to accumulate into the succeeding period with probability 1-α. The distribution of number of events recorded is obtained, together with its mean, variance, and generating function. [ABSTRACT FROM AUTHOR]

Many factors can contribute—independently or in combination—to seam flammability; i.e., fiber chemistry, fiber/thread geometry, thread tension, seam type, flammability of the base fabric, etc. This report cites a number of these factors and discusses results obtained in studying various combinations of four fabrics and five threads in plain seams stitched with both lockstitch and overedge. Burning behavior is described and some general conclusions drawn. [ABSTRACT FROM AUTHOR]

In the context of analyzing social structures through the use of graph theory, some binary matrix operations for valued graphs are presented. These operations are demonstrated in the analysis of social network data presented by Kapferer. Further examples of where the procedures should prove useful are suggested. [ABSTRACT FROM AUTHOR]

This note shows the general utility of this fundamental queuing relation by exploiting the basic premise used in its proof Weighted time in system averages are related to similarly weighted system-count averages. The implications of the result for simulation use are explained. [ABSTRACT FROM AUTHOR]

The concept of a median in a weighted graph is generalized to a multi- median. Then, it is shown that the optimum distribution of p switching centers in a communication network is at a p-median of the corresponding weighted graph. The following related problem in highway networks is also considered: What is a minimum number of policemen that can be distributed in a highway network so that no one is farther away from a policeman than a given distanced? This problem is attacked by generating all vertex-coverings (externally stable sets) of a graph by means of a Boolean function defined over the vertices of a graph. Then this idea is extended to Boolean functions that generate all matchings, all factors, and all pos- sible subgraphs of G with given degrees. [ABSTRACT FROM AUTHOR]

The crude Monte Carlo method is inefficient when searching for extreme points since it uses none of the information gained from earlier samples. If the possible situations are the permutations of a number of items, a method called Chain Monte Carlo is suggested that needs a measure of distance between two permutations. Examples are given and in some scheduling problems substantial savings in computation are observed. [ABSTRACT FROM AUTHOR]

Use is made of the Laplace transform to study the two-dimensional preemptive priority queuing problem with exponential arrival and service times The method of generating functions is used to solve the difference equations so obtained In the section "The Differential-Difference Equations for the System" the transform of the generating function of the queuing process is given and the moments of the distribution of the nonpriority queue length derived from this An explicit solution is given only for the case of equal service rates, the general case requiring only additional calculation The distribution of the length of a busy period for the nonpriority queue is studied later [ABSTRACT FROM AUTHOR]

An apparently combinatorial problem is defined, and a method given for solution by reduction to a network flow problem. The basic problem defined is that of assessing the desirability of incurring a number of fixed costs, when the benefits to be obtained cannot be related to individual cost-incurring items (facilities) but only to combinations. [ABSTRACT FROM AUTHOR]

"But we can't agree whether A or B is correct,' he concluded, 'and so we're collecting expert opinions, weighting them appropriately, and programming WESCAC to arbitrate the whole question.' " (John Barth, Giles Goat-Boy, p. 664.) In the Bayesian framework, quantified judgments about uncertainty are an indispensable input to methods of statistical inference and decision. If a decision maker has little knowledge with regard to the parameters of interest, he may decide to consult a number of experts and obtain their quantified judgements in the form of subjective probability distributions. If this is the case, the decision maker must somehow combine the distributions assessed by the experts and form a single distribution to be used as an input to a formal Bayesian analysis. Several methods for combining the distributions are suggested, some involving mathematical formulae and some involving feedback and/or group discussion. These methods are compared under certain assumptions regarding the form of the distributions and also under experimental conditions. [ABSTRACT FROM AUTHOR]

A branch and bound algorithm for solution of the "knapsack problem," max Σ v[sub i],x[sub i] where Σ w[sub i]x[sub i] ≤ W and x[sub i] = 0, 1, is presented which can obtain either optimal or approximate solutions. Some characteristics of the algorithm are discussed and computational experience is present. Problems involving 50 items from which approximately 25 items were loaded were solved in an average of 0.07 minutes each by a coded version of this algorithm for the IBM 7094 computer. [ABSTRACT FROM AUTHOR]