Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法)
对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数),并证明了当时,对偶阈值算法的近似比为,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法....
Main Authors: | FANJing(范静), YANGQi-fan(杨启帆) |
---|---|
Format: | Article |
Language: | zho |
Published: |
Zhejiang University Press
2005-05-01
|
Series: | Zhejiang Daxue xuebao. Lixue ban |
Subjects: | |
Online Access: | https://doi.org/zjup/1008-9497.2005.32.3.258-263 |
Similar Items
-
Algorithms for semi-on-line scheduling problems on two uniform machines with set-up time(带准备时间的两台同类机半在线排序的近似算法)
by: HUARong-wei(华荣伟)
Published: (2007-09-01) -
Algorithms for semi on-line scheduling problems on two uniform machines with set-up time where the total processing time is known in advance(带准备时间的两台同类机已知工件总加工时间的半在线排序问题的近似算法)
by: HUARong-wei(华荣伟), et al.
Published: (2008-07-01) -
A note on single processor scheduling with time restrictions(关于带时间约束的单机排序的一个注记)
by: WANShaochun(万绍春), et al.
Published: (2018-01-01) -
Better approximation algorithm for scheduling independent parallel tasks(带并行工件的平行机排序问题的一个新近似算法)
by: SHENHao(沈灏), et al.
Published: (2004-03-01) -
Semi-online multiprocessor scheduling with the longest given processing time(已知工件最大加工时间的平行机排序问题)
by: WUYong(吴用), et al.
Published: (2008-01-01)