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

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

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

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

具有到达时间和禁用区间的单机平行批排序

研究工件带有到达时间且机器带有可用性限制(禁用区间)的单机平行批排序问题.假设机器在一些不交的时间区间上不可用.工件以平行批的形式在机器可用的时间区间上加工,并且不可中断.一个批的加工时间是这一批中加工时间最长的工件的加工时间.对任意的正则目标函数,当工件带有到达时间且机器带有可用性限制时,给出了单机平行批排序问题的一个拟多项式时间算法.     

求解多目标单机分批排序问题

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类新型的排序问题．单机分批排序问题就是n个工件在一台机器上加工，要将工件分批，每批最多可以同时加工B个工件，每批的加工时间等于此批工件中的最大的加工时间．目前只有Cheng-shuo Wang，Reha Uzsoy运用Random Key方法编码研究了单目标函数为Lmax的分批排序问题．给出组合优化中的多目标分批排序问题的一种新编码，结合模糊数学知识，运用遗传算法研究多目标分批排序问题．研究了多目标遗传算法的机制特征，进而给出求解多目标分批排序的遗传算法．     

工时依赖位置的宽容期单机排序问题

研究了共同宽容交货期的单机排序问题,即加工时间是位置的函数,所有工件的提前/延误费用相同,共同宽容交货期的开始时间和大小待定,目标函数最小化的总惩罚费用(包括提前、延误、宽容交货期的定位和大小费用四部分).并给出了最优排序的性质,提出了一个多项式时间算法.     

有时间窗约束单车场单车型非满载车辆调度问题的遗传算法

有时间窗的车辆调度问题是一个典型的NP难题,一直成为运筹学与组合优化领域的前沿与研究热点问题,但传统的方法往往不能令人满意,利用遗传算法解决单车场单车型有时间窗约束的非满载车辆调度问题,构造了有创新性的染色体结构,并在遗传算法的迭代过程中与启发式算法交叉应用,现实应用中获得了很好的效果.     

加工时间恶化的单机成组排序问题

讨论了一类在成组技术条件下，工件的加工时间恶化的单机排序问题。工件的加工时间是开工时间的线性函数，同时工件组的安装时间也是开始安装时刻的线性函数，同组工件间必须连续加工且没有安装时间，不同组工件间连续加工时有安装时间。基于对问题的分析，给出了多项式算法。     

并行机优化调度问题的新算法

将调度规则的简洁性与遗传算法的强大搜索能力相结合,提出一种能用于最小化拖期任务数并行机调度问题的基于遗传的新的调度算法,并用计算实例表明了该调度算法优于迄今最好的启发式算法,并能适用于大规模并行机调度问题,本算法计算量小,具有很强的鲁棒性。提出的基于遗传的调度算法不仅能用于生产调度领域,在大规模数值计算及计算机网络技术等方面都有很好的应用前景。     

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

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

一种改进的人工免疫算法在模糊Flow—shop调度问题上的应用

为了克服传统的遗传算法和人工免疫算法的不足，提出一种改进的人工免疫算法。此种算法在进行亲合力计算前利用生成的亲和度矩阵排除相似抗体，大大减少运算量。用此种改进的人工免疫算法优化寻优过程，研究了处理时间不确定并且具有不同交货期窗口的Flow-shop的提前／拖期调度问题。最后，仿真实验验证了算法的有效性。     

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

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

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

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

离散加工时间单机多准则下可控排序问题

讨论了工件具有离散可控加工时间的单机多准则下的排序问题. 目标函数分别为极小化完工时间和与完工时间偏差和的线性组合, 极小化等待时间和与等待时间偏差和的线性组合, 极小化提前时间、延误时间、最早交货期及窗口长度的加权和, 极小化提前时间、延误时间及公共工期的加权和. 用数学规划的方法证明了四类多准则下的单机排序问题可以转化为指派问题,从而这四类问题都多项式时间可解.