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

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 {∑ni=1∑xik=0aik ≥ H} ≤ β, is shown to be different in substance from the classical case, Pr{∑ni=1a′ixi ≤ H} ≥ β, where xi denotes the variable of the program and aik 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.