一类P/S_(ij)/C_(max)问题的LS算法分析  

AN ANALYSIS OF LS PROCEDURE FOR P/S ij /C max PROBLEM

作　　者：张玉忠[1,2] 杜东雷[1,2] 

机构地区：[1]曲阜师范大学运筹所 [2]中科院应用数学所

出　　处：《曲阜师范大学学报（自然科学版）》1997年第1期9-12,共4页Journal of Qufu Normal University(Natural Science)

基　　金：国家自然科学基金

摘　　要：提出一类有准备时间的排序问题；分析了ＬＳ算法解此问题的最坏情况；修改了ＬＰＴ算法，使最差性能指标由４－２ｍ改进到８３－２３ｍ．One kind of scheduling problem with setup time is proposed, the worst_case performance of LS is studied, LPT algorithm is improved and the worst_case performance ratio 4-2 m is reduced to 83-23 m .

关 键 词：最大完工时间 LS算法 LPT算法 排序 

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