有使用限制的两台机器排序问题的近似算法

李刚刚; 李浩

doi:10.19603/j.cnki.1000-1190.2015.01.003

华中师范大学学报（自然科学版） ›› 2015, Vol. 49 ›› Issue (01) : 11 -13+20. DOI: 10.19603/j.cnki.1000-1190.2015.01.003

有使用限制的两台机器排序问题的近似算法

李刚刚, 李浩

作者信息 +

Author information +

文章历史 +

PDF

摘要

研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS(fully polynomial-time approximation scheme).