We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A branch-and-price approach for the stochastic generalized assignment problem.
- Authors
Sarin, Subhash C.; Sherali, Hanif D.; Kim, Seon Ki
- Abstract
In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch-and-price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method-one that utilizes a dual-stabilization technique and another that incorporates an advanced-start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch-and-cut (B&C) method within CPLEX. Our results show that all B&P-based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the 'true' optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10-fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131-143, 2014
- Subjects
STOCHASTIC programming; INTEGER programming; MONTE Carlo method; MATHEMATICAL models; NUMERICAL calculations; GAMES of chance; MATHEMATICAL variables
- Publication
Naval Research Logistics, 2014, Vol 61, Issue 2, p131
- ISSN
0894-069X
- Publication type
Article
- DOI
10.1002/nav.21571