摘要
证明了可变费用的单机等待损失排序问题１‖Σｆ＿ｉ（ｃ＿ｉ）是ＮＰ－ｈａｒｄ；给出了一般情形下工件优先安排加工的两个判别条件；对几种特殊情形给出了多项式时间算法或最优解的判定条件。
This paper is concerned with a single machine scheding problem of minimizingweighted completion times in which the weights can be variable.We first prove that theproblem is NP-hard， and then present some precedence criteria and polynomial algorithmsfor special cases.
出处
《河南科学》
1994年第3期173-180,共8页
Henan Science
关键词
单台机器排序
等待损失费用
排序
Single machine scheduling Weighted completion time Complexity precedence criteria.
