资源描述
集合论部分第四章、二元关系和函数 4.1 集合的笛卡儿积与二元关系有序对 定义 由两个客体 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作实例：点的直角坐标(3,-4) 有序对性质 有序性 （当x y时） 与 相等的充足必要条件是= x=u y=v 例1 = ，求 x, y. 解 3y- 4 = 2, x+5 = y y = 2, x = - 3 定义 一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即 = , xn 当 n=1时, 形式上可以当作有序 1 元组. 实例 n 维向量是有序 n元组. 笛卡儿积及其性质定义 设A,B为集合，A与B 的笛卡儿积记作AB， 即 AB = | xA yB 例2 A=1,2,3, B=a,b,c AB =, , BA =, , , A=, P(A)A=, 性质：不适合互换律 ABBA (AB, A, B)不适合结合律 (AB)CA(BC) (A, B)对于并或交运算满足分派律 A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 若A或B中有一个为空集，则AB就是空集. A=B= 若|A|=m, |B|=n, 则 |AB|=mn 证明 A(BC)=(AB)(AC)证 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有A(BC) = (AB)(AC).例3 (1) 证明 A=B C=D AC=BD (2) AC=BD是否推出 A=B C=D ? 为什么？ 解 (1) 任取 AC xA yC xB yD BD (2) 不一定. 反例如下： A=1，B=2, C=D=, 则 AC=BD 但是 AB. 二元关系的定义定义 设A,B为集合, AB的任何子集所定义的二元关系叫做从A到B的二元关系, 当A=B时则叫做 A上的二元关系.例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么 R1, R2, R3, R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系. 计数|A|=n, |AA|=n2, AA的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有=512个不同的二元关系. 设 A 为任意集合，是 A 上的关系，称为空关系EA, IA 分别称为全域关系与恒等关系，定义如下： EA=|xAyA=AA IA=|xA例如, A=1,2, 则 EA=, IA=,小于等于关系 LA, 整除关系DA, 包含关系R定义： LA=| x,yAxy, AR，R为实数集合 DB=| x,yBx整除y, BZ*, Z*为非0整数集 R=| x,yAxy, A是集合族.类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 例如 A = 1, 2, 3, B =a, b, 则 LA=, DA=,A=P(B)=,a,b,a,b, 则 A上的包含关系是 R=, , 二元关系的表达表达方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=a1, a2, , am，B=b1, b2, , bn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中 rij = 1 R. 关系图：若A= x1, x2, , xm，R是从A上的关系，R的关系图是GR=, 其中A为结点集，R为边集.假如属于关系R，在图中就有一条从 xi 到 xj 的有向边. 注意：A, B为有穷集，关系矩阵适于表达从A到B的关系或者A上的关系，关系图适于表达A上的关系A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下：4.2 关系的运算基本运算定义：定义域、值域 和 域 domR = x | $y (R) ranR = y | $x (R) fldR = domR ranR 例1 R=, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 逆与合成 R-1 = | R RS = | | $ y (RS) 例2 R=, , , S=, , , , R-1=, , , RS =, , SR =, , , 定义 F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA) 实例 R=, , , R1=, R1=2,4 R= R1,2=2,3,4注意：FAF, FA ranF 基本运算的性质定理1 设F是任意的关系, 则(1) (F-1)-1=F (2) domF-1=ranF, ranF-1=domF 证 (1) 任取, 由逆的定义有 (F - 1)-1 F-1 F 所以有 (F-1)-1=F (2) 任取x, xdomF-1 $y(F-1) $y(F) xranF 所以有domF-1= ranF. 同理可证 ranF-1 = domF.定理2 设F, G, H是任意的关系, 则 (1) (FG)H=F(GH) (2) (FG)-1= G-1F-1 证 (1) 任取, (FG)H $t(FGH) $t ($s(FG)H) $t $s (FGH) $s (F$t (GH) $s (FGH) F(GH) 所以 (FG)H = F(GH)(2) 任取, (FG)-1 FG $t (F(t,x)G) $t (G-1(t,y)F-1) G-1F-1 所以 (FG)-1 = G-1F-1 幂运算设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0= | xA =IA (2) Rn+1 = RnR 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R 性质：定理3 设A为n元集, R是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.证 R为A上的关系, 由于|A|=n, A上的不同关系只有 个. 当列出 R 的各次幂 R0, R1, R2, , , , 必存在自然数 s 和 t 使得 Rs=Rt.定理4 设 R 是 A 上的关系, m, nN, 则 (1) RmRn=Rm+n (2) (Rm)n=Rmn 证 用归纳法 (1) 对于任意给定的mN, 施归纳于n.若n=0, 则有 RmR0=RmIA=Rm=Rm+0 假设RmRn=Rm+n, 则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1 , 所以对一切m, nN有RmRn=Rm+n. (2) 对于任意给定的 mN, 施归纳于n.若n=0, 则有 (Rm)0=IA=R0=Rm0 假设 (Rm)n=Rmn, 则有(Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1) 所以对一切 m,nN 有 (Rm)n=Rmn. 4.3 关系的性质自反性反自反性定义 设R为A上的关系,(1) 若x(xAR), 则称R在A上是自反的.(2) 若x(xAR), 则称R在A上是反自反的.实例：反关系：A上的全域关系EA, 恒等关系IA 小于等于关系LA, 整除关系DA 反自反关系：实数集上的小于关系 幂集上的真包含关系例1 A=1,2,3, R1, R2, R3是A上的关系, 其中R1,R2,R3 R2自反, R3反自反, R1既不是自反也不是反自反的对称性反对称性定义 设R为A上的关系, (1) 若xy(x,yARR), 则称R为A上对称的关系. (2) 若xy(x,yARRx=y), 则称R为A上的反对称关系.实例： 对称关系：A上的全域关系EA, 恒等关系IA和空关系 反对称关系：恒等关系IA，空关系是A上的反对称关系. 例2 设A1,2,3, R1, R2, R3和R4都是A上的关系, 其中 R1,， R2, R3,， R4, R1 对称、反对称. R2 对称，不反对称. R3 反对称，不对称. R4 不对称、也不反对称. 传递性定义 设R为A上的关系, 若 xyz(x,y,zARRR),则称R是A上的传递关系.实例： A上的全域关系EA,恒等关系IA和空关系 小于等于关系, 小于关系，整除关系，包含关系， 真包含关系例3 设A1,2,3, R1, R2, R3是A上的关系, 其中 R1, R2, R3R1 和 R3 是A上的传递关系 R2不是A上的传递关系关系性质的充要条件设R为A上的关系, 则 (1) R在A上自反当且仅当 IA R (2) R在A上反自反当且仅当 RIA= (3) R在A上对称当且仅当 R=R-1 (4) R在A上反对称当且仅当 RR-1IA (5) R在A上传递当且仅当 RRR证明模式 证明R在A上自反 任取x, xA . R 前提 推理过程 结论例4 证明若 IA R ，则 R在A上自反. 证 任取x, xA IA R 因此 R 在 A 上是自反的.证明模式 证明R在A上对称 任取 R . R 前提 推理过程 结论例5 证明若 R=R-1 , 则R在A上对称. 证 任取 R R -1 R 因此 R 在 A 上是对称的.证明模式 证明R在A上反对称 任取 RR . x=y 前提 推理过程 结论例6 证明若 RR-1IA , 则R在A上反对称. 证 任取 R R R R -1 RR -1 IA x=y 因此 R 在 A 上是反对称的.证明模式 证明R在A上传递 任取， RR . R 前提 推理过程 结论例7 证明若 RRR , 则R在A上传递. 证 任取， R R RR R 因此 R 在 A 上是传递的.4.4 关系的闭包闭包定义定义 设R是非空集合A上的关系, R的自反（对称或传递）闭包是A上的关系R, 使得R满足以下条件：（1）R是自反的（对称的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系 R 有 RR. 一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递闭包记作 t(R). 闭包的构造方法定理1 设R为A上的关系, 则有 (1) r(R) = RR0(2) s(R) = RR-1(3) t(R) = RR2R3说明： 对于有穷集合A (|A|=n) 上的关系, (3)中的并最多 不超过 Rn. 若 R是自反的，则 r(R)=R; 若R是对称的，则 s(R)=R; 若R是传递的，则 t(R)=R. 设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr, Ms 和 Mt , 则 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和 M 同阶的单位矩阵, M是 M 的转置矩阵. 注旨在上述等式中矩阵的元素相加时使用逻辑加.设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt , 则Gr, Gs, Gt 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述方法添加新边： 考察G的每个顶点, 假如没有环就加上一个环，最终得到Gr . 考察G的每条边, 假如有一条 xi 到 xj 的单向边, ij, 则在G中加一条 xj 到 xi 的反方向边，最终得到Gs. 考察G的每个顶点 xi, 找从 xi 出发的每一条途径，假如从 xi 到途径中任何结点 xj 没有边，就加上这条边. 当检查完所有的顶点后就得到图Gt . 4.5 等价关系和偏序关系定义 设 R 为非空集合上的关系. 假如 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系. 设 R 是一个等价关系, 若R, 称 x 等价于y, 记做 xy.实例 设 A=1,2,8, 如下定义A上的关系 R：R = | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 验证模 3 相等关系 R 为 A上的等价关系, 由于 xA, 有x x(mod 3) x, yA, 若 x y(mod 3), 则有 y x(mod 3) x, y, zA, 若x y(mod 3), y z(mod 3), 则有 xz(mod 3)自反性、对称性、传递性得到验证定义 设R为非空集合A上的等价关系, xA，令xR = y | yAxRy 称 xR 为 x 关于R 的等价类, 简称为 x 的等价类, 简记为x. 实例 A= 1, 2, , 8 上模 3 等价关系的等价类： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6等价类的性质：定理1 设R是非空集合A上的等价关系, 则 (1) xA, x 是A的非空子集. (2) x, yA, 假如 x R y, 则 x=y. (3) x, yA, 假如 x y, 则 x与y不交. (4) x | xA=A，即所有等价类的并集就是A. A= 1, 2, , 8 上模 3 等价关系的等价类： 1=4=7=1,4,7， 2=5=8=2,5,8， 3=6=3,6 以上3 类两两不交， 1,4,72,5,83,6 = 1,2, ,8定义 设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = xR | xA 实例 A=1,2,8,A关于模3等价关系R的商集为 A/R = 1,4,7, 2,5,8, 3,6 A关于恒等关系和全域关系的商集为： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 集合的划分：定义 设A为非空集合, 若A的子集族(P(A) 满足下面条件： (1) (2) xy (x,yxyxy=) (3) =A 则称是A的一个划分, 称中的元素为A的划分块. 例1 设Aa, b, c, d, 给定1,2,3,4,5,6如下： 1= a, b, c, d ， 2= a, b, c, d 3= a, a, b, c, d , 4= a, b, c 5= ,a, b, c, d , 6= a, a, b, c, d 则1和2 是A的划分, 其他都不是 A 的划分. 为什么？ 等价关系与划分的一一相应商集 A/R 就是 A 的一个划分 不同的商集相应于不同的划分 任给 A 的一个划分, 如下定义 A 上的关系 R： R = | x,yAx 与 y 在的同一划分块中则 R 为 A上的等价关系, 且该等价关系拟定的商集就是. 例2 给出A1,2,3上所有的等价关系求解思绪：先做出A的所有划分, 然后根据划分写出相应的等价关系. 例3 设 A=1, 2, 3, 4，在 AA上定义二元关系R： ,R x+y = u+v，求 R 导出的划分. 解 AA=, , , , , , , , , , , , , 根据 的 x + y = 2,3,4,5,6,7,8 将AA划提成7个等价类： (AA)/R= , , , , , , , , , , , , , , 定义 非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作. 设为偏序关系, 假如, 则记作 xy, 读作 x“小于或等于”y. 实例 集合A上的恒等关系 IA 是A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系. x与 y 可比：设R为非空集合A上的偏序关系, x,yA, x与y可比 xy yx.结论：任取两个元素x和y, 也许有下述情况： xy (或yx), xy, x与y不是可比的.全序关系： R为非空集合A上的偏序, x,yA, x与 y 都是可比的，则称 R 为全序（或 线序）实例：数集上的小于或等于关系是全序关系 整除关系不是正整数集合上的全序关系覆盖：设R为非空集合A上的偏序关系, x, yA, 假如 x y且不存在 zA 使得 x z y, 则称 y 覆盖x.实例： 1, 2, 4, 6 集合上的整除关系, 2 覆盖 1, 4 和 6 覆盖 2. 4 不覆盖 1. 定义 集合A和A上的偏序关系一起叫做偏序集, 记作 .实例：整数集和小于等于关系构成偏序集，幂集P(A)和包含关系构成偏序集. 哈斯图：运用偏序自反、反对称、传递性简化的关系图特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表达，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边偏序集的特定元素定义 设为偏序集, BA, yB.(1) 若x(xByx) 成立, 则称 y 为 B 的最小元.(2) 若x(xBxy) 成立, 则称 y 为 B 的最大元. (3) 若$x (xBx y) 成立, 则称 y 为B的极小元. (4) 若$x (xBy x) 成立, 则称 y 为B的极大元.特殊元素的性质对于有穷集，极小元和极大元必存在，也许存在 多个. 最小元和最大元不一定存在，假如存在一定惟一.最小元一定是极小元；最大元一定是极大元. 孤立结点既是极小元，也是极大元. 定义 设为偏序集, BA, yA. (1) 若x(xBxy) 成立, 则称 y 为B的上界. (2) 若x(xByx) 成立, 则称 y 为B的下界. (3) 令Cy | y为B的上界, 则称C的最小元为B的最小上界 或 上确界. (4) 令Dy | y为B的下界, 则称D的最大元为B的最大下界 或 下确界.特殊元素的性质下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下确界、上确界假如存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确界；反之不对. 4.6 函数的定义和性质函数定义：定义 设 F 为二元关系, 若 xdomF 都存在唯一的yranF 使 xFy 成立, 则称 F 为函数. 对于函数F, 假如有 xFy, 则记作 y=F(x), 并称 y 为 F 在 x 的值. 例1 F1=, F2=, F1是函数, F2不是函数 函数相等：定义 设F, G为函数, 则 F = G FGGF 假如两个函数 F 和 G 相等, 一定满足下面两个条件： (1) domF = domG (2) xdomF = domG 都有 F(x) = G(x) 实例 函数 F(x)=(x2-1)/(x+1), G(x)=x-1不相等, 由于 domFdomG. 定义 设A, B为集合, 假如 f 为函数 domf = A ranf B, 则称 f 为从A到B的函数, 记作 f：AB. 实例 f：NN, f(x)=2x 是从 N 到 N 的函数 g：NN, g(x)=2也是从 N 到 N 的函数 定义 所有从 A 到 B 的函数的集合记作 BA, 读作“B上A”，符号化表达为 BA = f | f：AB 计数： |A|=m, |B|=n, 且m, n0, |BA|=nm. A=, 则 BA=B=. A且B=, 则 BA=A= .例2 设 A = 1, 2, 3, B = a, b, 求BA. 解 BA = f0, f1, , f7, 其中 f0=, f1=, f2=,，f3=, f4=,，f5=, f6=, f7=, 定义 设函数 f：AB, A1A. A1 在 f 下的像： f(A1) = f(x) | xA1 函数的像 f(A) 注意：函数值 f(x)B, 而像 f(A1)B. 函数的性质定义 设 f：AB,（1）若ranf = B, 则称 f：AB是满射的.（2）若 yranf 都存在唯一的 xA使得 f(x)=y, 则称 f：AB是单射的.（3）若 f：AB既是满射又是单射的, 则称 f：AB是双射的f 满射意味着：y B, 都存在 xA 使得 f(x) = y. f 单射意味着：f(x1) = f(x2) x1= x2 例4 判断下面函数是否为单射, 满射, 双射的, 为什么? (1) f：RR, f(x) = -x2+2x-1 (2) f：Z+R, f(x) = lnx, Z+为正整数集 (3) f：RZ, f(x) = x (4) f：RR, f(x) = 2x+1 (5) f：R+R+, f(x)=(x2+1)/x, 其中R+为正实数集.解 (1) f：RR, f(x)=-x2+2x-1 在x=1取得极大值0. 既不单射也不满射. (2) f：Z+R, f(x)=lnx 单调上升, 是单射. 但不满射, ranf=ln1, ln2, . (3) f：RZ, f(x)= x 满射, 但不单射, 例如 f(1.5)=f(1.2)=1. (4) f：RR, f(x)=2x+1 满射、单射、双射, 由于它是单调的并且ranf=R. (5) f：R+R+, f(x)=(x2+1)/x 有极小值f(1)=2. 该函数既不单射也不满射.构造从A到B的双射函数有穷集之间的构造例5 A=P(1,2,3), B=0,11,2,3解 A=,1,2,3,1,2,1,3,2,3,1,2,3. B= f0, f1, , f7 , 其中 f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=,.令 f：AB, f()=f0, f(1)=f1, f(2)=f2, f(3)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f7常函数、恒等函数、单调函数1. 设f：AB, 若存在 cB 使得 xA 都有 f(x)=c, 则称 f：AB是常函数. 2. 称 A 上的恒等关系 IA为 A 上的恒等函数, 对所有 的 xA 都有 IA(x)=x. 3. 设 f：RR，假如对任意的 x1, x2R，x1x2, 就 有 f(x1) f(x2), 则称 f 为单调递增的；假如对任意 的 x1, x2A, x1 x2, 就有 f(x1) f(x2), 则称 f 为 严 格单调递增 的. 类似可以定义单调递减 和严格单调递减 的函数.例8 (1) A的每一个子集A都相应于一个特性函数, 不同的子集相应于不同的特性函数. 例如 A=a, b, c, 则有 c = , , ， ca,b = , , (2) 给定集合 A， A 上不同的等价关系拟定不同的自然映射, 其中恒等关系拟定的自然映射是双射, 其他的自然映射一般来说是满射. 例如 A=1, 2, 3, R=,IA g(1) = g(2) = 1,2, g(3) = 3 4.7 函数的复合和反函数函数复合的定理定理 设F, G是函数, 则FG也是函数, 且满足 (1) dom(FG)= x | xdomF F(x)domG (2) xdom(FG) 有 FG(x) = G(F(x)推论1 设F, G, H为函数, 则 (FG)H 和 F(GH) 都是函数, 且 (FG)H = F(GH)推论2 设 f：AB, g：BC, 则 fg：AC, 且 xA 都有 fg(x) = g(f(x). 函数复合运算的性质定理 设 f：AB, g：BC. (1) 假如 f：AB, g：BC 都是满射的, 则 fg：AC也是满射的. (2) 假如 f：AB, g：BC 都是单射的, 则 fg：AC也是单射的. (3) 假如 f：AB, g：BC 都是双射的, 则 fg：AC也是双射的.证 (1) cC, 由 g：BC 的满射性, $bB 使得 g(b)=c. 对这个b, 由 f：AB 的满射性，$aA 使得 f(a)=b. 由合成定理有 fg(a)=g(f(a)=g(b)=c 从而证明了 fg：AC是满射的. (2) 假设存在 x1, x2A使得 fg(x1) = fg(x2) 由合成定理有 g(f(x1)=g(f(x2). 由于 g：BC是单射的, 故 f(x1)=f(x2). 又由 于 f：AB也是单射的, 所以 x1=x2. 从而证 明 fg：AC是单射的. (3) 由 (1) 和 (2) 得证.定理 设 f: AB，则 f = fIB = IAf 反函数存在的条件任给函数 F, 它的逆F -1不一定是函数, 是二元关系.实例：F=,， F -1=, 任给单射函数 f：AB, 则 f -1是函数, 且是从 ranf 到 A的双射函数, 但不一定是从 B 到 A 的双射函数.实例：f : N N, f(x) = 2x, f -1 : ranf N, f -1 (x) = x/2 反函数定理 设 f：AB是双射的, 则f -1：BA也是双射的.证 由于 f 是函数, 所以 f -1 是关系, 且 dom f -1 = ranf = B , ran f -1 = domf = A, 对于任意的 yB = dom f -1, 假设有x1, x2A使得f -1f -1成立, 则由逆的定义有ff 根据 f 的单射性可得 x1 = x2, 从而证明了f -1是函数，且是满射的. 下面证明 f -1 的单射性. 若存在 y1, y2B 使得 f -1 (y1) = f -1 (y2) = x, 从而有f -1f -1 ff y1 = y2 反函数的定义及性质对于双射函数f：AB, 称 f -1：BA是它的反函数. 反函数的性质定理 设 f：AB是双射的, 则f -1f = IB, ff -1 = IA对于双射函数 f：AA, 有f -1f = ff -1 = IA 函数复合与反函数的计算问题描述多机调度问题：有2台机器c1, c2；6项任务t1, t2, , t6. 每项任务的加工时间分别为： l(t1)=l(t3)=l(t5)=l(t6)=1, l(t2)=l(t4)=2任务之间的顺序约束是： 任务t3只有在t6和t5完毕之后才干开始加工； 任务t2只有在t6, t5和t4都完毕后才干开始加工； 任务t1只有在t3和t2完毕之后才干开始加工. 调度：任务安排在机器上加工的方案截止时间：开始时刻0，最后停止加工机器的停机时刻问题描述集合任务集 T=t1, t2, . , tn, nZ+ 机器集 M=c1, c2, . , cm，mZ+ 时间集 N 函数和关系加工时间函数 l:TZ+. 顺序约束R T上的偏序关系，定义为 R=| ti, tjT, i=j 或 ti完毕后tj 才可以开始加工 可行调度分派到机器：T 的 划分 p=T1, T2, . , Tm，划分块Tj 是T 的非空子集，由安排在机器cj上加工的所有任务组成. 每个机器上的任务开始时间Tjp，存在调度函数 sj:TjN， 满足以下条件：(1) 任意时刻 i，每台机器上正在加工至多1个任务 i, 0 iD, | tk | tkTj, sj(tk)isj(tk)+l(tk) | 1, j=1, 2, , m (2) 任务的安排满足偏序约束 tiTi, tjTj, R si(ti)+l(ti)sj(tj) i, j=1, 2, , m 机器 j 的停止时间 Dj=maxsj(tk)| tkTj+l(tk)所有任务的截止时间 D=maxDj | j=1,2,.,m. 我们的问题就是拟定使得D达成最小的可行调度.
展开阅读全文