生产调度问题的模糊满意优化

研究了生产调度的模糊多目标优化问题．分析了生产调度问题中的优化目标和系统约束的模糊性，分别定义了其模糊满意度，形成了一类具有模糊目标和模糊约束的多目标优化模型，运用模糊优化算法进行求解，对一算例进行了仿真研究，验证了该算法的有效性。     

非对称模糊加工时间工期指派调度优化问题的一类多项式求解算法

针对工件加工时间为非对称模糊数,极小化提前完工惩罚和拖期完工惩罚之和的均值的单机工期指派调度优化问题展开研究.证明了当模糊加工时间具有相同宽度比时,该问题是多项式可解的,并 给出了多项式求解算法.同时根据历史数据,构造了工期指派问题的调度模型,并利用所给出的算法求得最优解,从而 表明所提出的模型和算法的有效性.      

具有加工顺序约束和非对称模糊加工时间的工期指派调度方法

研究了工件加工时间是非对称模糊数、工件间具有优先加工顺序约束、目标函数为极小化提前完工惩罚和拖期完工惩罚和的均值的单机工期指派调度优化问题.证明了当模糊加工时间具有相同宽度比、优先加工约束关系为树状约束时,该问题是多项式可解的.进一步,当优先加工顺序为一般约束时,基于线性规划松弛技术,设计了近似比为2的近似算法.      

单机模糊交货期调度问题最优解性质的分析及证明

每个工件依据其完成时间有一个满意程度.单机模糊交货期总加权满意程度最大化问题是一个NP-难问题.当工件的参数满足一定条件时,最优解中相邻工件的排列顺序也可以确定,从而简化问题的难度.本文对最优解的性质进行了分析和证明.     

机器在一段时间不可用条件下的单机调度问题

文章对机器在一段给定时间内不可用情况下部分可恢复模式的单机调度问题进行了研究,当目标函数是最小化调度长度时,首先证明了LPT规则的误差上限是α/2,并举例说明该界限是紧的;同理可证该规则对不可恢复模式调度问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例;其次提出了一个启发式算法,该算法以LPT规则得到的解作为初始解,并结合基于成对交换技术的邻域搜索对解进行改进;当目标函数是最小化加权完成时间之和时,首先证明了最优调度的一个性质,并据此提出了动态规划算法。     

多共同工期分配调度问题算法研究

为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该问题可解。该问题是多项式可解的,并给出了具体求解算法。     

具有模糊交货期的平行机排序问题

研究了一种具有模糊交货期的平行机调度问题,目标函数是最大模糊延误修正值,并对相关的模型给出了算法。为了计算方便,文章采用模糊交货期的隶属函数与任务的完工时间之间的关系,判断任务是否误工。     

关于最小可行图的一个结果

给出了关于（Ｘ１，Ｘ２，Ｘ３，Ｘ４）的可行图Ｇ＝ＵＧｉ是最小可行图的充分必要条件：Ｇ是连通单圈图；或Ｊ∈（１，２，３，４），当∩Ｘｉ≠时，∩Ｇｉ是树，对任意整数ｎ给出了关于（Ｘ１，Ｘ２，…Ｘｎ）的最小可行图的若干性质，推广了已有的结果。     

两台同型机多阶段维护调度问题的若干结果

研究了2种类型的机器维护:一种为周期性维护,另一种为决策维护.对于周期维护最小化时间表长问题,证明了经典的FFD算法是一个很好的启发式算法,并且得到了该算法的一个上界.对于决策维护最小化总完工时间问题,分析了SPT算法的界.特别地,对于单机并且机器仅需要2次维护的情况,给出SPT算法的界不超过11/9.     

带约束的平行机排序问题

讨论了带资源约束和机器准备时间的平行机排序问题，资源约束是指每个机器最多加工κ个工件．首先对一般情况下的同型机的PLPT排序进行了讨论；并首次对同类机排序进行了研究，给出了一个FLPT近似算法，同时对m=2时证明了PLPT排序的最坏情况紧界是2．     

最小化时间表长的平行机调度近似算法研究

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.     

模糊环境下单机调度中的总提前完工量问题

在工件的加工时间及工期均为模糊参数的情况下,研究了单机调度中的总提前完工量问题.当工件具有共同工期及相同提前隶属水平时,给出了使得总提前完工量达到最大的最优调度;当工件具有共同工期及不同提前隶属水平时,给出了调度为最优的必要条件,并构造了求解该问题的分枝定界算法.     

允许中断的同速机调度问题的一个最优算法

讨论工件有不同准备时间,加工允许中断的同速机调度问题,目标函数为最小化时间表长.提出了一个算法,并证明了该算法为最优算法,该算法中工件中断的次数至多为Nn次,计算的复杂度为O(Nn logn).最后给出一个实例加以说明.     

各机器上具有相同加工时间F1oW Shop 调度问题

由m台机器构成的Flow Shop，当工件在各机器上加工时间相同时，直觉上，等价于单机问题。本文推测单机情形最优解的性质及其确定策略也应适合此调度模型。本文就一些目标函数验证了这一推测。     

可变费用的单机等待损失排序问题

证明了可变费用的单机等待损失排序问题１‖Σｆ＿ｉ（ｃ＿ｉ）是ＮＰ－ｈａｒｄ；给出了一般情形下工件优先安排加工的两个判别条件；对几种特殊情形给出了多项式时间算法或最优解的判定条件。     

具有传递时间变工时的单机排序问题

确定了具有传递时间变工时的单机排序问题是ＮＰ－完全的，且讨论了它的一些特殊情况。     

具有相同加工时间单机调度最优交货期和最优排序的确定

研究了工件加工时间相同的确定单机调度最优交贷期和最优加工顺序的问题,且目标函数基于交货期和工件交货时间不准的情况。利用HLP不等式提出了时间复杂度为O（n^2）的最优算法。     

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.     

任务无准备时间最小化加权最大延误单机调度问题的若干结果

研究任务无准备时间最小化加权最大延误的单机调度问题,给出逆向最小带权延误排序法并证明其最优性.随后,引入延误差函数概念,借助它给出简化的基于延误差函数的排序算法.特别地,对于工期相同的情形,给出更简便的权值关于期限正态分布算法.最后,借助实例说明了上述算法的应用.