A two‐stage stochastic programming model for the parallel machine scheduling problem with machine capacity

This paper proposes a two‐stage stochastic programming model for the parallel machine scheduling problem where the objective is to determine the machines' capacities that maximize the expected net profit of on‐time jobs when the due dates are uncertain. The stochastic model decomposes the problem into two stages: The first (FS) determines the optimal capacities of the machines whereas the second (SS) computes an estimate of the expected profit of the on‐time jobs for given machines' capacities. For a given sample of due dates, SS reduces to the deterministic parallel weighted number of on‐time jobs problem which can be solved using the efficient branch and bound of M’Hallah and Bulfin . FS is tackled using a sample average approximation (SAA) sampling approach which iteratively solves the problem for a number of random samples of due dates. SAA converges to the optimum in the expected sense as the sample size increases. In this implementation, SAA applies a ranking and selection procedure to obtain a good estimate of the expected profit with a reduced number of random samples. Extensive computational experiments show the efficacy of the stochastic model.