大葉大學圖書館 |

Resource constrained assignment problems with flexible customer demand.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Resource constrained assignment problems with flexible customer demand.
Author:	Rainwater, Chase E.
Description:	198 p.
Notes:	Source: Dissertation Abstracts International, Volume: 70-12, Section: B, page: 7780.
Contained By:	Dissertation Abstracts International70-12B.
Subject:	Engineering, Industrial.
Subject:	Operations Research.
ISBN:	9781109519174
[NT 15000229]:	This dissertation considers classes of problems that seek to make profitable demand fulfillment decisions with limited available resources. This general problem scenario has been given much consideration over recent decades. In this work, we add to this body of research by considering less explored problem variants that allow decision makers to exploit demand flexibility to increase profit. We first consider a generalization of the capacitated facility location with single-sourcing constraints. Each customer must be assigned to a procured facility, and the level at which the customer's demand is fulfilled (a decision variable) must be determined, subject to falling within pre-specified limits. A customer's revenue is nondecreasing in its resource consumption, according to a general revenue function, and a fixed cost is incurred for each resource procured. We provide an exact branch-and-price algorithm that solves both this problem and a special case in which resource procurement is not considered. Our approach identifies an equally interesting class of pricing subproblems. We discuss how this class of problems can be solved with generalized revenue functions and offer efficient algorithms for solving instances with specially structured revenue functions that correspond to common pricing structures. Our extensive computational study compares the performance of our exact algorithm to that of well-known commercial solvers and demonstrates the advantages of our algorithmic approach for various categories of problem instances. Since real-world scenarios often result in large-scale problem sizes, we consider novel heuristic approaches for both the generalization of the capacitated facility location problem and a particular special case, which can be viewed as an extension of the well-known Generalized Assignment Problem (GAP). We first develop a class of heuristic solution methods for the variant without resource procurement decisions. Our approach is motivated by a rigorous study of the linear relaxation of the model. We show that our class of heuristics is asymptotic optimality in a probabilistic sense under a broad stochastic model. Improvement procedures are discussed and a thorough computational study confirms our theoretical results. We then provide fast and practically implementable optimization-based heuristic solution methods for the generalized class of facility location problems with resource procurement decisions. Our procedure is designed for very large-scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems. Finally, we consider a separate class of assignment problems with non-linear resource consumption and non-traditional capacity constraints. The model is applicable to manufacturing scenarios in which products with common production characteristics share setup times or some element of fixed resource consumption. The additional capacity constraints account for real-world restrictions that may result from environmental guidelines, transportation resource limitations, or limited warehouse storage space. We propose a branch-and-price algorithm for this class of problems that requires a unique reformulation of our problem, as well as a study of a new class of knapsack problems. A computational study demonstrates the appeal of our approach over commercial solvers for various problem instances.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3385984

Resource constrained assignment problems with flexible customer demand.
Rainwater, Chase E.

Resource constrained assignment problems with flexible customer demand. - 198 p.

Source: Dissertation Abstracts International, Volume: 70-12, Section: B, page: 7780.

Thesis (Ph.D.)--University of Florida, 2009.

This dissertation considers classes of problems that seek to make profitable demand fulfillment decisions with limited available resources. This general problem scenario has been given much consideration over recent decades. In this work, we add to this body of research by considering less explored problem variants that allow decision makers to exploit demand flexibility to increase profit. We first consider a generalization of the capacitated facility location with single-sourcing constraints. Each customer must be assigned to a procured facility, and the level at which the customer's demand is fulfilled (a decision variable) must be determined, subject to falling within pre-specified limits. A customer's revenue is nondecreasing in its resource consumption, according to a general revenue function, and a fixed cost is incurred for each resource procured. We provide an exact branch-and-price algorithm that solves both this problem and a special case in which resource procurement is not considered. Our approach identifies an equally interesting class of pricing subproblems. We discuss how this class of problems can be solved with generalized revenue functions and offer efficient algorithms for solving instances with specially structured revenue functions that correspond to common pricing structures. Our extensive computational study compares the performance of our exact algorithm to that of well-known commercial solvers and demonstrates the advantages of our algorithmic approach for various categories of problem instances. Since real-world scenarios often result in large-scale problem sizes, we consider novel heuristic approaches for both the generalization of the capacitated facility location problem and a particular special case, which can be viewed as an extension of the well-known Generalized Assignment Problem (GAP). We first develop a class of heuristic solution methods for the variant without resource procurement decisions. Our approach is motivated by a rigorous study of the linear relaxation of the model. We show that our class of heuristics is asymptotic optimality in a probabilistic sense under a broad stochastic model. Improvement procedures are discussed and a thorough computational study confirms our theoretical results. We then provide fast and practically implementable optimization-based heuristic solution methods for the generalized class of facility location problems with resource procurement decisions. Our procedure is designed for very large-scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems. Finally, we consider a separate class of assignment problems with non-linear resource consumption and non-traditional capacity constraints. The model is applicable to manufacturing scenarios in which products with common production characteristics share setup times or some element of fixed resource consumption. The additional capacity constraints account for real-world restrictions that may result from environmental guidelines, transportation resource limitations, or limited warehouse storage space. We propose a branch-and-price algorithm for this class of problems that requires a unique reformulation of our problem, as well as a study of a new class of knapsack problems. A computational study demonstrates the appeal of our approach over commercial solvers for various problem instances.

