用单亲遗传算法解具有窗口式交货期的多机加工排序问题

具有窗口式交货期的加工排序问题是一个强NP困难问题,传统方法的计算效果往往不能令人满意.采用基于整数编码的单亲遗传算法较成功地解决了这类窗口式交货期的单机和多机加工排序问题,并讨论了该算法的计算复杂性是属可计算的.文中的算例表明,该算法是实际有效的.     

交货期固定的工件准时完工数——最大排序问题的多项式时间算法

给出了求解交货期固定的工件准时完工数最大的排序问题的多项式时间算法。     

带有交货期窗口的调度问题及算法

对不同交货期窗口下的提前／拖期单机调度问题进行了分析,给出了最优序列中相邻工件对所满足的必要条件,提出了两个优先级法则,并利用优先级法则设计出遗传算法的交叉算子,在文章的最后,给出了实验结果和结论．     

交货期窗口下的并行机调度问题的遗传算法

给出了一种求解不同交货期窗口的并行机调度问题的混合遗传算法，根据问题的特征采用扩展排列编码方式表示工件的分配和排列，利用给出的调度优先级规则和最好适应值规则相结合的启发式算法对每台机器上工件的顺序进行调整，实验表明所给的算法是有效的。     

公共交货期窗口下提前／拖期问题单机调度新算法

在证明关于单机问题最优排序和最优公共交货期性质的若干定理基础上,提出了求公共交货期窗口下,提前．拖期都有惩罚的单机零件排序问题最优解的新算法。最后数值例子介绍了算法的使用。     

带有交货期窗口模糊加工时间的Flow-shop调度问题

研究了处理时间不确定且具有不同交货期窗口F low-shop的提前/拖期调度问题。采用三角模糊数表示不确定性信息,运用模糊数的加法和取大运算建立了问题的模糊规划模型。通过“Lee-L i”法转化为精确的目标,采用遗传算法寻优。仿真实验验证了算法的有效性。     

用遗传算法解决在并行机上带有不同交货期窗口的Job-Shop调度问题

本文讨论了不同交货期窗口下的提前／拖期并行机调度问题,提出了染色体用工件编号进行编码规则,给出了用稳步遗传算法求解上述问题的方法,仿真实验表明了算法及编码规则的可行性和有效性。     

带公共交货期窗口的提前/拖期非等同多机调度问题

提出了公共交货期窗口下提前 /拖期惩罚的多台不同设备情形的零件排序模型 .在分析相应单机问题最优排序和最优交货期性质的基础上 ,证明该多机零件问题实际上蕴含着使系统 makespan达最小的多机零件排序问题 .由于使系统 makespan达最小的并行多机零件排序问题已被证明是 NP完全问题 ,因此提出了求解该零件排序问题的一个启发式算法 ,该算法计算复杂性低且对并行多机零件排序问题同样适用 .最后给出了两个数值例子 .     

不确定条件下不同交货期窗口的Flow Shop调度

研究了具有不同交货期窗口的Flow Shop的提前／拖期调度问题，并考虑了处理时间的不确定性。采用三角模糊数表示不确定性信息，引入两种模糊运算，建立了问题的模糊规划模型，并采用“中间值最大隶属度”的算法将模糊规划模型转化为清晰的非线性规划模型。针对清晰的数学模型提出了基于遗传算法的优化方法，最小化对所有工件提前／拖期惩罚。最后，大量仿真实验验证了算法的有效性。     

一种区间数线性规划的满意解

针对目标函数和约束条件均为区间数的线性规划问题,提出了一种基于模糊约束满意度的求解方法,把区间数线性规划卖座经为确定型的一般参数规划问题来求解,决策者可以根据自己的主观判断和客观情况,对目标函数优化水平和约束条件满意水平作出不同的估计,从而得到在相应情况下的满意解,使决策过程更具柔性。     

具有交货期限的占线订单加工

探讨一类占线订单加工问题，具体分析当订单交货时间具有一定上限约束时的不可中断和可中断两种模型。对于不可中断模型，证明先到先服务策略在两种不同交货期限约束时分别是最优策略与最优占线策略；对于可中断模型，提出了基于先到先服务原则的可中断策略，并证明当交货期限小于3倍加工时间时该策略具有竞争比3／2。     

基于PSO-H优化算法的单机E/T调度问题

经典的粒子群优化算法是一个有效的寻找连续函数极值的方法。其在离散空间的应用还很不成熟。主要针对公共交货期下E/T(Earliness/Tardiness)指标的单机调度问题进行研究,并基于粒子群与启发式集成的优化算法(Particle Swarm Optimization integrated with Heuristic:PSO-H)对该问题进行求解。启发式信息由工件加工时间和拖期惩罚构成,它对算法的寻优性能有明显的改善。同时,采用OR-Library中的标准算例对该算法进行仿真实验,显示出理想的寻优结果。     

MPS上作业的分配和调度问题

多处理机系统MPS(MultiprocessorSystem)上作业的分配和调度问题是其运行效率的关键.本文讨论的是具有不相容性作业集的作业分配和调度问题,提出了一种启发式方法及其定量分析技术,并证明了相关定理和若干推论.     

具有时间窗口约束的并行机床调度问题研究

具有时间窗口约束的并行机床调度问题可以被描述为在M台互不相同机器上安排加工N个工件。每个工件只能在一个给定机器子集中的一台机器上加工，且加工过程只能在给定的离散时间窗口内进行，并且工件的加工时间长度和时间窗口约束与加工机器有关。为了解决该问题，本文给出一种集成约束规划与禁忌搜索的搜索算法，其中约束规划系统被作为验证解的可行性和确定变量的值，而禁忌搜索过程被用来对解空间进行搜索。讨论禁忌搜索过程中的初始解产生、邻域结构、禁忌列表、解空间搜索等算法设计问题。最后给出算法在不同问题实例上的算法效率比较及分析。     

链优先约束工件单机随机排序问题

讨论单机随机排序问题，目标函数为确定工件的排列顺序使工件的加权完工时间和的数学期望最小。设工件问具有平行链优先约束，机器发生随机故障。考虑两种情况，第一种情况是链不允许中断．第二种情况是链允许中断，对两种情况分别给出最优算法。     

有交货期的单件车间调度问题的逆序算法

提出了一种以“加工效率”为主要参数,并引入“虚工序”、“虚机器”求解有交货期的单件车间调度问题的逆序算法． 经分析实例验证,该算法具有一定的优度,并且在工程中是可行的．     

并行多机加权成套订单数极大化的混合遗传算法

从实际应用出发,提出了在相同的并行机上加权成套订单数极大化的排序问题,建立了该问题的整数规划模型,并设计了一种有效的混合遗传算法.还通过一个算例对这类排序问题和所提出的算法进行了说明,计算结果表明了该算法的有效性.     

有时间窗约束车辆调度优化的一种禁忌算法

针对有时间窗的V SP问题提出了一种禁忌算法,本算法运用了多初始解和全局禁忌表等各种措施来减小解的不稳定性和扩大搜索范围,并根据容量约束和时间窗约束性质的不同,结合惩罚函数和各约束的性质来联合控制车场的分配。给出了两组具有代表性的试验数据,并与其他算法优化时间窗V SP的实验结果作了比较。结果表明,此禁忌算法是解决有时间窗约束的一条有效途径。