加工时间依赖工件位置的链约束单机排序问题

讨论了工件加工时间依赖工件位置的链约束单机排序问题．对于链可中断和不可中断两种情形．证明了目标函数为最大完工时间和总完工时间时该问题仍然多项式时间可解．     

加工时间具有学习效应的链约束单机排序问题

研究了工件的加工时间具有学习效应的链约束单机排序问题,在链可中断和不可中断两种情况下,均给出了目标函数为极小化最大完工时间的多项式算法。     

工件加工时间为非线性分段函数的单机排序问题

讨论工件加工时间是开工时间非线性分段函数的单机排序问题，目标函数为极小化最大完工时间，总完工时间和加权总完工时间．对于目标函数为极小化最大完工时间和总完工时间的问题，给出了求解最优排序的多项式算法，对于目标函数为加权总完工时间的问题，给出了工件间的一致关系。     

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

加工时间依赖资源的单机成组加工问题

对问题1｜pi,j=bi,j-ai,jui,j,∑i=1^m∑j=1^nj ui,j≤U,Si,GT｜∑i=1^m∑j=1^nCi,j 给出了一个有关最优解中最优资源分配的性质,并利用该性质对bi,j = b, ai.j = a; bi,j = b,ui,j = u; ai,j = a, ui,j = u 3种特殊情况分别给出了最优解。     

任务到达时间依赖资源的单机排序问题

讨论了任务到达时间依赖于分配给它的一类资源约束问题,对问题1|rj=fj(uj),∑^ujj=1≤U^A|Cmax,将已有的一个算法做了改进,对问题1|rj=fj(uj),Cmax≤C^A|∑uj给出了在任意给定排列的条件下求最优解的算法。     

带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序.     

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

讨论工件加工时间依赖于分配给它的一类资源，且加权总完工时间有限，目标函数为极小化资源总量的单机排序问题，对问题1，给出了一个有关最优解中最优资源使用的重要性质并利用该性质，对于bj=b，wj=w,aj=a这种特殊情况给出了最优算法．     

一类加工时间与位置有关的单机排序问题

研究一类工件加工时间和位置有关的单机排序问题．在这一问题中。全部工件有一个待定的共同工期d，目标函数是提前时间，延误时间和工期的加权和达到最小，即惩罚函数最小．通过对问题的分析，将其转化为指派问题，从而证明该问题具有多项式算法．并用一个例子作了说明。     

线性加工时间单机成组排序问题

讨论一类线性加工时间成组排序问题．在这一模型中，工件的加工时间是其开工时间的线性函数，全部工件分成若干组．工件的加工必须满足成组技术限制，同组工件间没有安装时间，各组间有与顺序无关的安装时间．目标函数为极小化最大完工时间．基于对问题的分析，给出了多项式算法。     

一类带有可控加工时间的单机排序问题 (运筹学与控制论)

讨论了具有学习效应的工期指派和可控加工时间的单机排序问题。工件的实际加工时间同时依赖于所排位置和所分配的资源消耗相关的函数,资源消耗分为线性和凸资源消耗2种。考虑共同工期、松弛工期和没有限制的工期3种工期分派方法。目标是确定工件最优的加工顺序、工期和资源分配量,极小化一个包含提前、延误、工期分派、总完工时间和总资源消耗的总费用函数。对于上述2种不同资源消耗函数与3种不同的工期分派方法的每一种组合,均给出了多项式时间算法。     

带有交货期和加工时间可控的单机排序问题

讨论了带有交货期和工件的加工时间可控的单机排序问题.本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序.然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的.最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nlogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序.     

一类安装时间和加工时间受资源约束的成组排序问题

讨论了安装时间和加工时间同时受资源约束的单机成组排序问题．目标函数为在满足最大完工时间限制条件下极小化安装时间消耗资源量与工件消耗资源量的总和．在讨论了问题若干性质基础上，给出了一个最优多项式算法，并用数值例子作了说明．     

带有公共交货期窗口和加工时间可控的单机排序问题 (运筹学与控制论)

讨论了带有公共交货期窗口和工件的加工时间可控的单机排序问题。假设工件的加工时间是所分配资源的线性非增函数,且分配资源会产生费用。交货期窗口的开始时间是固定且不受限制的,交货期窗口的结束时间是不确定的决策变量(即交货期窗口的大小不确定)。如果工件在窗口中完工则不产生费用,否则工件提前或延误,则会产生相应的提前或延误的费用。目标函数是极小化总完工时间,提前时间,延误时间,交货期窗口的结束时间(即窗口的开始时间与窗口大小的和)和资源分配的总费用。给出了最优解的一些性质,并且证明了这个问题是多项式时间可解的。     

随机加工时间的单机调度问题

讨论ｎ个独立工件在一台机器上加工。工件的加工时间服从正态分布,所有工件交货期设置公共交货期。目标是确定公共交货期及工件的最扰排序,使工件完工时间与公共交货期之差绝对值之和及工件完工时间之和的线性组合的期望值最小。     

带有交货期和加工时间可控的单机排序问 (运筹学与控制论)

讨论了带有交货期和工件的加工时间可控的单机排序问题。本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序。然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的。最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nl ogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序。     

带有分段线性递减加工时间和拒绝工件的单机排序问题

讨论了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中,工件的实际加工时间是关于开始时间的分段线性递减函数,目标函数是极小化被接受工件的最大完工时间和被拒绝工件的总惩罚之和。这一问题是NP-难的。基于对问题的分析,给出了一个全多项式近似策略。全多项式近似策略的计算复杂性为 O(n4L4/ε3)。
     

模糊加工时间和/或模糊交货期下的单机调度问题

分析了一类带模糊加工时间和/或模糊交货期的单机调度问题,调度目标是最小化误工任务数.为了简化计算,用模糊三角数表示模糊加工时间和模糊交货期,引入可能性理论中的必然性测度,分别在只有加工时间为模糊数、只有交货期为模糊数以及加工时间和交货期都为模糊数等3种情况下,比较任务完成时间和交货期,判断任务是否误工.指出确定性环境下的最小化误工任务数单机调度问题是模糊情况的特例.     

两个代理商松弛工期指派与位置有关负荷资源约束单机排序问题

【目的】研究两个代理商松弛工期指派资源约束单机排序问题。【方法】代理商通过竞争在同一台处理机上处理各自任务集合,各有一定数量的资源可以分派给任务。任务有待定的松弛工期,处理时间与位置有关且是所获资源量的凸函数。目标是求出任务的处理顺序、工期和资源分配方案,使得乙代理商任务中最大费用不超过给定值,且甲代理商任务最大费用取最小值。将问题转化为凸规划问题,先求出任务资源数量;再通过求解指派问题确定任务的处理顺序,进而求得工期。【结果】给出了多项式时间的最优算法,提供算例说明算法的有效性。【结论】分析表明算法的计算时间复杂度为O（n3）,其中n为两个代理商任务数中较大的一个。