作业车间调度问题的文化算法

构造用于作业车间调度问题的文化算法,模拟文化的进化实现对问题的寻优,通过算法中信念空间和种群空间的相互联系和相互促进实现求解。算法采用固定优先表编码方式,其种群空间采用遗传算法作为进化手段,采用较独特的信念提取方式构造算法的信念空间并促使其进化。将该算法应用于作业车间调度问题标准实例,证明其有效性。     

求解逾期惩罚的作业调度问题的模拟退火算法

逾期惩罚的作业调度问题是一个典型的NP完全问题，模拟退火算法是求解此问题的一种理想方法。模拟退火算法是依赖邻域结构的迭代方法，模拟退火算法对选择试验解比较敏感。文章针对找领域解，提出4种策略。算法的分析和测试表明，策略C是一种简单有效的算法。     

有不同中断时间代价的一致并行抢先调度问题

提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax)．该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景．首先证明了这个问题是一个NP难优化问题．并给出了一个时间复杂度为O(nlogn)的近似算法,其近似度为5／3．算法的特点是结合中断时间δi来应用LPT思想,而不只是把它应用到任务i的执行时间pi上,从而避免了LPT算法在最坏情形下的近似度差的问题．在算法的关键部分,运用了均分的技巧来提高任务执行的并行性,进一步提高了近似度．     

另辟蹊径求解工厂作业调度问题

为了找到一种求解工厂作业调度问题的好方法,文章首先阐述了拟物法的思想,紧接着在此思想上提出了前沿沉底法,并根据前沿沉底法对相关算法经过反复的测试后,终于找到了一种求解工厂作业调度问题的实用快速算法.此算法的提出,对于解决NP难相关的问题有很好的借鉴意义.     

资源受限工程调度问题的最新发展

许多学者对资源受限的工程调度问题这一著名的ＮＰ完全问题提出了各种解法，并对某些解法做了评价。尽管这些解法各异，但可分成两大类：一类是以线性规划、整数规划为代表的精确算法；另一类是启发式算法。根据收集的资料，对近年来国外关于这一问题的发展状况作了简要概述。     

求解工件车间调度问题的一种新的邻域搜索算法

该文提出了一种新的求解工件车间调度(job shop scheduling)问题的邻域搜索算法．问题的目标是：在满足约束条件的前提下使得调度的makespan尽可能地小．定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向．计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法．其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解．这些实例是当前文献中报导的所有规模为10工件10机器的实例．     

几何算法求解货郎担问题

本文提出求解货郎担问题的一种几何算法。它的时间复杂性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次乘法，其中ｎ，ｍ分别是点集的点数和凸包顶点数。     

MSP问题及其求解研究

提出多级图简单路径求解问题,我们称之为MSP问题.给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性.最后通过将HC问题(哈密顿图判定问题)多项式归结成MSP问题,证明MSP问题的NP完全性质.结论是MSP∈P,HC∈P.     

求解哈密顿图判定问题的一个新算法

本文给出求解哈密图判定问题（即ＨＣ问题）的一个算法及其证明。     

具有最大作业延迟的生产调度优化算法及仿真

成组作业优化调度问题中的作业根据其加工特点要求可分成若干作业类。同一类的作业连续加工，其后的作业不需要机器设置花费，而不同类的作业连续加工，其后的作业需要机器设置花费。当优化目标是最大作业延迟时，单机成组作业优化调度是HP—hard。本文在利用优化性质的基础上，提出了一种适于大规模优化调度问题的多项式时间算法。仿真实验表明该算法具有良好的性能。     

拟牛顿粒子群优化算法求解调度问题

针对资源受限的项目调度问题,将粒子群优化算法与拟牛顿优化算法相结合,提出了一种混合粒子群算法。本算法利用粒子群算法求得优化解,然后利用拟牛顿方法对所得到的解进行局部优化,以尽量达到或接近全局最优点。结果表明,本算法能够有效地求解大规模项目调度问题,具有较好的应用价值。     

基于剪枝算法解决多处理机调度问题的算法研究