ISBN: 9781109519174Subjects--Topical Terms:

423093
Engineering, Industrial.

Resource constrained assignment problems with flexible customer demand.
LDR:04840nam 2200289 4500 001 345058
005 20110620110224.5
008 110817s2009 ||||||||||||||||| ||eng d
020 $a 9781109519174
035 $a (UMI)AAI3385984
035 $a AAI3385984
040 $a UMI $c UMI
100 1 $a Rainwater, Chase E. $3 423516
245 1 0 $a Resource constrained assignment problems with flexible customer demand.
300 $a 198 p.
500 $a Source: Dissertation Abstracts International, Volume: 70-12, Section: B, page: 7780.
500 $a Advisers: Joseph P. Geunes; H. Edwin Romeijn.
502 $a Thesis (Ph.D.)--University of Florida, 2009.
520 $a This dissertation considers classes of problems that seek to make profitable demand fulfillment decisions with limited available resources. This general problem scenario has been given much consideration over recent decades. In this work, we add to this body of research by considering less explored problem variants that allow decision makers to exploit demand flexibility to increase profit. We first consider a generalization of the capacitated facility location with single-sourcing constraints. Each customer must be assigned to a procured facility, and the level at which the customer's demand is fulfilled (a decision variable) must be determined, subject to falling within pre-specified limits. A customer's revenue is nondecreasing in its resource consumption, according to a general revenue function, and a fixed cost is incurred for each resource procured. We provide an exact branch-and-price algorithm that solves both this problem and a special case in which resource procurement is not considered. Our approach identifies an equally interesting class of pricing subproblems. We discuss how this class of problems can be solved with generalized revenue functions and offer efficient algorithms for solving instances with specially structured revenue functions that correspond to common pricing structures. Our extensive computational study compares the performance of our exact algorithm to that of well-known commercial solvers and demonstrates the advantages of our algorithmic approach for various categories of problem instances. Since real-world scenarios often result in large-scale problem sizes, we consider novel heuristic approaches for both the generalization of the capacitated facility location problem and a particular special case, which can be viewed as an extension of the well-known Generalized Assignment Problem (GAP). We first develop a class of heuristic solution methods for the variant without resource procurement decisions. Our approach is motivated by a rigorous study of the linear relaxation of the model. We show that our class of heuristics is asymptotic optimality in a probabilistic sense under a broad stochastic model. Improvement procedures are discussed and a thorough computational study confirms our theoretical results. We then provide fast and practically implementable optimization-based heuristic solution methods for the generalized class of facility location problems with resource procurement decisions. Our procedure is designed for very large-scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems. Finally, we consider a separate class of assignment problems with non-linear resource consumption and non-traditional capacity constraints. The model is applicable to manufacturing scenarios in which products with common production characteristics share setup times or some element of fixed resource consumption. The additional capacity constraints account for real-world restrictions that may result from environmental guidelines, transportation resource limitations, or limited warehouse storage space. We propose a branch-and-price algorithm for this class of problems that requires a unique reformulation of our problem, as well as a study of a new class of knapsack problems. A computational study demonstrates the appeal of our approach over commercial solvers for various problem instances.
590 $a School code: 0070.
650 4 $a Engineering, Industrial. $3 423093
650 4 $a Operations Research. $3 423094
690 $a 0546
690 $a 0796
710 2 $a University of Florida. $3 423388
773 0 $t Dissertation Abstracts International $g 70-12B.
790 1 0 $a Geunes, Joseph P., $e advisor
790 1 0 $a Romeijn, H. Edwin, $e advisor
790 $a 0070
791 $a Ph.D.
792 $a 2009
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3385984