A branch‐and‐price approach for the stochastic generalized assignment problem. (31st January 2014)

• Record Type: Journal Article
• Authors: Sarin, Subhash C.; Sherali, Hanif D.; Kim, Seon Ki
• Is Part Of: Naval research logistics. Volume 61:Number 2(2014:Mar.)
• Page Start: 131
• Page End: 143
• Publication Date: 2014-01-31
• Subjects: Logistics, Naval -- Periodicals; Supplies and stores -- Periodicals; 359.07
• DOI: 10.1002/nav.21571
• Languages: English
• ISSNs: 0894-069X

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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&amp;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&amp;C) method within CPLEX. Our results show that all B&amp;P‐based approaches perform better than the B&amp;C method, with the best performance obtained for the B&amp;P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&amp;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&amp;P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014</p> </abstract>