[1]闻振卫,莫泽. 加工时间为线性增函数有上界的排序问题[J].重庆师范大学学报(自然科学版),2010,27(01):1-6.[doi:10.11721/cqnuj20100101]
-[J].期刊社,2010,27(01):1-6.[doi:10.11721/cqnuj20100101]
点击复制
重庆师范大学学报(自然科学版)[ISSN:1672-6693/CN:50-1165/N]
- 卷:
-
27
- 期数:
-
2010年01期
- 页码:
-
1-6
- 栏目:
-
运筹学与控制论
- 出版日期:
-
2010-01-25
文章信息/Info
- Title:
-
-
- 作者:
-
闻振卫; 莫泽
-
- Author(s):
-
-
-
-
- 关键词:
-
排序; 加工时间增加; 最大完工时间
- Keywords:
-
-
- 分类号:
-
-
- DOI:
-
10.11721/cqnuj20100101
- 文献标志码:
-
A
- 摘要:
-
本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1|pj(t)(t0,T1,T2)|Cmax:设工件集J=J1,J2,…,Jn中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻t00开始加工;Ω1中工件的加工时间为pj(t)=ajt(当tT1)或pj(t)=ajT1(当t≥T1),Ω2中工件的加工时间为pj(t)=ajt(当tT2)或pj(t)=ajT2(当t≥T2),其中T2T1t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cm ax。在所得的引理2和引理3的基础上,本文给出一个复杂度为nlogn的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的。
- Abstract:
-
更新日期/Last Update:
2013-07-06