共查询到15条相似文献，搜索用时 939 毫秒
1.
本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$ $m$
2.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ $m$ $m$ $(m-1)$ $(m-1)$ $(2+\rho)$ $\rho$
3.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ $m$ $m$ $(m-1)$ $(m-1)$ $(2+\rho)$ $\rho$
4.
设$ G $ $ n $ $ k $ $ k $ $ k-1 $ $ \mu_{1}(G) $ $ \mu_{2}(G) $ $ G $ $ G $ $ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $ $ k $ $ k=1, 2, 3 $
5.
设$ G $ $ n $ $ k $ $ k $ $ k-1 $ $ \mu_{1}(G) $ $ \mu_{2}(G) $ $ G $ $ G $ $ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $ $ k $ $ k=1, 2, 3 $
6.
7.
8.
研究了单位$l_{\infty}$ $G=(V, E, w)$ $T^0$ $\bm{l}$ $\bm{u}$ $K$ $\bm{\bar{w}}$ $\bm{l}\le\bar{\bm w}\le {\bm u}$ $T^0$ $\bm{\bar{w}}$ $K$ $l_{\infty}$ $\|\bar{\bm w}-{\bm w}\|$ $O(|V||E|)$
9.
研究了单位$l_{\infty}$ $G=(V, E, w)$ $T^0$ $\bm{l}$ $\bm{u}$ $K$ $\bm{\bar{w}}$ $\bm{l}\le\bar{\bm w}\le {\bm u}$ $T^0$ $\bm{\bar{w}}$ $K$ $l_{\infty}$ $\|\bar{\bm w}-{\bm w}\|$ $O(|V||E|)$
10.
11.
本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$ $\alpha$ $0\leq\alpha\leq 1$
12.
13.
14.
15.
设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。 相似文献