关于单机两个客户竞争排序问题1||∑w_j~Ac_j~A:f_(max)~B≤Q的一个注记

研究了单机两个客户竞争排序问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q,证明了该问题与问题1|MA_i|∑w_jc_j及问题1|h_i,pmtn|∑w_jc_j之间是相互等价的.对w_j=p_j时的特殊情形,指出了问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q存在近似比为2的最长处理时间优先算法(LPT)且该界是紧的,对w_j任意的一般情形,指出了问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q存在近似比为4+ε的近似算法.当客户B的工件数是常数时,对问题1‖∑w_j~Ac_j~A:f_(max)~B≤Q则给出了伪多项式时间的动态规划算法.此外,指出了问题1‖∑w_j~Ac_j~A:∑w_j~Bc_j~B≤Q具有多项式时间近似方案(PTAS).     

单机主次指标排序问题(英文)

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax.在同工期且准备时间和工期具有一致性的情形下,给出了该问题的允许中断抢先的多项式时间算法.     

加工时间和工期一致的单机主次指标排序问题1｜｜∑U｜Tmax

本研究了单机主次指标排序问题1||∑U|Tmax。在加工时间和工期具有一致性的情形下，给出了该问题的多项式时间算法。     

单机主次指标排序问题1|(rj, dj) agreeable, pj = p, pmtn|∑Uj|Tmax

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax．在同工期且准备时间和工期具有一致性的情形下，给出了该问题的允许中断抢先的多项式时间算法．     

折扣加权总完工时间问题的半在线排序算法

讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间P→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同Pmin=Pmax     

问题Pm|rj,B|∑Cj的多项式时间近似算法

本文针对同型机分批排序问题Pm|rj,B|∑Cj进行了研究,给出了该问题在批容量B及机器台数m为常数情况下的多项式时间近似算法(以下简称PTAS);在B为常数时设计出了问题1|rj,B|∑WjCj的计算时间更少的PTAS．     

工件加工可拒绝的无界批量分批排序问题的几点探讨

本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑ωjTj+TP和1|B≥n,rej|∑ωj+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.     

问题1|d_j=d|Σw_jT_j的一个全多项式近似方案

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1ΣwjTj的一个O(n2)时间的近似算法,把该算法得到的目标值作为问题1|dj=d|ΣwjTj的一个上界,对问题1|dj=d|ΣwjTj给出全多项式近似方案(FPTAS).已知问题1|dj=d|ΣwjTj是一般意义下的NP-困难问题,并且已经有人对该问题给出了拟多项式时间算法,本文对已有结果进行了扩充.     

最小化最大加权完工时间重新排序研究

重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的.     

几类任务到达时间受资源约束的单机排序问题

本研究了任务到达时间受资源影响的，与时间表长有关的几个问题。对问题1|rj=bj-ajuj,∑j=1^nju≤U|Cmax的一种特殊情况给出了求任务的最优排序的算法，对问题1|rj=fj(uj),pj=p,Cmax≤C|∑j=1^nuj给出了最优算法；还给出了问题1|rj=fj(uj)|∑j=1^nujΛCmax的一个算法。     

单机排序问题1|rj,prmp|∑wj(1-e-acj)的动态在线调度

本文首先一般化了可中断的概念,并建立了相应的中断-安装重复模型,然后研究了单机排序问题1 |rj,prmp|∑wj(1-c-acj)在中断-重复和中断-安装重复模型下的动态在线排序问题,给出了只考虑当前可用信息而不是考虑全部任务信息的在线调度规则.     

用素数判定多项式不可约

本文介绍两个用素数列来判定多项式不可约的定理 ,从而把素数与不可约多项式紧密联系起来了 .定理 1　对于整系数多项式f ( x) =∑ni=0aixi　 ( n∈ N,an ≠ 0 ) ( 1 )若存在一个正整数 p >1 max0≤ i≤ n{| ai| },使| f ( p) |不是合数 ,则 f ( x)在 Q上不可约 .为证明定理 1 ,先给出两个引理 .引理 1　多项式 ( 1 )的根的模必小于u =1 max0≤ i≤ n{| ai| }.证明　当 f ( z) =0时 ,假设 | z|≥ u(因为 an ≠ 0 ,所以 u≥ 2 ) ,得| f ( z) |≥ | an| .| z| n - ( u - 1 ) ∑n- 1i=0| z| i≥ 1 . | z| n - ( u - 1 ) .| z| n - 1| z| -…     

加工时间依赖资源的流水作业资源分配问题

本研究加工时间受资源影响的流水作业时间表长问题。对问题F2|chain，∑（j=1，n）μj≤U|Cmax给出了问题求最优解的多项式时间算法。     

素数与不可约多项式

本文介绍三个用素数来判定多项式不可约的结论 ,从而把素数与不可约多项式紧密地联系起来了 .定理 1　对于整系数多项式f ( x) =∑ni=0aixi( n∈ N,an ≠ 0 ) ( 1 )若存在一个正整数 p >u =1 max0≤ i≤ n{| ai| },使 | f ( p) |不是合数 ,则 f( x)在 Q上不可约 .为证明 ,先给出两个引理 .引理 1　多项式 ( 1 )的根的模小于 u.证明　 (用反证法 )设当 f ( z) =0时 ,| z|≥ u(因为 an ≠ 0 ,所以 u≥ 2 ) ,得| f ( z) |≥ | an| .| z| n - ( u - 1 ) ∑n-1i=0| z| i　≥ 1 .| z| n - u - 1| z| - 1 ( | z| n - 1 )≥ 1 ,即　 | f ( z) |≥…     

一类资源约束排序问题

引入与研究 1| pj=fj( uj) ,∑uj U| ∑ ( wj Cj+ uj)型资源约束排序问题 .针对系统中加工顺序确定的情况 ,给出三个寻求最优资源分配的算法 ;就 fj=f和 fj=bj+ g,wj=w等情况研究系统的最优排序 .     

半线性摄动电报方程的渐近理论及应用

对二阶半线性摄动电报方程的初值问题.本交给出了一个渐近方法.证明了渐近理论及形式近似解的合理性都在时间变量无穷大时(即0≤t≤O(|ε|-1)成立.作为浙近理论的应用,我们对一个带初问题的特殊电报方程进行了研究,得到了两个|ε|-1阶渐近近似解.     

资源有限的加权总完工时间单机排序问题

本讨论资源有限的加权总工时间单机排序问题，对现在仍为OPEN问题1｜pj=bj-ajuj，∑uj≤U｜∑wjCj给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况bj=b,wj=w,aj=a；bj=b,wj=w,uj=u；aj=a,wj=w,uj=u的最优算法。     

加工时间和工期一致的单机主次指标排序问题1‖∑U︱Tmax

本文研究了单机主次指标排序问题1‖∑U︱Tmax.在加工时间和工期具有一致性的情形下,给出了该问题的多项式时间算法.     

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.     

带固定工件的单机排序问题1｜FB, rj,pmtn｜∑j Uj的多项式算法

研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,rj,pmtn|∑j Uj.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n4+m log m),其中m和n分别是固定工件数和自由工件数.