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

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

提出一类有准备时间的排序问题；分析了ＬＳ算法解此问题的最坏情况；修改了ＬＰＴ算法，使最差性能指标由４－２ｍ改进到８３－２３ｍ．

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 .