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

Talal M. Alkhamis

doi:10.1016/j.cor.2011.01.017

Return

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

2011-12-01

PRE

Talal M. Alkhamis *

Rym M’Hallah

DOI：10.1016/j.cor.2011.01.017

Original

Original request for help

Save

Abstract

En 中文

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. (C) 2011 Elsevier Ltd. All rights reserved.

Keywords:

Parallel machine scheduling

Weighted number of on-time jobs

Stochastic programming

Ranking and selection

Average sample approximation

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.