| 分批排序的"转换引理"及其应用 |
| |
| 引用本文： | 张玉忠,王忠志,王长钰.分批排序的"转换引理"及其应用[J].系统科学与数学,2002,22(3):328-333. |
| |
| 作者姓名： | 张玉忠 王忠志 王长钰 |
| |
| 作者单位： | 曲阜师范大学运筹学研究所,曲阜,273165 |
| |
| 基金项目： | 国家自然科学基金,教育部高校骨干教师项目,山东省自然科学基金,山东省中青年科学家奖励基金,山东省中青年学术骨干项目资助课题. |
| |
| 摘 要： | 本文首次对同类机分批排序问题进行了研究,讨论极小化最大完工时间和极小化最大延迟两类问题.首先揭示了分批排序问题与经典排序问题之间的联系,得到了有趣的“转换引理”,提出了近似算法并用“转换引理”分析了这些算法的最差性能,改进了前人的诸多结果.
|
| 关 键 词： | 排序 同类机 LPT算法 LS算法 装箱 |
THE "TRANSFORM LEMMA" AND ITS APPLICATION IN BATCH SCHEDULING |
| |
| Yu Zhong ZHANG,Zhong Zhi WANG,Chang Yu WANG.THE "TRANSFORM LEMMA" AND ITS APPLICATION IN BATCH SCHEDULING[J].Journal of Systems Science and Mathematical Sciences,2002,22(3):328-333. |
| |
| Authors: | Yu Zhong ZHANG Zhong Zhi WANG Chang Yu WANG |
| |
| Institution: | Institute of Operations Research, Qufu Normal University, Qufu 273165,P.R.China |
| |
| Abstract: | The scheduling problems on uniformly related batch machines are firstly delivered in the paper. Two kinds of problems are considered: minimize the makespan and minimize the maximum lateness. The relation between batch scheduling and classical scheduling is declared, then an interesting " transform lemma " is obtained. Then some heuristics for theproblems are presented, and their performance guarantees are analyzed by the " transform lemma ". Some existing results are improved. |
| |
| Keywords: | Scheduling uniform machines LPT algorithm LS algorithm Bin-packing |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 |
|
