有时间窗的车辆调度问题的网络启发式算法

本文对有时间窗的车辆调度问题进行了分析,提出了以网络优化为基础的启发式算法,算法中引入重载点,把求解有时间窗的调度问题转化为求解多个有确定开始时间的车辆调度问题,利用最小费用最大流算法求解有确定开始时间的车辆调度问题,再根据检验数来调整开始时间值,并用实例进行了验证。最后对算法的适用性及进一步应用进行了讨论。     

含作业到达时间的同类机调度问题启发式算法

研究了目标函数是最小化完成时间和的同类机调度问题,其中作业到达时间可能不同.此问题被证明是强NP-hard问题.由于同类机调度是一种重要的平行机调度问题,而最小完成时间和目标是最常见的正则目标之一,因此完成时间和的同类机调度问题在相关研究领域具有非常重要的地位.为此问题建立数学模型,通过对单机和同型机的相应问题研究成果的推广,提出6个启发式算法,给出算例及其计算结果,并通过实验对算法的性能及算法适应的情形进行了分析.     

有时间窗的车辆路线安排问题的启发式算法

本文对有时间窗的车辆路线安排问题进行了分析，提出了一种利用旅行商问题的Ｃ－Ｗ算法来安排路线的启发式算法，并用实例进行了验证，最后对算法的适用性及进一步应用进行了讨论，     

含有到达时间的最大完成时间同类机调度算法

研究了目标函数是最小最大完成时间的同类机调度问题,其中作业到达时间可能不同。此问题被证明是NP-hard问题。通过对单机和同型机的相应问题研究成果的推广,提出5个启发式算法,给出算例及其计算结果,并通过实验对算法的性能及算法适应的情形进行了分析,与现有Koulamas＆Kyparisis的算法进行了比较。     

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

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

模糊作业时间的并行多机调度问题与算法研究

结合抚顺钢厂实际,利用模糊数学理论,对生产实际中的模糊作业时间进行处理,通过定理将模糊作业时间问题转换为非模糊的精确问题,利用禁忌搜索智能优化方法,对问题进行了求解,使调度计划具有一定的柔性,让管理者能够掌握调度时间范围,从而使计划调度更接近现实,大大缩短总完工时间,对于钢厂一体化管理,使连铸生产的高温铸坯,能够在允许时间范围到达热轧厂,降低了能源消耗,缩短生产周期。     

分布式环境下批处理机调度启发式算法求解

将批处理机调度问题扩展到分布式环境下,提出了批调度问题的一个新模型.模型中,工件动态到达各批处理机,且在加工之前和之后需要有运输时间.证明了该模型是NP难的,并通过问题的一个下界来衡量各算法性能.给出了分布式环境下批分配的一个启发式算法AR(assignment rule)以及一个分批准则BR(batching rule),在此基础上对问题的求解提出了若干启发式算法.仿真实验表明各算法均可以对问题进行有效的求解,加入分批准则对于算法有进一步的优化作用.     

多时间窗车辆调度问题的建模与求解

传统的单时间窗车辆调度问题模型无法描述用户空闲时间分段可选的情况,为此需要建立多时间窗车辆调度问题模型.对多时间窗车辆调度问题进行研究,建立了问题的数学模型,并基于模拟退火算法设计了一种两阶段启发式算法进行求解.该算法首先利用扫描算法求得初始解,然后利用模拟退火算法对初始解进行改进.实验结果表明该算法可以有效地求解多时间窗车辆调度问题.     

有时间窗的非满载车辆调度问题的遗传算法

有时间窗的车辆调度问题是一个典型的ＮＰ－难题,传统求解方法往往不能令人满意,本文将货运量约束和时间窗约束转化为目标约束,设计了基于自然数编码的可同时处理软、硬时间窗约束的遗传算法,实验分析获得了较好的结果。     

柔性Flow shop加权完成时间调度问题的启发式算法

使用单机松弛方法证明了,即使对于柔性F low shop加权完成时间调度问题,基于加权最短处理时间需求的启发式算法也是渐近最优的。     

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

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

基于时间约束的配送系统模型及一种启发式算法

设计配送系统时，除了使系统的总费用最小外，还要满足各需求点对时间的要求。在说明建模的假设条件后．建立考虑时间约束的配送系统模型。并根据模型的特殊结构开发出一种相应的启发式算法，最后用实际调研的数据作为一个算例对模型进行数值演算。     

A Heuristic for the Job Scheduling Problem with a Common Due Window on Parallel and Non-Identical Machines

1. INTroDUCTIONThe emergence of JIT (Just in Time) management tee~gy opens up a recency research field for the jobscheduling and production managemellt. As its farther develOPment, the earnness-tardiness job schedulingproblem becomes a hot research point over y6ars. conference [1] gives a review on job scheduling problem withearnness and tardiness penalties. Reference [2] p~s another scheduling problem for minimizing the rangeof lateness on a single machine, and reference [3] giVes a he…     

