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

丁; 伟

您当前的位置：

首页 >

文章列表页 >

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

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

- 速度相同的具有m-2台通用机的两组工件的LS算法分析
- An Analysis of LS Algorithm for the Scheduling Problem on m－2GeneralPurpose Machinery and Two Group Tasks with Uniform Processors
- 中山大学学报(自然科学版)(中英文) 2010年49卷第6期页码：1-5
- 作者机构：
  
  中山大学数学与计算科学学院,广东,广州,510275
- 作者简介：
- 基金信息：
- DOI：
  中图分类号：
- 纸质出版日期：2010，
  
  网络出版日期：2010-11-25，
扫描看全文
丁, 伟. 速度相同的具有m-2台通用机的两组工件的LS算法分析[J]. 中山大学学报(自然科学版)(中英文), 2010,49(6):1-5.

An Analysis of LS Algorithm for the Scheduling Problem on m－2GeneralPurpose Machinery and Two Group Tasks with Uniform Processors[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2010,49(6):1-5.
丁, 伟. 速度相同的具有m-2台通用机的两组工件的LS算法分析[J]. 中山大学学报(自然科学版)(中英文), 2010,49(6):1-5. DOI：

An Analysis of LS Algorithm for the Scheduling Problem on m－2GeneralPurpose Machinery and Two Group Tasks with Uniform Processors[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2010,49(6):1-5. DOI：

摘要

对于实践中存在的具有两组任务的优化排序问题进行了讨论，在经典的LS算法的基础上提出了一种改进的LS算法，利用“首先空闲”准则选择机器，按照工件的到达顺序安排工件，讨论了将两组工件安排在两台速度相同的专用机，m－2台同速度的通用机上的〖WTBX〗C

max

问题，其中工件具有准备或到达时间，且工件的准备或到达时间均不超过其加工时间的α倍。目标是在最短的时间内完成所有给定的任务。得到了利用该近似算法所得的解T

与最优解T*的一个估计(1+α)(2-1/m)，并且证明了对任意的α此界是紧的。

Abstract

The C

max

 problem on twogroup jobs with m－2generalpurpose machineries and two specialpurpose machineries that they are the same speed

and the jobs have the setup times and it is no more α time than its processing times is studied. An improved LS algorithm and the upper tight bound performance are given. The ratio of the approximate solution T

 and the best way T

is (1+α)(2-1/m)

and it is tight for all α.

关键词

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

Keywords

heuristic approachperformance indexesLS algorithmLPT algorithmgeneralpurpose and specialpurpose machinery

references

浏览量

127

下载量

CSCD

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

提交

工具集

关联资源

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

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