平行機排序及相關問題研究

《平行機排序及相關問題研究》是依託浙江大學，由何勇1擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：平行機排序及相關問題研究
• 依託單位：浙江大學
• 項目負責人：何勇1
• 項目類別：青年科學基金項目
• 批准號：19701028
• 申請代碼：A0406
• 負責人職稱：講師
• 研究期限：1998-01-01 至 2000-12-31
• 支持經費：3.5（萬元）

項目摘要

本項目討論了一系列平行機排序問題。對經典平行排序問題，解決了一些著名近似算法的緊界估計；利用對偶的思想設計出一些複合型近似算法，它們用來求解相應排序問題，既有很低的時間複雜性，又有很好的的似性能比。對帶機器準備時間的平行機排序問題，首次發現了非積極機器的存在性；給出了幾個經典貪婪算法在不同目標下的緊界估計。研究了線上半線上排序問題，對一些新提出的半線上排序模型，給出了各自的最好線上近似算法。探討了工件可拒絕加工的平行機排序問題，對兩台同類機線上模型，給出了一個近似優算法。此外，對隨機算法，排序相關問題如分劃問題、約束最短網路問題等進行了一些研究。發表論文有9篇被SCI檢索。