基于混沌遗传算法的自动化生产单元调度方法

针对遗传算法在求解一类带时间窗口的自动化生产单元调度问题时易出现冗余迭代、收敛缓慢等问题,将混沌搜索技术引入至遗传算法中,通过将混沌初始化、混沌扰动与遗传算法的基本操作相结合,利用混沌运动搜索精度高、遍历性好的特点来提高遗传算法的收敛速度和优化质量.本文在给出自动化生产单元调度问题的数学模型的基础上,着重讨论了混沌遗传调度算法的设计,包括编码方式、混沌初始化、交叉操作、混沌变异操作和适应度函数的计算等.最后以自动化电镀生产线为例对提出的算法进行了验证,为此类调度问题提供了有效的算法.     

基于联合视角的项目支付问题及其模拟退火启发式算法

从合同双方的联合视角出发,研究项目支付进度问题。其中,支付与项目事件相联系,任务是合理地安排支付事件、活动执行模式及事件发生时间,以使合同双方的共同收益最大化并使二者都能接受相应的安排。在对问题进行界定的基础上,构建由两个子模型构成的优化模型。针对问题的强NP-hard属性,设计包含两个子模块的模拟退火启发式算法,并在随机生成的标准算例集合上对算法进行测试,结果表明,该算法是求解问题的有效算法。最后,用一个算例对研究进行说明,得到如下结论:如果合同双方均按自身偏好进行决策,那么将会导致一种双输的结果;如果他们能够相互合作和协调,那么都可从项目中获得更高的收益。本文的研究可以为合同双方关于项目支付进度安排的谈判提供决策支持。     

基于CSP的Job shop调度算法研究

针对一类典型的约束满足问题——Job shop调度问题，提出一种CSP调度算法框架，详细讨论CSP调度算法中的工序开始时间窗、一致性预处理、搜索空间概率模型、工序排序启发、开工时间排序启发的求解方法。仿真结果表明CSP调度算法在较小的计算时间代价下，获得了FT10标准调度问题的近优解。     

基于改进遗传算法的流水车间调度求解方法

流水车间调度问题是一类经典的NP完全问题,为此提出了一种求解极小化总完工时间的流水车间调度问题的改进遗传算法.该算法采用构造型启发式算法和随机方法共同产生初始种群,结合禁忌搜索算法的局部搜索性能和遗传算法的全局搜索性能.仿真实例的结果表明该算法对问题求解的可行性和有效性.     

A Job Scheduling Model and Heuristic Algorithm for Minimizing the Range of Lateness and Makespan on Parallel Machines

ＡＪｏｂＳｃｈｅｄｕｌｉｎｇＭｏｄｅｌａｎｄＨｅｕｒｉｓｔｉｃＡｌｇｏｒｉｔｈｍｆｏｒＭｉｎｉｍｉｚｉｎｇｔｈｅＲａｎｇｅｏｆＬａｔｅｎｅｓａｎｄＭａｋｅｓｐａｎｏｎＰａｒａｌｅｌＭａｃｈｉｎｅｓ⒇ＨＵＡＮＧＤｅｃａｉＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉ...     

一种有新任务到达的多卫星动态调度模型与方法

基于动态约束满足问题,针对初始方案执行过程中任务动态到达的情况,以最大化完成任务的优先级之和,并使新任务到达后,对原方案的调整最小为目标,建立了多卫星动态调度模型,提出了模型求解方法,最后给出了仿真算例,对模型和算法进行了验证.     

A Heuristic Algorithm for the Two-Machine Flowshop Group Scheduling Problem

1 .ＩＮＴＲＯＤＵＣＴＩＯＮＴｈｅｇｒｏｕｐｓｃｈｅｄｕｌｉｎｇｈａｓｂｅｅｎａｎａｃｔｉｖｅａｒｅａｏｆｒｅｓｅａｒｃｈｓｉｎｃｅｇｒｏｕｐｔｅｃｈｎｏｌｏｇｙ (ＧＴ)ｗａｓｗｉｄｅｌｙａｐｐｌｉｅｄｉｎｉｎ ｄｕｓｔｒｉａｌｐｒｏｄｕｃｔｉｏｎｓｙｓｔｅｍｓ .ＩｎｔｈｅＧＴｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ ,ｊｏｂｓｔｏｂｅｐｒｏｃｅｓｓｅｄａｒｅｃｌａｓｓｉｆｉｅｄｉｎｔｏｇｒｏｕｐｓａｎｄａｌｌｊｏｂｓｉｎａｐａｒｔｉｃｕｌａｒｇｒｏｕｐｎｅｅｄｓｏｍｅｃｏｍｍｏｎｓｅｔｕｐａｔｅａｃｈｍ…