情況惡化下受限於先後順序關係之單機排序
Other Title
Single Machine Sequencing under Deteriorating Situations
with Precedence Relations
with Precedence Relations
Date Issued
2002
Date
2002
Author(s)
賴聰乾
DOI
902416H002029
Abstract
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.
Subjects
single machine
sequencing
deteriorating situations
precedence relations
makespan
complexity
NP-hard
polynomial solvable
optimal algorithms
Publisher
臺北市：國立臺灣大學工商管理學系
Type
report
File(s)![Thumbnail Image]()
Loading...
Name
902416H002029.pdf
Size
111.43 KB
Format
Adobe PDF
Checksum
(MD5):7c7bbc487f7d1010b5fe7baedd538e84