无空闲Flowshop带折扣加权排序的算法

讨论了目标函数为带折扣的加权总完工时间的无空闲Flowshop排序问题,对其中四种特殊情况给出了最优算法.第一种问题是机器满足单调递增优势关系,第二种问题是机器满足单调递减优势关系,第三种问题是机器满足先递减、后递增的优势关系,第四种问题是机器满足先递增、后递减的优势关系.     

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

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

一类带折扣加权总完工时间单机排序问题

讨论了工件加工时间和排列中位置相关的单机排序问题．对工件加工时间和位置相关的两个线性模型Pi(v)=ai-biv和pi(v)=aiv^-b进行了讨论，目标函数是带折扣的加权总完工时间,并且对工件加工时间与给定权值之间具有一致关系的某些情况给出了最优算法。     

带尺寸批排序问题的一个最优算法

首次对问题1｜B,sj,pj=1｜∑Cj的一种特殊情况——工作可拆分的情形进行了研究指出此时该问题是多项式可解的,并且给出了该问题的多项式时间的算法。     

无等待流水调度问题迭代启发式算法

针对以总完工时间最小化为目标的无等待流水调度问题(缩写为NWFSP),提出了两个迭代启发式算法(缩写为IHA1、IHA2).一个是以FL(described by Framinan and Leisten,OMEGA,2003)启发式算法产生的解作为初始解,另一个是以WY(described by Hoon-shik Woo and Dong-soon Yim,Computers & Ops Res,1998)启发式算法产生的解作为初始解,然后两者均应用RZ(developed by Rajendran and Ziegler,European Journal of Operational Research,1997)和FL插入以及成对交换技术进行多次迭代来改善解的质量.为了评估,我们使用了Taillard's基准程序随机产生了大量实例,实验结果显示,IHA1和IHA2在解的性能上优于经典的RC1、RC2、PH1(p)算法,随着问题规模的增大,对解的质量改善得更好.     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

具有链形约束排序问题的最优算法

本文给出了问题１｜ｃｈａｉｎｓ｜∑Ｗ（１－ｅ＾－ｒｃｊ）的一个最优算法，推广了文「１」中的一个结果。     

单台机器速度可选择的排序问题

研究一类单台机器具有速度可选择约束的排序问题。引进了有关记号，给出了该问题解的概念。ｍ＝１的情形问题１｜ｓｐｅ．｜ΣＣ＿ｊ和问题１｜ｓｐｅ．｜Σｗ＿ｊＣ＿ｉ具有多项式时间算法，即为所谓的Ｐ问题，但对ｍ为一般情形其计算复杂性尚未解决。     

Flow shop排序问题F2｜prmu｜∑ωjCj的一个启发式算法

给出Flow shop排序问题F2|prmu|∑ωjCj的一个启发式算法，其最坏情况的界为2，且是紧界。此外，还讨论了它的三种多项式可解的条件。     

带不可用时间段的不允许等待柔性流水排序问题

给出了极小化时间表长带不可用时间段限制的不允许等待柔性流水车间排序问题的模型,并对其算法复杂性进行分析.分析的结果表明,该问题在几乎所有情况下都不存在具有有限最坏比的多项式时间算法.     

A genetic algorithm for the flowshop scheduling problem

The flowshop scheduling problem is NP complete. To solve it by genetic algorithm, an efficient crossover operator is designed. Compared with another crossover operator, this one often finds a better solution within the same time. Supported by the National Natural Science Foundation of China and 863 High Technology Project of China Qi Yuesheng: born in 1967, Ph. D.     

有分离调整和移走时间的两机器no-wait流水作业最大延误问题

以最大延误为目标函数，讨论了两机器no—wait流水作业问题解中的工件排列应满足的条件，并根据这些条件给出了几个近似算法．     

交换机中周期流优化调度问题的复杂性

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.     

PCB机器人装配系统的优化调度

研究了印刷电路板(PCB)机器人装配系统中的优化调度问题，针对这类机器人装配系统，提出最小平衡法，并通过算例验证了该算法的有效性。     

用GA算法解不同交货期窗口下的E/T调度问题

针对准时生产制下提前 /延迟 ( E/ T)费用的生产排序与调度问题 ,对不同交货期窗口下 E/ T指标的单机调度问题进行了分析 ,给出了在给定加工顺序条件下求解最优加工时间的动态规划算法。在此基础上 ,应用 GA( genetic al-gorithms)算法实现了求解。为提高算法优化性能 ,针对问题本身特性 ,分别从关键参数的选取 ;交叉操作的动态控制 ;变异操作的优化 3方面提出了相应改进策略。最后利用计算机仿真对算法性能进行研究 ,并得到一些经验性结论。仿真结果表明 ,该算法在优化性能和时间性能上均能满足工程上的要求。     

转盘上的Flow-shop排序问题的复杂性

讨论转盘上的Flow-shop排序问题,当运送不相等且只有一台机器的情况下,转盘上的Flow-shop排序问题是强NP-困难的.     

关于"Fm|prmu|Cmax问题"的算法

Fm|prmu|Cmax,即m(m>2)台机器同顺序加工n个工件问题是一类重要的车间作业排序问题.对于给定加工顺序的n个工件的排列排序,排序时间表长即任务的最后完工时间的计算可以通过与问题对应的有向图的关键路的计算得到.本文从关键路的结构特点和性质出发,提出了在关键路的基础上将前后相邻的两个工件的加工时间进行比较,然后择优排序的方法,使Johnson SM算法可以在多台机器上得到一定程度的推广,从而使该问题的解法得到明显简化.