作業管理若干最適化問題之預先處理
Date Issued
2000
Date
2000
Author(s)
賴聰乾
DOI
892416H002039
Abstract
We introduce a new class of yes-no decision problems to preprocess an
optimization problem in which each cost coefficient in the objective function can
assume any value between a lower and upper bound. This new yet rich class of
decision problems arises naturally in real-world scenarios, poses new challenges and
demands new types of solution techniques. In the first part we establish NP-completeness
results for some problems in this class. We also establish some general
results for this new class of problems. In the second part we present ten problems
(examples) among this new class of problems along with their polynomial-time
algorithms to demonstrate some types of new solution techniques for those that are
polynomially solvable. These ten problems arising in operations management include
matroid, network optimization, sequencing, and location.
Subjects
Optimization
Operations Management
Preprocessing
Polynomially Solvable
Publisher
臺北市：國立臺灣大學工商管理學系
Type
report
File(s)![Thumbnail Image]()
Loading...
Name
892416H002039.pdf
Size
17.95 KB
Format
Adobe PDF
Checksum
(MD5):f62133c74df1f0db36db0ba7d05a1acb