可变费用的单机等待损失排序问题  

A SINGLE MACHINE SCHEDULING PROBLEM WITH VARIABLE WEIGHTS

作　　者：王敏娟[1] 邓俊强[1] 林诒勋 

机构地区：[1]郑州大学系统科学与数学系

出　　处：《河南科学》1994年第3期173-180,共8页Henan Science

摘　　要：证明了可变费用的单机等待损失排序问题１‖Σｆ＿ｉ（ｃ＿ｉ）是ＮＰ－ｈａｒｄ；给出了一般情形下工件优先安排加工的两个判别条件；对几种特殊情形给出了多项式时间算法或最优解的判定条件。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.

关 键 词：单台机器排序 等待损失费用 排序 

分 类 号：O223[理学—运筹学与控制论]