賴聰乾2006-07-252018-06-292006-07-252018-06-292002http://ntur.lib.ntu.edu.tw//handle/246246/3064本計畫探討情況惡化下且工作間有先後順序關係下之單機排序問題。 在 情況惡化下，一工作之處理時間與該工作何時開始處理有關且愈等待愈長。本 計畫證明，如果先後順序關係乃一鏈狀結構、一樹狀結構、一森林結構、或一串- 並列結構，該問題可可在多項式時間內求解。在一般性之結構下，證明該問題係 一NP-難度問題，但如果處理時間呈等比例關係，則該問題之求解時間為二次式。This research project considers the single machine sequencing in the presence of precedence relations under deteriorating situations with an objective to minimize the makespan. In a deteriorating situation, the processing time of a job is not only increasing while waiting but also dependent on the time at which the job begins processing. It is proved that the problem can be solved in polynomial time when precedence constraints are in the form of a set of chains, a tree, a forest or series-parallel graph. The general case, when precedence constraints are given by arbitrary directed a-cyclic graph and processing times are linear, is proven to be NP-hard. It is also shown that if in the latter case the processing times are proportional functions, the problem can be solved in quadratic time.application/pdf114109 bytesapplication/pdfzh-TW國立臺灣大學工商管理學系單機排序情況惡化先後順序關係作業全程複雜度NP-難度可多項式時間內求解最佳演算法single machinesequencingdeteriorating situationsprecedence relationsmakespancomplexityNP-hardpolynomial solvableoptimal algorithmsreporthttp://ntur.lib.ntu.edu.tw/bitstream/246246/3064/1/902416H002029.pdf