具有通用机的多组工件的Q//Cmax问题的近似算法

丁伟

您当前的位置：

首页 >

文章列表页 >

具有通用机的多组工件的Q//Cmax问题的近似算法

研究论文 | 更新时间：2023-12-11

- 具有通用机的多组工件的Q//Cmax问题的近似算法
- Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors
- 中山大学学报(自然科学版)(中英文) 2010年49卷第1期页码：5-8
- 作者机构：
  
  中山大学数学与计算科学学院,广东,广州,510275
- 作者简介：
- 基金信息：
- DOI：
  中图分类号：
- 纸质出版日期：2010，
  
  网络出版日期：2010-1-25，
扫描看全文
丁伟. 具有通用机的多组工件的Q//Cmax问题的近似算法[J]. 中山大学学报(自然科学版)(中英文), 2010,49(1):5-8.

DING Wei. Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2010,49(1):5-8.
丁伟. 具有通用机的多组工件的Q//Cmax问题的近似算法[J]. 中山大学学报(自然科学版)(中英文), 2010,49(1):5-8. DOI：

DING Wei. Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2010,49(1):5-8. DOI：

摘要

研究的目的在于解决实践中对多组任务的优化排序问题

即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题

人们通常寻求其近似算法。提出了一种改进的LPT算法，利用“最大相对加工时间”准则和“首先空闲”准则，讨论了将n组工件安排在n台速度不同的专用机，一台速度小于专用机的通用机上的〖WTBX〗Cmax 〖WTBZ〗问题

得到了利用该近似算法所得的解T与最优解T*的一个估计：T/T*≤1+1/∑〖DD(X〗i∈I〖DD)〗si

其中I表示在最后完工的工件完工之前，在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对工件排序，在最差情况下要比最优排序多出1/∑〖DD(X〗i∈I〖DD)〗si的时间。

Abstract

To study the Cmax problem on manygroup jobs with one generalpurpose machinery and n specialpurpose machineries that they are with the different speeds. This problem is always NPC problem

so the approximate method is usually to be found. An improved LPT algorithm and the upper bound performance are given. The ratio of the approximate solution and the best way is T/T*≤1+1/∑〖DD(X〗i∈I〖DD)〗si

it means that the complete time using this approximate method is 1/∑〖DD(X〗i∈I〖DD)〗si more than the best in worst condition.

关键词

启发式算法性能指标LPT算法通用机专用机

Keywords

heuristic algorithmperformance indexesLPT algorithmgeneralpurpose machineryspecialpurpose machinery

references

浏览量

124

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

速度相同的具有m-2台通用机的两组工件的LS算法分析

同速度的具有m台通用机的n组工件的排序问题