https://scholars.lib.ntu.edu.tw/handle/123456789/98985
標題: | 作業管理若干最適化問題之預先處理 | 作者: | 賴聰乾 | 關鍵字: | 最適化;作業管理;預先處理;NP-complete;可於多項式時間內解答;Optimization;Operations Management;Preprocessing;Polynomially Solvable | 公開日期: | 2000 | 出版社: | 臺北市:國立臺灣大學工商管理學系 | 摘要: | 作者與 Professor James Orlin (MIT) 共同引進一類新問題用來預先處理一 最適化問題,其中該最適化問題目標函數之成本係數的值可落於一上下界區間. 該類問題來自於實際情境,提出新的挑戰,並要求新的求解技巧. 第一部分結 果包含證明若干該類問題係NP-complete 並包括若干該類問題之一般性結果. 第二部分針對十個問題(例子)分別提出可於多項式時間內解答之演算出.這十個 問題來自於作業管理:包含matroid, 網路最適化, 排序, 位置選擇. 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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/3042 | 其他識別: | 892416H002039 | Rights: | 國立臺灣大學工商管理學系 |
顯示於: | 工商管理學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
892416H002039.pdf | 17.95 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。