情況惡化下受限於先後順序關係之單機排序

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.