This work studies a combinatorial optimization problem encountered in industrial production planning: the single-item multi-resource lot-sizing problem with inventory bounds and lost sales. The demand to be satisfied by the production plan is subject to uncertainty and only probabilistically known. We consider a multi-stage decision process with a Decision–Hazard–Decision information structure in which decisions are made at each stage both before and after the uncertainty is revealed. Such a setting has not yet been studied for stochastic lot-sizing problems, and the resulting problem is modeled as a multi-stage stochastic integer program. We propose a solution approach based on an approximate stochastic dynamic programming algorithm. It relies on a decomposition of the problem into single-stage sub-problems and on the estimation at each stage of the expected future costs. Due to the Decision–Hazard–Decision information structure, each nested single-stage sub-problem is itself a two-stage stochastic integer program. We therefore introduce a Benders decomposition scheme to reduce the computational effort required to solve each nested sub-problem, and present a special-purpose polynomial-time algorithm to efficiently solve the single-scenario second-stage sub-problems involved in the Benders decomposition. The results of extensive simulation experiments carried out on large-size randomly generated instances are reported. They demonstrate the practical benefit, in terms of the actual production cost, of using the proposed approach as compared to a naive deterministic optimization approach based on the expected demand.

Abstract A min‐sum controllable risk problem, defined on a given set of elements or on combinatorial structures, which are either paths of a directed acyclic graph or spanning trees of an undirected graph, with resource‐dependent risk functions of the elements, is studied. The resource amount is limited, and the objective is to distribute it between the selected elements or elements of the selected structure so that the total risk is minimized. A reduction to a series of easier problems is suggested. Solution approaches based on this reduction are asymptotically faster than the solution approaches suggested in the literature for special cases of this problem.

We focus on one of the simple assembly line balancing problems known as SALBP-2 which consists in assigning a set of elementary operations V = {1, 2, ... , n} to the m linearly ordered stations with respect to the precedence constraints and aims in minimizing the line cycle time c. The processing times of operations tj, j ¿ V may vary during the life cycle of assembly line for manual operations (represented by set V¿ ) and be fixed for automated operations (set V \ V¿ ). The goal of this paper is to derive necessary and sufficient condition (so-called qualitative analysis) of the stability of an optimal balance found for a given vector of operations times t = (t1, t2, ... , tn) with regard to possible independent perturbations of the processing times of the operations from set .