A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity |
| |
Authors: | Talal Al-Khamis,Rym M&rsquo Hallah |
| |
Affiliation: | Department of Statistics and Operations Research, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait |
| |
Abstract: | 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 [16]. 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. |
| |
Keywords: | Parallel machine scheduling Weighted number of on-time jobs Stochastic programming Ranking and selection Average sample approximation |
本文献已被 ScienceDirect 等数据库收录! |