带有折扣因子的树型约束排序问题的最优算法

讨论优先约束条件为树型,目标函数为带有折扣的加权完工时间的单机排序问题l|outtree|∑wj(1-e-rCj),并给出了求解该问题的一个算法复杂性为O(n2)的最优算法.     

单机排序1|sp-graPh|∑wj(1-e-rCj)的最优算法

研究约束条件为串并有向图的单机加权总折扣花费问题,通过证明在考虑折扣因子的条件下,模块M的ρ因子最大初始集合I中的任务优先于模块M中的其他任务加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上.     

单机排序1｜sp-graph｜∑ωj（1-e^rCj）的最优算法

研究约束条件为串并有向图的单机加权总折扣花费问题，通过证明在考虑折扣因子的条件下，模块M的ρ因子最大初始集合I中的任务优先于模块M中的其他任务加工，并且被连续加工所得的排序为最优排序，从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上。     

关于一类两台机器自由作业的排序问题

以工件完工时间的总和为优化目标的两台机器自由作业问题是NP-hard问题.本文针对加工时间仅依赖于机器并且机器连续加工的问题,给出了机器排序是可行排序的充分必要条件,引入可行排列的极小子排列的概念,运用组合优化方法,研究了最优排序中极小子排列的性质,并由此得到了该问题的最优时间表的一般构造方法.     

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究3台机器调整时间可分离的无等待F1ow Shop排序问题，目标函数为极小化折扣加权总完工时间。对某些特殊情况，给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待F1ow Shop排序问题的分派规则。     

差异作业批调度的流水车间问题及近似算法

考虑了尺寸有差异的作业在两台设备上的流水加工问题,两台设备均为批处理机,有确定的最大容量.采用了制造跨度和总完工时间两类目标函数,建立了基于整数规划的优化模型,分析了两类问题的计算复杂性,给出了设备和作业数量既定情况下的可行解规模.设计了一种基于LPT规则和批调度规则的近似算法,时间性能为O(nlogn),证明了该算法在优化制造跨度时的最坏性能比不大于2,优化总完工时间的最坏性能比不大于3.     

MapReduce系统中的两阶段混合流水作业调度算法

以极小化最大完工时间为目标,研究MapReduce系统中的两阶段混合流水作业调度问题.每个工件都包含两个任务集,即map任务集和reduce任务集.所有map任务必须在第一阶段的m1台平行机上加工,而reduce任务则必须在第二阶段的m2台平行机上加工.一个工件的reduce任务只有在该工件的所有map任务完成后才能开始加工.所有reduce任务不允许中断.对map任务不可中断情形,给出了一个最坏情况界为2-1/max{m1,m2}的近似算法.对map任务可任意分割情形,分别给出了基于Johnson规则和LPT规则的近似算法H(2,J)和H(2,L),并证明了这两个算法的最坏情况界分别为2-1/m2和2.通过数值实验发现,一般情况下H(2,J)性能要优于H2,L,但在reduce任务的总加工时间大于map任务且m2较大时则相反.最后,当map任务和reduce任务的总加工时间成比例关系时,给出了算法H(2,J)的参数最坏情况界.     

具有外包选择的无等待流水线干扰修复模型北大核心CSSCI

针对双机成比例无等待流水线环境下最小化完工时间和的调度问题,研究如何基于干扰管理理论和采用作业外包途径来应对机器干扰事件。在证明最短加工时间优先(SPT)最优解定理的基础上,同时考虑最小化工件完工时间和指标(初始调度目标)与最小化工件滞后时间和指标(偏离最小目标),构建了基于SPT规则的干扰修复0-1整数规划模型,提出了基于差分进化全局搜索策略与"插入-交换"邻域搜索机制相结合的多目标混合智能算法。数值实验结果表明,本文提出的机器干扰条件下外包修复模型及算法是有效的。     

具有优势机器和恶化工件的流水作业排序问题

