摘要
本文主要研究了平行机上时间一致时极小化工件配送时间的分批排序问题,该问题是传统的分批排序与当代的物流相结合而产生的一类新的问题.一般情况下当工件有不同的到达时间时该问题是强NP—难的,但对工件有有限个到达时间及机器台数有限时,若所有的输入数据均为整数,本文给出了问题的伪多项式时间算法,从而说明了在这种情况下问题不是强NP—难的.当输入数据是有理数时,本文给出了问题的FPTAS算法.并给出了时间一致时一般情形的PTAS算法.
In this paper we conside the problem to minimize the delivery times on parallel batch machines when jobs have agreeable times . This is a new kind of problem which contains both batch scheduling problems and logistic problems. Generally speaking , when jobs have different release dates, this problem is strong NP - hard . But when the number of job release dates and the number of machines are constant , if all the inputs are integral values we will present a pseudo -polinomial algorithm , so the problem is not shrongly NP -hard in this special case . when the inputs are not restricted to integral values , we obtain a FPTAS algorithm. Fi- nally we extend this result to a PTAS algorithm for the general problems.
出处
《济宁学院学报》
2008年第6期31-34,共4页
Journal of Jining University
