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

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

Flow Shop成组排序问题的调度算法设计及其界的估计

讨论Flow Shop成组排序问题F2│prmu,s,pkij=pij,GT│∑ωjcj.基于WSPT规则,给出求解该问题的一个启发式算法,并证明2是该算法的一个上界.     

可拆分平行机排序问题的一个启发式算法

为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标.在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工.与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题.借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配.通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策.     

一类调整时间可分离的Flow Shop 排序问题F3│S│Cmax的最优算法

讨论调整时间可分离的Flow Shop排序问题F3│S│Cmax，对其一类特殊情况给出了最优算法。     

单件车间排序问题的一个启发式算法

本文提出了一个启发式算法,经计算表明,这个方法对于以加工周期为目标函数的单件车间排序问题,效果是比较好的。     

一种极小化∑wjCj的分批排序问题的算法

讨论了单机分批排序问题中目标是极小化加权总完工时间的问题．对于所有工件的加工时间都相等的情况，分别对常数个到达时间和任意个到达时间的情况给出了两个最优算法，并给出了其算法复杂性．     

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

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

有重叠的两抓钩周期性排序问题的启发式算法

抓钩排序问题不同于古典的排序问题,只有一个抓钩和一种产品,它仍然被证明为ＮＰ难题,对于有重叠区域的两抓钩周期性排序问题,迄今尚无法用数学模型直接求解。为了寻找出好的排序,提出了一种启发式算法以及求解有重叠两抓钩周期性排序问题。该方法把问题分解成相应序列的子问题,并对每个序列化建立和求解一个整体问题的线性规划模型,在序列空间中,通过寻找好的序列以得到最佳的排序。量化的示例表明所使用的方法是高效的。     

一种极小化ΣwjCj的分批排序问题的算法

讨论了单机分批排序问题中目标是极小化加权总完工时间的问题.对于所有工件的加工时间都相等的情况,分别对常数个到达时间和任意个到达时间的情况给出了两个最优算法,并给出了其算法复杂性.     

一类单机排序问题的算法研究

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

工件带到达时间和服务器的平行机排序问题复杂性和启发式算法

研究带到达时间和单服务器的平行机排序问题，工件在加工之前均有一定的安装时间，且所有安装时间均由单服务器来完成．证明在只有两台平行机的情况下，带到达时间和单服务器的平行机排序问题是强NP-困难的，对于有m台平行机的情况，给出一种改进的启发式算法，并证明该算法的紧界为2．     

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

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

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

针对以总完工时间最小化为目标的无等待流水调度问题(缩写为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)算法,随着问题规模的增大,对解的质量改善得更好.     

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

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

排序问题Fm‖Cmax的几种启发式算法在最坏情况下性能比上界的可达性研究

Ｇｏｎｚａｌｅｚ和Ｓａｈｎｉ已证明：当ｍ≥３时，排序问题ＦｍＣｍａｘ是ＮＰ困难问题，没有好算法。因此，很多学者提出了多种简单易行的启发式方法求这类问题的次优解，且对其中的ＧＳ算法和ＲＳ算法证明了在最坏情况下性能比Ｃ＊ｍａｘ（Ａ）／Ｃ＊ｍａｘ的上界不超过｛ｍ／２｝＊。本文用同一例子证明，对这两种算法，这一上界是可达的。     

定位-运输路线安排问题的一种启发式算法研究

定位-运输路线安排问题(LRP)是分销网络设计和物流管理决策中的难题,属于NP难问题,求解有一定难度.文章通过构造辅助函数对优化问题约束条件的处理,基于分层次实现多个目标的思路将LRP看作一个整体,利用具群体智能的粒子群算法进行求解,避免了基于两阶段算法的不足,减小了在进化过程中停滞于局部最优解的概率.为粒子群算法在大规模组合优化问题中实际应用做了有益的尝试.     

极小化工时恒等的加权总完工时间的分批排序

本文就分批排序中最小化加权总完工时间的几个工时恒等的问题分别给出其最优算法.     

单机排序问题1｜rj｜Lmax的分枝定界算法

给出了单机排序问题1|rj|Lmax的分枝定界算法。     

集合覆盖问题的一种启发式算法

给出了完备策略的概念，并提出了一个求解集合覆盖问题的启发式算法，对该算法的合理性、时间复杂性以及精度进行了分析。用该方法可以求解其它的NP困难问题。     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。