排序方式： 共有5条查询结果，搜索用时 15 毫秒
1
1.
栾文婕 《聊城大学学报(自然科学版)》2011,(4):37-40,51
考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性. 相似文献
2.
武光华 《青岛大学学报(自然科学版)》2014,(2):14-16
主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP一难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。 相似文献
3.
4.
经典的排序问题要求工件都必须进行加工,然而在实际中有时候由于一些特殊的原因可以考虑工件不加工。例如,加工时间非常大,或加工所需费用非常高,于是就不加工这一工件,而是通过支付一定的费用后送到外边"外加工"或购买更合算,这类问题称为工件可拒绝排序问题。需要研究的任务是怎样选择工件在机器上进行加工或拒绝,并且如何安排被接受加工工件的加工次序使给定的目标函数值最优。本文研究了工件可拒绝排序中,目标函数是有限的总惩罚费用(总惩罚费用约束下)极小化加权总完工时间,工件到达时间都相同的同型机问题,设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法。 相似文献
5.
研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS (fully polynomial－time approximation scheme). 相似文献
1