具有传递时间变工时的单机排序问题

作     者：周贤伟 姜俊 

作者机构：郑州高炮学院河南省科学院 

出 版 物：《河南科学》 (Henan Science)

年 卷 期：1995年第13卷第3期

页      面：194-198页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主　　题：单机排序 变工时 传递时间 排序 

摘      要：确定了具有传递时间变工时的单机排序问题是ＮＰ─完全的，且讨论了它的一些特殊情况。）（ｉ＿０）＝π￣＊（ｎ－１），定义π￣（）如下：显然有ｆ（π￣＊）≥ｆ（π￣（）），对于π￣（）的证明同情况１类似。由上面讨论知π＇不比π￣＊差，即目标函数值下降。将工件Ｊ＿（ｊ０）从Ｊ中划去，重复（２）－（４）步，由于每一步目标函数值都下降，至多有限步可使目标函数值得到最优，即算法产生一最优解。算法的时间复杂性估计：该算法至多循环ｎ步，每一步中求工件ｊ＿０可用Ｏ（ｎｌｏｇｎ）时间，由此总的计算量为Ｏ（ｎ￣２ｌｏｇｎ）。由此算法说明问题１｜α＿ｉＰ＿ｉ，Ｐ＿ｊ＝１，ｄｅｌｉｖｅｒｙｔｉｍｅｓ｜ｍａｘ（Ｗ＿ｊＣ＿ｊ＋ｑ＿ｊ）是具有多项式时间可解的，即所谓Ｐ问题。定理３．３就问题１｜α＿ｉＰ＿ｉ，Ｐ＿ｊ＝１，ｄｅｌｉｖｅｒｙｔｉｍｅｓ｜ｍａｘ（Ｃ＿ｊ＋ｑ＿ｉ）而言，按传递时间｛ｑ＿ｊ｝递减的顺序（即按ｑ＿１≥ｑ＿２≥…≥ｑ＿ｎ）加工工件得到最优排序。 证明 由上述算法立得欲证。