针对流水作业排序问题,建立了具有优势机器和恶化工件并且有无空闲限制的排序模型.在该排序模型中,机器加工工件时,工件的相邻加工工序之间不允许出现空闲,工件的加工时间是其开工时间的严格增加线性函数.其中讨论的优势机器有2种情况:机器形成增减增优势关系和机器形成减增减优势关系.考虑了多台机器的流水作业排序问题,其中,目标函数分别为极小化最大完工时间和极小化总完工时间,对于这两类问题分别给出了求解最优排序的多项式算法和它们的计算复杂性,并通过证明证实了算法的有效性.     

具有外包选择的无等待流水线干扰修复模型

针对双机成比例无等待流水线环境下最小化完工时间和的调度问题,研究如何基于干扰管理理论和采用作业外包途径来应对机器干扰事件。在证明最短加工时间优先(SPT)最优解定理的基础上,同时考虑最小化工件完工时间和指标(初始调度目标)与最小化工件滞后时间和指标(偏离最小目标),构建了基于SPT规则的干扰修复0-1整数规划模型,提出了基于差分进化全局搜索策略与"插入-交换"邻域搜索机制相结合的多目标混合智能算法。数值实验结果表明,本文提出的机器干扰条件下外包修复模型及算法是有效的。     

THE SPECTRAL COMPLETION OF A CLASS OF OPERATOR PARTIAL MATRICES

1. IntroductionLet Hi be complex Banach spaces, i = 1, 2,'' 5 n, and B(Hi, Hi) (B(Hi) if i = j) denotethe Banach space of all bounded linear operators from Hi to Hi. Let H ~ ffi:=IHi; thenA E B(H) may .be denoted by (Ail)... with Ail e B(Hj,Hi). Given a subset J C {(i,j)li,j = 1, 2,'',n} and Ail E B(Hj,Hi) for (i,i) e J, we get a partially specified n x n matriX(Xij)... with Xij ~ Ail if (i,i) e J and Xby (Ail)J If Q = (oil) E B(H) such that oil ~ Aijwhenever (i,i) e J, the…     

带有学习效应和机器可用性限制的排序问题

针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。同时由于定期维修等原因而导致机器在某段时间内不能加工工件。考虑了目标函数为极小化总完工时间的单机和两台机器的平行机问题。对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法。     

考虑最小化最大完工时间间隔的三台平行机调度

针对平行机调度,研究了当无预知情况下应对紧急任务快速响应的一类加工方案.考虑三台平行机的加工环境,分析任意两个相邻的工件完工时间的间隔,以最小化最大间隔值为优化目标.首先给出机器完工时间的两个上界作为可行方案的充分条件,进而给出最优方案的基本性质;其次,基于最优解的性质证明了目标值的一个下界并设计了 O(n~2)时间的算法来求解该下界值;最后运用预留尽可能多的空闲时间(RMST)在一台机器上的思想,设计了改进的RMST算法(IRMST)来求解该问题.通过利用数值仿真实验与RMST算法,遗传算法等其它算法及下界进行对比,验证了该算法的有效性.     

Existence and Stability of Positive PeriodicSolution of Delay Logistic Ecosystem with Feedback Control and Diffusion

1IntroductionWeconsiderthedelaylogisticecosystemwithfeedbackcontrolanddiffusionoftheformConcerningthestabilityproblemofpositivestead-stateforsystem(1.1),ithasbeendiscussedbyX.Shengli[1],whereastheasymptoticbehaviorofsolutionsofsystem(1.1)withoutdiffusionhasalsobeenconsideredbyK.Gopalsamy[2]andtheoscillationofsystem(1.1)withoutdiffusionandfeedbackcontrolcanbefoundinreference[3](K.GopalsamyandG.Ladas),Inreference[4],J.Dangpinghasgivedsufficientconditionsofexistenceandstabilityofperiodicsolut…     

具有学习效应的总完工时间流水作业问题

研究工件具有学习效应的2台机器流水作业排序问题.工件的学习效应指工件的加工时间为所排位置的指数函数.目标函数为极小化总完工时间.给出该问题的数学规划模型.同时对大规模问题给出3个启发式算法,计算结果表明,用这3个算法解决所研究问题比较有效.     

