The lower bounded and partial upper bounded distribution model

This paper pruvides a smaller equivalelnt bounded variable transportation problem than that in Charnes, Glover, and Klingman [1] for the lower bounded and partial upper bounded distribution model.     

Linear search with bounded resources

A point is placed at random on the real line according to some known distribution F, and a search is made for this point, beginning at some starting points s on the line, and moving along the line according to some function x(t). The objective of this article is to maximize the probability of finding the point while traveling at most d units. Characterizations of simple optimal searches are found for arbitrary distributions, for continuous distributions with continuous density everywhere (e.g., normal, Cauchy, triangular), and for continuous distributions with density which is continuous on its support (e.g., exponential, uniform). These optimal searches are also shown to be optimal for maximization of the expected number of points found if the points are placed on the line independently from a known distribution F.     

The bounded interval generalized assignment model

The bounded interval generalized assignment model is a “many-for-one” assignment model. Each task must be assigned to exactly one agent; however, each agent can be assigned multiple tasks as long as the agent resource consumed by performing the assigned tasks falls within a specified interval. The bounded interval generalized assignment model is formulated, and an algorithm for its solution is developed. Algorithms for the bounded interval versions of the semiassignment model and sources-to-uses transportation model are also discussed.     

Convergence of the bounded fixed charge programming problem

Calculating the solution for a mixed integer linear programming problem has been problematic for any sizable dimension because of the time required. Accordingly, an improved method for the fixed charge problem is presented here. The method is a modification of a bounding technique first suggested by Balinski, and it exploits fully the ratio of costio-use, first described by Cooper and Drebes. It exploits those local properties which have global application so that enumeration is confined to those relatively few combinations which cannot be evaluated otherwise.     

Parametric analysis of linear programs with upper bounded variables

Linear programming problems with upper bounded variables can be solved by regular simplex method by considering upper bounding constraints as explicit constraints of the problem. However, more efficient methods exist which consider these upper bound constraints implicitly. When parametric analysis for problems with upper bounds is to be carried out, one can use the regular parameter analysis by considering the upper bound constraints explicitly. This paper develops formulas for parametric analysis where upper bound constraints are used implicitly, thus reducing the size of the basic matrix.     

A general treatment of upper unbounded and bounded hitchcock problems

This paper is designed to treat (a) the problem of the determination of the absolute minimum cost, with the associated assignments, when there is no limit, N, on the number of parcels available for shipment in a modified Hitchcock problem. This is accomplished with the use of a transformed cost matrix. C*, to which the so-called transportation paradox does not apply. The general Hitchcock solution using C* gives the cost T*, which is the absolute minimum cost of the original problem, as well as sets of assignments which are readily transformed to give the general assignments of the original problem. The sum of these latter assignments gives the value of N_u, the unbounded N for minimum cost. In addition, this paper is designed to show (b) how the method of reduced matrices may be used, (c) how a particular Hitchcock solution can be used to determine a general solution so that one solution using C* can provide the general answer, (d) how the results may be modified to apply to problems with fixed N, and hence (e) to determine the function of the decreasing T as N approaches N_u, and finally (f) to provide a treatment when the supplies at origin i and/or the demands at destination j, are bounded.     

Equivalent knapsack-type formulations of bounded integer linear programs: An alternative approach

In this paper we show that every bounded integer linear program can be transformed into an integer program involving one single linear constraint and upper and lower bounds on the variables, such that the solution space of the original problem coincides with that one of the equivalent knapsack-type problem.     

A bounded dual (all-integer) integer programming algorithm with an objective cut

In this article, we describe a new algorithm for solving all-integer, integer programming problems. We generate upper bounds on the decision variables, and use these bounds to create an advanced starting point for a dual all-integer cutting plane algorithm. In addition, we use a constraint derived from the objective function to speed progress toward the optimal solution. Our basic vehicle is the dual all-integer algorithm of Gomory, but we incorporate certain row- and column-selection criteria which partially avoid the problem of dual-degenerate iterations. We present the results of computational testing.     

Determining optimal sizes of bounded batches with rejection via quadratic min‐cost flow

In this article, we consider a single machine scheduling problem, in which identical jobs are split into batches of bounded sizes. For each batch, it is allowed to produce less jobs than a given upper bound, that is, some jobs in a batch can be rejected, in which case a penalty is paid for each rejected job. The objective function is the sum of several components, including the sum of the completion times, total delivery cost, and total rejection cost. We reduce this problem to a min‐cost flow problem with a convex quadratic function and adapt Tamir's algorithm for its solution. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 217–224, 2017     

Cyclic scheduling in robotic flowshops with bounded work‐in‐process levels

This study addresses cyclic scheduling in robotic flowshops with bounded work‐in‐process (WIP) levels. The objective is to minimize the cycle time or, equivalently, to maximize the throughput, under the condition that the WIP level is bounded from above by a given integer number. We present several strongly polynomial algorithms for the 2‐cyclic robotic flowshop scheduling problems for various WIP levels. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 1–16, 2011