Please wait a minute...
高校应用数学学报
高校应用数学学报  2017, Vol. 32 Issue (4): 462-472    
    
单台机以总完工时间为目标的批排序问题
严羽洁
浙江大学数学科学学院, 浙江杭州310027
Study for batch scheduling on single machine
YAN Yu-jie
School of Math. Sci., Zhejiang Univ., Hangzhou 310027, China
 全文: PDF 
摘要： 研究单台机, 工件加工时间相等, 大小不同的批排序问题, 给出了一个最坏情况界为$\frac{9+\sqrt{3}}{6}\approx 1.7817$的多项式时间近似算法, 并证明了即使工件总大小不超过$2$, 该问题也不存在FPTAS, 除非P=NP. 
关键词： 组合优化;  批排序问题;  多项式时间近似算法;  计算复杂性    
Abstract: For the problem of minimizing total completion time on single machine with unit processing time, an approximation algorithm with a performance ratio smaller than$\frac{9+\sqrt{3}}{6}\approx1.7817$ is given. The paper showed that there dose not exist any fully polynomial time approximation schedule unless $P=NP$, even if the total size of the jobs is smaller than 2.
Key words: combinatorial optimization    batch scheduling    approximation algorithm    computational complexity
收稿日期: 2017-03-18 出版日期: 2018-12-01
CLC:  O223  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
严羽洁

引用本文:

严羽洁. 单台机以总完工时间为目标的批排序问题[J]. 高校应用数学学报, 2017, 32(4): 462-472.

YAN Yu-jie. Study for batch scheduling on single machine. Applied Mathematics A Journal of Chinese Universities, 2017, 32(4): 462-472.

链接本文:

http://www.zjujournals.com/amjcua/CN/    或    http://www.zjujournals.com/amjcua/CN/Y2017/V32/I4/462

[1] 魏麒, 蒋天颖. 一个混合协调分配机制下自私调度问题的社会无序代价分析[J]. 高校应用数学学报, 2017, 32(4): 473-486.