We analyze a stochastic model of a production line with k stations (machines) in series. There are finite-capacity buffers between the machines and at the end of the line. The movement of the workpieces through the li...
详细信息
We analyze a stochastic model of a production line with k stations (machines) in series. There are finite-capacity buffers between the machines and at the end of the line. The movement of the workpieces through the line is demand-driven, i.e. we deal with a pull (kanban) production system. Processing times are assumed to be deterministic and constant. There are two sources of randomness in the model: Demand for workpieces from outside is stochastic, and the machines may break down (and then be repaired) with a given probability. A demand from outside is lost if the final buffer is empty. This system is described by a discrete-time Markov chain. The steady-state distribution is given for k = 1. This is the basis of a decomposition algorithm which approximates the throughput of the line and the percentage of satisfied demand for arbitrary k. A comparison with simulation results shows that this algorithm is very accurate.
We study the static load balancing in a distributed computer system that consists of a set of heterogeneous host computers interconnected by a tree network with two-way traffic. The static load balancing problem is fo...
详细信息
We study the static load balancing in a distributed computer system that consists of a set of heterogeneous host computers interconnected by a tree network with two-way traffic. The static load balancing problem is formulated as a nonlinear optimization problem. We demonstrate that the particular structure of the optimization problem can be solved by a decomposition technique. An algorithm is developed to obtain the optimal solution. The proposed algorithm is compared with other two well known algorithms: the FD (Flow Deviation) algorithm and the Dafermos algorithm. It is shown that the proposed algorithm requires less storage and spends the least computation time to converge to the optimal solution.
Berck and Bible (1984) have suggested a solution approach for harvest scheduling problems based on the Dantzig-Wolfe (1960) decomposition algorithm. We first expose the fact that the area constraints in their problem ...
详细信息
Berck and Bible (1984) have suggested a solution approach for harvest scheduling problems based on the Dantzig-Wolfe (1960) decomposition algorithm. We first expose the fact that the area constraints in their problem possess a network structure, requiring the solution of a single longest path problem, and show that the elegant closed-form solution derived by Berck and Bible is precisely a readily obtained longest path solution. Moreover, we show that when additonal variable bounds are imposed, the network structure remains exploitable. Second, we compare the computational effort and storage requirements of the Dantzig-Wolfe algorithm and the revised simplex method for solving this problem. The slow tail-end convergence of the Dantzig-Wolfe approach is of particular concern. However, we provide operational guidelines showing when this procedure may be preferred. Other viable algorithms suitable for solving this problem are also discussed.
A primal–dual decomposition method is presented to solve the separable convex programming problem. Convergence to a solution and Lagrange multiplier vector occurs from an arbitrary starting point. The method is equiv...
详细信息
A primal–dual decomposition method is presented to solve the separable convex programming problem. Convergence to a solution and Lagrange multiplier vector occurs from an arbitrary starting point. The method is equivalent to the proximal point algorithm applied to a certain maximal monotone multifunction. In the nonseparable case, it specializes to a known method, the proximal method of multipliers. Conditions are provided which guarantee linear convergence.
In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. Th...
详细信息
The paper represents an algorithm for the estimation of multivariate ARMA models. A orthogonalization procedure proposed by Phadke enables a decomposition of the extremely high dimensional estimation problem in subpro...
详细信息
The paper represents an algorithm for the estimation of multivariate ARMA models. A orthogonalization procedure proposed by Phadke enables a decomposition of the extremely high dimensional estimation problem in subproblems of lower dimensions. Some problems of this method resulting in difficulties in its practical use are discussed. By means of a further decomposition in subproblems with maximal two inputs and one output and by an appropriate prefiltering the whole estimation problems splits in relatively simple, more practicable parts. The resulting successive determination of the submodels is especially effective in a direct dialog with the computer.
This paper describes a general concept and a particular optimization algorithm for solving a class of large-scale nonlinear programming problems with a nested block-angular structured system of linear constraints with...
详细信息
This paper describes a general concept and a particular optimization algorithm for solving a class of large-scale nonlinear programming problems with a nested block-angular structured system of linear constraints with coupling variables. A primal optimization algorithm is developed, which is based on the recursive application of the partitioning concept to the nested structure in combination with a feasible directions method. The special column by column application of this partitioning concept finally leads to a very clear and efficient algorithm for nested problems, which is called ‘successive partitioning method’. It is shown that the reduced-gradient method can be represented as a special application of the concept.
Kronsjö's nonlinear generalization (Ref. 1) of Benders' algorithm (Ref. 2) is reviewed. At each iteration, this algorithm produces upper and lower bounds to the true optimum, and the sequence of lower bou...
详细信息
Kronsjö's nonlinear generalization (Ref. 1) of Benders' algorithm (Ref. 2) is reviewed. At each iteration, this algorithm produces upper and lower bounds to the true optimum, and the sequence of lower bounds is increasing. The algorithm is modified, so that the sequence of upper bounds is ε-decreasing as well. The two versions are tested numerically using an ALGOL program originally written by Wong (Ref. 3), incorporating the SUMT method (Fiacco and McCormick, Refs. 4 and 5). The two versions are compared against each other, and the problem of the optimal degree of decomposition is considered. Finally, an attempt is made to express the computer time required to solve the test problems as a function of master problem size, number of subproblems, and average subproblem size.
An algorithm for obtaining simple disjunctive decompositions of fuzzy functions is described. The insufficiency of Boolean methods for simplification of fuzzy functions is discussed. Special properties of the decompos...
详细信息
An algorithm for obtaining simple disjunctive decompositions of fuzzy functions is described. The insufficiency of Boolean methods for simplification of fuzzy functions is discussed. Special properties of the decomposed fuzzy structures are introduced and their relationships to two-valued logic are investigated. This new algorithm is the first one in a containing research in the area of multivalued and fuzzy decompositions of complex systems.
暂无评论