针对当前算法求解多处理机调度问题的不足,从剪枝策略的角度提出了一种笨人算法。笨人算法的思路是：不断排除最差解,直到剩下唯一解。这种剪枝算法至少保证当前的选择不是最差的,并且对计算过程的最大复杂度作了一个估计。经过实验分析,对于◢N×N◣的MSP,多数情况下,笨人算法比贪心算法、遗传算法、差分进化算法的表现更为稳定和优秀,是一种有效的算法,也为相关问题的研究提供了一种新的思路。     

A genetic algorithm-based approach for solving the resource-sharing and scheduling problem

We introduce a heuristic that is based on a unique genetic algorithm (GA) to solve the resource-sharing and scheduling problem (RSSP). This problem was previously formulated as a continuous-time mixed integer linear programming model and was solved optimally using a branch-and-bound (B&B) algorithm. The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of the resources needed, and an operation may share different resources simultaneously. The problem is to select a single mode for each operation and accordingly to schedule the resources, while minimizing the makespan time. The GA we propose is based on a new encoding schema that adopts the structure of a DNA in nature. In our experiments we compared the effectiveness and runtime of our GA versus a B&B algorithm and two truncated B&B algorithms that we developed on a set of 118 problem instances. The results demonstrate that the GA solved all the problems (10 runs each), and reaches optimality in 75% of the runs, had an average deviation of less than 1% from the optimal makespan, and a runtime that was much less sensitive to the size of the problem instance.     

灾变遗传算法求解带时间窗的车辆调度问题

提出一种可以有效求解带时间窗的车辆调度问题的灾变遗传算法.遗传算法作为一种高效的启发式算法被用于解决这类组合优化问题,但是该算法存在过早收敛、易陷入局部最优等缺陷.针对此问题,在搜索过程中采用灾变算子使遗传算法跳出局部最优,并针对车辆调度问题设计一种可以直接产生可行解的交叉算子,避免染色体交叉过程中产生不可行的子代.通过仿真算例验证了所提出的算法求解带时间窗的车辆调度问题的有效性;通过与标准遗传算法、改进遗传算法和粒子群算法的比较,进一步验证了灾变遗传算法在优化性能以及算法鲁棒性方面的优势.     

多目标柔性作业车间调度问题的混合差分算法

多目标柔性作业车间调度问题属于NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,并改进了多目标函数,使其更符合实际需要。提出了一种求解该问题的混合差分演化算法,该算法针对差分演化算法易陷入局部最优现象,提出了算法早熟收敛判定方法,并且利用混沌搜索解决早熟收敛问题,突破了局部极值的限制以再次寻优计算。仿真结果表明,该算法效率高,寻优速度快,有效地解决了收敛性能和早熟之间的矛盾。     

基于两阶段调度的制造单元协同调度算法研究

针对单元制造问题,提出了一种基于两阶段的调度算法,通过过程分解和算法优化两方面实现问题求解。调度过程分为“预调度”和“整体调度”两个阶段,对大规模调度进行调度,不仅有效地降低了问题规模,同时制造单元调度结果对实际生产具有现实意义;调度算法采用了“精确”计算和“近似”求解相结合的方式,既提高计算效率又兼顾了全局优化目标。数值实验结果表明了的这一设计思路的有效性。     

变量块内部迭代算法求解零空闲流水车间问题

零空闲流水车间问题（NIFSP）是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。     

应用新型萤火虫算法求解Job-shop调度问题

Job shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对该问题提出一种新型萤火虫求解算法,分析了萤火虫算法的仿生原理,给出了萤火虫算法求解JSP问题的求解步骤,并通过典型基准测试实例对算法进行了仿真实验,并与GA和PSO算法进行了比较,验证了该算法参数少,操作简单,收敛速度快,在生产调度中有广泛的应用前景。     

基于遗传算法的Job-Shop调度问题求解

针对 Job Shop调度问题,详细讨论了遗传算法以及染色体编码方法,建立了算法模型。通过仿真实验,验证了该算法的有效性。     

遗传算法在车辆调度优化问题中的研究

车辆调度优化问题是一个有约束的组合优化问题,属于NP难题（Nondeterministic Polynomial Problem）。随着问题输入规模的扩大,求解时间呈几何级数上升,传统的优化算法本身存在着过早收敛于局部值的问题。针对这一问题在染色体编码、算子的自适应机制和约束的处理等方面对标准遗传算法进行了改进。测试结果表明,该算法提高了优化算法的质量和搜索效率,具有良好的效果。