带约束的平行机排序问题

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

一种工件可拒绝的有界批量分批排序问题研究

研究了一类极小化加权总完工时间的可拒绝分批排序问题.首先证明了该问题是NP-难的,然后对于所有工件的加工时间相同的情况,给出了时间复杂性为O（n2）的动态规划算法,在此基础上,对于工件有两种到达时间的情况给出了多项式时间算法.     

带机器准备时间的同类机在线与半在线排序问题

研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题，目标函数为极小化最大机器(工件)完工时间。对于在线情形，证明了LS算法的最坏情况为ρ=｛（1 √5）/2，m=2,1 √2m-2/2,m≥3，并且当m=2，LS算法是最好的近似算法；当m=2，3，…，6时界是紧的，特别地，当s1=s2=…=sm-1,sm≥l时，证明了LS算法的最坏情况界为ρ=｛（1 √5）/2，m=2,3-4/m 1,m≥3，而且界是紧的；对于已知加工时间递减的半在线排序问题，证明了LS算法的最坏情况界为2—2/(m 1)。     

复合两信息的同类机半在线排序问题

研究了两台同类机的一个半在线排序问题，当预先知道所有工件的加工时间总和（sum）与最大工件的加工时间（max）及目标为极大化最小机器完工时间的情形时，证明了此问题的竞争比为（3s＋2）／（2s＋2）的半在线算法．     

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

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

关于5色K_4问题的两个充要条件

设KN是具有n个顶点的完全图，f（n）是满足下列条件的最小正整数：对于任意的正整数m≥f（n），存在Kn的一个m边着色，使得Kn中的任一个巧至少含5种颜色．Erdoes和Gyarfas给出了f（n）的上下界：2/3n〈f（n）〈n；并且证明了f（9）=8．唐明元证明了f（10）=9；并且改进了f（n）的下界：f（n）〉2/3n＋1．作者进一步改进了f（n）的下界：当n≥20时，f（n）〉1/8（6n-5）．给出了关于5色K4问题的两个充要条件．     

风车的δ-最优性

给出了关于风车的一组标号,证明了风车wm^n（m≥3,m≠4,5）是δ-最优的．     

单机分族分批排序的最小误工个数问题

文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O(mb(n/m)2m)的动态规划算法。     

一类具有学习效应的分批排序问题

本文讨论了分批排序中机器具有带学习效应,目标函数为极小化加权总完工时间的几个问题．就所有工件的加工时间都相等的这一特殊情况,给出几个算法,并证明了算法的最优性．     

一类最优排序具有∧型或∨型特征的随机单机调度问题

本文讨论了一类加工时间随机、机器随机故障的单机调度问题．其目标函数为：（ｉ）完成时间的平方和，（ｉｉ）平均完成时间的平方，（ｉｉｉ）平均完成时间的线性组合的期望．文中首先给出了当与机器随机故障相关的点过程为广义泊松过程时，目标函数的确定形式，然后给出了使目标函数最小的最优排序依加工时间的期望具有∨型或∧型特征的条件．     

Parallel Machine Scheduling with Special Jobs

Introduction Parallel machine scheduling problems arise in many fields, including service and manufacturing systems. A parallel machine scheduling problem has a sequence of n jobs with processing times { p1 , p 2 , ... , p n } to be processed on m paralle…     

批处理机上有就绪和截止时间的等长度工件排序

一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表.就该问题,Baptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广Garey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法.算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策.     

Minimizing Maximum Lateness on Unbounded Single Batching Machine with Family Jobs

The scheduling problem on a single hatching machine with family jobs was proposed.The single hatching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The batch size is assumed to be unbounded.Jobs that belong to different families can not be processed in the same batch.The objective function is minimizing maximum lateness.For the problem with fixed number of m families and n jobs,a polynomial time algorithm based on dynamic programming with time complexity of O(n(n/m + 1)m) was presented.     

最大化接收工件总权值的批处理机在线排序

研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p0,一个到达时间r_j≥0,一个权值w_j0,一个必须交货期d_j0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m~2-m)~(1/2)/(2m~2-m).     

流水作业由二台柔性机器组成时的极小完工时间之和问题

该文考虑下述由2台机器组成的流水作业问题:n个相同工件需依相同次序在机器1、2上共进行3次加工.工件j的第一次加工在机器1上进行,所需时间为p1;其第二次加工或单独在机器1上或单独在机器2上进行,当工件j的第二次加工在机器1上进行时,所需时间为p12,当工件j的第二次加工在机器2上进行时,所需时间为p21;其第三次加工需在机器2上进行,所需时间为p2.要求适当安排这n个工件的加工方式以使它们的完工时间之和达到极小.对该问题作者对应不同情况给出了不同的最优解法.     

锁定初始调度的紧急工作单机重调度问题

对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.     

应用混合蚁群算法求解并行批处理机组批与调度问题

晶圆制造系统的批处理机具有长加工时间的特征,其调度性能指标对车间总体绩效有重要影响.批处理机调度分为组批与批次调度.针对工件的动态到达特性导致组批困难,提出了一种混合型蚁群算法.利用该算法的全局并行搜索能力对工件进行组批,并使用BATC算法对批次进行调度,可以解决多产品并行批处理机调度问题.以工件总拖期最小为性能指标,通过实例仿真,对蚁群算法性能进行分析评价和比较.结果表明,所提出的算法具有有效性和实用性.     

宽容交货加权超前延误单机排序问题

该文研究下述宽容交货加权超前延误排序问题:n个工件具有一共同的宽容交货期,任一工件在宽容交货期内完工不受罚,超前或延误则受罚,惩罚系数依赖于工件.排序目标是找一个最优序和最优宽容交货区间位置使最小化加权超前延误惩罚之和.证明它是NP-Completeness的,并给出一伪多项式算法,从而获知所研究问题是一般意义下NP-Completeness的,也使该类问题的复杂性界限更清楚.     

链组约束下部分批处理平行机在线排序

研究了一台是批处理机而另一台是正常机器、工件具有链组约束、最小化时间表长的两台恒同机在线排序问题.给出该问题竞争比为(5+1)/2的最好可能的在线算法.