Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors

DING Wei

您当前的位置：

首页 >

文章列表页 >

Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors

更新时间：2023-12-11

- Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors
- Acta Scientiarum Naturalium Universitatis SunYatseni Vol. 49, Issue 1, Pages: 5-8(2010)
- 作者机构：
  
  中山大学数学与计算科学学院,广东,广州,510275
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2010，
  
  Published Online：25 January 2010，
扫描看全文
DING Wei. Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors. [J]. Acta Scientiarum Naturalium Universitatis SunYatseni 49(1):5-8(2010)
DOI：

DING Wei. Heuristic Algorithm of the Q//CmaxProblem on MultiTasks with Uniform Processors. [J]. Acta Scientiarum Naturalium Universitatis SunYatseni 49(1):5-8(2010) 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

Views

124

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

An Analysis of LS Algorithm for the Scheduling Problem on m－2GeneralPurpose Machinery and Two Group Tasks with Uniform Processors

A Type of Scheduling Problem on m GeneralPurpose Machineryand n Group Tasks with Uniform Processors

Related Author

丁

伟

DING Wei

Related Institution

School of Mathematics and Computational Science,Sun Yatsen University

中山大学数学系//物理系

Postal code：510275
Tel：020-84112585，84113223 Email：xuebaozr@mail.sysu.edu.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