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

详细信息    查看全文

• 作者：Talal Al-Khamis ; ^a ; ^{alkhamis@kuc01.kuniv.edu.kw"" rel=""nofollow} ; Rym M’ ; Hallah^a
• 关键词：Parallel machine scheduling ; Weighted number of on-time jobs ; Stochastic programming ; Ranking and selection ; Average sample approximation
• 刊名：Computers and Operations Research
• 出版年：2011
• 出版时间：December 2011
• 年：2011
• 卷：38
• 期：12
• 页码：1747-1759
• 全文大小：1078 K

文摘

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.