Chance Constrained Programming of the Machine Loading Problem with Stochastic Processing Times

Abstract

The statistical model of a chance constrained variable which is the sum of stochastically independent random variables is considered, using the machine loading problem as an expository case. The resulting chance constrained statement, Pr {∑ n i =1 ∑ x i k =0 a ik ≥ H } ≤ β, is shown to be different in substance from the classical case, Pr{∑ n i =1 a ′ i x i ≤ H } ≥ β, where x i denotes the variable of the program and a ik and a ′ i denote the random variables. A formal mathematical analysis is carried out on the deterministic equivalent nonlinear problem with solutions over a set that may be nonconvex. The mathematical results are then used in stating and evaluating a linear approximation, thus enabling one to state the problem using a generalized transportation problem formulation.