A NOTE ON COMPLETELY POSITIVE GRAPHS

1. IlltroductionPioneered by M. Hall Jr. in 195811] and investigated by A. Berman [2--4] and J. H. Drew, C.R. Johnson and Loewy[5] et al., completely positive matrices have been shown their importancenot only in the study of block designs in combinatorial analysis[6], but also in establishingeconomic model.[7].Recall that an n x n matrix A is said to be completely positive, denoted by A E CPu, ifthere edest m nonnegative column vectors hi,'', ba such thatwhere I denotes transpose. The …     

A REMARK ON THE GLOBAL SMALL SOLUTION FOR GENERAL COUPLED MAXWELL-SCHR■DINGER EQUATIONS IN IR~3

1.IntroductionandMainResultInthispaperwecontinuetostudytheCauchyproblemforgeneralcoupledMaxwellmSchrsdingerequations.Whenthespatialdimensionsarethree,weprovetileexistenceofglobalsmallsolutionfortheCauchyproblemofgeneralcoupledMaxwellSchrsdingerequationsunderLorentzgaugebyapplyingthequasi--energymethodwhichwasintroducedbyV.M.n.erieril].Basingon[2]or[3],CauchyproblemforgeneralcoupledMaxwelL'Schri'dingerequationsunderLorentzgaugecanbewrittenaswherex6R",p,urangeover0,112,3,jrangesover112,3a…     

A MUCLTI-PARAMETER SPLITTING EXTRAPOLATION AND A PARALLEL ALGORITHM

1.IntroductionConsidertheone-dimensionalDirichletproblemwherethecoefficientsoftheproblemaresmoothandsatisfyp(x)2c>0,q(x)30,xE(0,1).Let[0,1]bedividedintopsubintervalsT={(aj--1,aj):j=1,2,'',p},ac=0,ap--1.Oneach(aj--1)aj),auniformmeshrefinementwithsizehiisi…     

SOME QUALITATIVE PROPERTIES OF SOLUTIONSTO A SECOND-ORDER NONLINEAR BOUNDARY VALUE PROBLEM ON[0, ∞)

1.IntroductionUtilizingthemethodofupperandlowersolutions,WangJunyu,GaoWenneandLinZhenghuahaveestablisedinarecelltpaper[1]thefollowingtheorem:Theorem1.1LetN>0and^2--1.Thenthesecond-oafednonlinearboundaryvalueproblemWesaythatafunctiony(x)isaCIsolutiontotheboundaryvalueproblem(1.1)--(1.3),ifi)bothy(x)andly'(2)I"--,y,(2)areinC'[0, co),n)theequation(1.1)issatisfiedin(0, co),andiii)y(0)=1and:hTOOxl~'] y(x)=0.Furthermore,ifthesolutiony(x)P,,,,,,WcontinuoussecondderiVativein(0, co),thenitiscal…     

ON NORMAL EULER NUMBERS OF EMBEDDING SURFACES INTO 4-MANIFOLDS

Let N be a closed,orientable 4-manifold satisfying H_1(N,Z)=0,and M be a closed,connected,nonorientable surface embedded in N with normal bundle v.The Euler class e(v)ofv is an element of H_2(M,(?)),where (?) denotes the twisted integer coefficients determined byw_1(v)=w_1(M).We study the possible values of e(v)[M],and prove H_1(N-M)=Z_2 or 0.Underthe condition of H_1(N-M,Z)=Z_2,we conclude that e(v)[M]can only take the followingvalues:2σ(N)-2(n+β_2),2σ(N)-2(n+β_2-2),2σ(N)-2(n+β_2-4),…,2σ(N)+2(n+β_2),where σ(N) is the usual index of N,n the nonorientable genus of M and β_2 the 2nd real Bettinumber.Finally,we show that these values can be actually attained by appropriate embeddingfor N=homological sphere.In the case of N=S~4.this is just the well-known Whitney conjectureproved by W.S.Massey in 1969.