Suchergebnisse

AbstractThe job‐shop scheduling problem is a large‐scale combinatorial problem of great practical significance. First, a discussion of the size of the combinatorial problem involved will be given. Then, the various methods of attacks for solving this problem will be discussed and criticized by the use of examples. These methods include principally the integral linear programming, the heuristic, the loading rule, the simulation, and the Monte Carlo methods. The latter method, in the form devised by Giffler and Thompson, will be described in detail, and some computational results will he presented.

AbstractWe consider the transportation problem of determining nonnegative shipments from a set of m warehouses with given availabilities to a set of n markets with given requirements. Three objectives are defined for each solution: (i) total cost, TC, (ii) bottleneck time, BT (i.e., maximum transportation time for a positive shipment), and (iii) bottleneck shipment, SB (i.e., total shipment over routes with bottleneck time). An algorithm is given for determining all efficient (pareto‐optimal or nondominated) (TC, BT) solution pairs. The special case of this algorithm when all the unit cost coefficients are zero is shown to be the same as the algorithms for minimizing BT. provided by Szwarc and Hammer. This algorithm for minimizing BT is shown to be computationally superior. Transportation or assignment problems with m=n=100 average about a second on the UNIVAC 1108 computer (FORTRAN V)) to the threshold algorithm for minimizing BT. The algorithm is then extended to provide not only all the efficient (TC, BT) solution pairs but also, for each such BT, all the efficient (TC, SB) solution pairs. The algorithms are based on the cost operator theory of parametric programming for the transportation problem developed by the authors.

AbstractThis paper investigates the effect on the optimum solution of a capacitated generalized transportation problem when any coefficient of any row constraint is continuously varied as a linear function of a single parameter. The entire analysis is divided into three parts. Results are derived relative to the cases when the coefficient under consideration is associated, to a cell where the optimal solution in that cell attains its lower bound or its upper bound. The discussion relative to the case when the coefficient under consideration is associated to a cell in the optimal basis is given in two parts. The first part deals with the primal changes of the optimal solution while the second part is concerned with the dual changes. It is shown that the optimal cost varies in a nonlinear fashion when the coefficient changes linearly in certain cases. The discussion in this paper is limited to basis‐preserving operators for which the changes in the data are such that the optimum bases are preserved. Relevant algorithms and illustrations are provided throughout the paper.

AbstractThis paper investigates the effect on the optimum solution of a capacitated generalized transportation problem when certain data of the problem are continuously varied as a linear function of a single parameter. First the rim conditions, then the cost coefficients, and finally the cell upper bounds are varied parametrically and the effect on the optimal solution, the associated change in costs and the dual changes are derived. Finally the effect of simultaneous changes in both cost coefficients and rim conditions are investigated. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum bases are preserved.

AbstractThis paper considers a logistics system modelled as a transportation problem with a linear cost structure and lower bounds on supply from each origin and to each destination. We provide an algorithm for obtaining the growth path of such a system, i. e., determining the optimum shipment patterns and supply levels from origins and to destinations, when the total volume handled in the system is increased. Extensions of the procedure for the case when the costs of supplying are convex and piecewise linear and for solving transportation problems that are not in "standard form" are discussed. A procedure is provided for determining optimal plant capacities when the market requirements have prespecified growth rates. A goal programming growth model where the minimum requirements are treated as goals rather than as absolute requirements is also formulated.

AbstractThis paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions‐i. e., the warehouse supplies and market demands‐the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. An operator theory is developed and algorithms provided for applying rim and cost operators that effect the transformation of optimum solution associated with changes in rim conditions and unit costs. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum basis structures are preserved.

AbstractThis paper describes a computer program that uses simple rules and applies them probabilistically to minimize manpower requirements in shops of a naval shipyard. Preliminary runs on a small fictitious problem show that this "multiship, multishop, workload‐smoothing" program, called (MS)2, may be able to reduce the maximum number of men required on any one day by 30 to 60 percent.The program employs the critical path method of analyzing the jobs to be done on a given project (ship) and begins by assigning all jobs at their earliest possible start time. Then suitable jobs on peak workload days are selected at random and shifted to later days beyond the peak days until further shifting no longer reduces peak loads. The first segment of the program smooths the workloads on all shops simultaneously. After the first segment is completed the second segment performs further smoothing on individual shops, beginning with the most expensive shop.Although a limited amount of experience has been gained with this program, it appears likely that it can be developed further so that it can handle realistic‐sized problems such as those encountered in a Naval Shipyard. Moreover, it can be applied on three levels: (1) smoothing shop workloads in a shipyard; (2) smoothing the workloads of individual shops; and (3) smoothing shipyard workloads.