欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
主要讨论了工件有到达时间、加工时间和尺寸的目标函数是极小化最大延误时间的单机分批排序问题1｜B,rj,sj｜Lmax.在机器容量B为常数时,即使在B=2和工件的到达时间与尺寸都相同时,问题也是强NP—难的.基于问题1｜B,rj｜Lmax目前最好的多项式时间近似算法——PTAS算法（从算法的最差性能比来说是最好的）,我们采用任意工件可以按尺寸拆分的技巧,针对问题1｜B,rj,sj｜Lmax设计了一个多项式时间的近似算法,并分析出这个算法的最差性能比为2＋ε（其中ε是任意小的正数）.
英文摘要：
We consider the batch processing problem 1｜B,rj,sj｜Lmax.Under the assumption that the machine capacity B is fixed,the problem is strongly NP—hard even with B=2 and identical job arrival-times and sizes.Using the PTAS for the problem 1｜B,rj｜Lmax which is best possible in the sense of worst-case ratio,we successly present an approximation algorithm with worst-case ratio 2＋ε（where ε0,can be made arbitrarily small） for the bounded problem of maximum lateness time 1｜B,rj,sj｜Lmax.
同期刊论文项目
同项目期刊论文
期刊信息
位置：