Combined Timetabling Procedure and Complete Local Search for No-Wait Job Shop Scheduling with Total Tardiness

The strong non-deterministic polynomial-hard （NP-hard） character of job shop scheduling problem （JSSP） has been acknowledged widely and it becomes stronger when attaches the no-wait constraint, which widely exists in many production processes, such as chemistry process, metallurgical process. However, compared with the massive research on traditional job shop problem, little attention has been paid on the no-wait constraint. Therefore, in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems, in traditional frame work. A new efficient combined non-order timetabling method, coordinated with objective of total tardiness, is proposed for the timetabling problems. As for the sequencing one, we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms. Computational experiments showed that our proposed algorithm performed both effectively and efficiently.     

耦合约束柔性作业车间调度优化研究

为扩展工艺约束的存在形式,对耦合约束柔性作业车间调度模型构建与调度优化算法设计进行探讨。在沿用链式约束调度的形式化与图形化描述构建耦合约束模型的基础上,对耦合约束邻域结构进行设计,选取禁忌搜索算法为设计框架,围绕算法执行步骤进行设计,并采用耦合约束案例与Brandimarte测试数据验证调度优化算法的适用性与优化性。耦合约束模型构建与调度算法的探讨为多部件系统作业的调度优化提供解决方案,也为调度相关邻域的深入研究拓宽思路。     

基于局部搜索策略的车间作业调度问题的算法研究

为车间作业调度问题提供了一个快速、易于实现的近似算法．该算法基于局部搜索策略,采用特殊的邻域构造方法,即邻域的构造仅与关键路径上的工序相关．该算法找到了所测试的14个标准算例中12算例的最优解,而且在PⅡ233的计算机上每个算例的计算时间不超过1s。     

柔性作业车间多目标调度优化研究

研究了多目标柔性作业车间调度问题(FJSP),提出了一种基于Pareto的混合遗传算法,并建立了包括生产周期、总拖期时间和机床负载在内的多目标优化模型.该算法采用基于工序的编码方式和活动化解码方法,将Pareto排序策略与Pareto竞争方法结合起来.为了保证解的多样性,采用小生境技术并同时使用多种交叉方法,用Pareto解集过滤器保存进化过程中的最优个体,防止最优解的遗失.算法最后给出问题的Pareto最优解集.仿真试验证明,提出的混合遗传算法可以有效解决多目标FJSP.     

基于粒子群优化的多目标作业车间调度

为了利用粒子群优化算法解决作业车间调度问题,提出了将调度问题转化为连续优化问题的有效策略;设计了Pareto档案粒子群算法(PAPSO),该算法将档案维护和全局最好位置选取结合在一起,在档案维护过程中为每个粒子选取全局最好位置;给出了变异与PAPSO的结合新策略.将PAPSO和带变异的PAPSO应用于15个调度实例,以最小化总拖后时间和最大完成时间,与强度Pareto进化算法2等进行比较,结果验证了PAPSO在作业车间调度方面的良好性能.     

缓冲区间有限条件下的作业车间调度方法

针对缓冲区间有限条件下的作业车间调度问题,以最小化make-span为目标建立了非线性混合整数规划模型,提出了基于邻域搜索的两阶段算法对问题进行求解.算法的第一阶段为迅速找到可行解,第二阶段为基于非连通图,通过邻域搜索对得到的可行解进行优化.针对benchmark算例进行测试并与已有的算法进行对比,验证了算法的有效性.对比分析发现,如果工件的加工时间符合均匀分布,当缓冲区间容量与工件数量的比例达到20%,缓冲区间大小对调度结果的影响将会迅速变小.     

基于准时制的零等待混合Flow Shop高度问题

讨论了具有零等待混合Ｆｌｏｗ Ｓｈｏｐ调度问题,其目标是阳小化提前／拖期总成本,这是一个ＮＰ－难题。给出了问题的数学模型,同时将启发式算法和求解线性规划相结合,提出了这一调度模型的求解方法;最后给出了实验结果和结论。     

调整时间可分离的无等待FlowShop调度问题

研究了3台机器调整时间可分离的无等待FlowShop调度问题,目标函数为极小化加权完工时间和·基于对问题的分析,给出了目标函数的一般表示·对某些特殊情况,给出了问题存在多项式最优算法的充分条件·在此条件下,将单机调度问题的WSPT规则应用到无等待FlowShop调度问题,得到了求解无等待FlowShop问题最优调度的分派规则·通过反例指出了文献中的某些错误·     

一种求解带有阻塞限制的混合流水车间的禁忌搜索算法

针对带有阻塞限制的混合流水车间调度问题,提出一种禁忌搜索算法和优先级规则相结合的方法.开发了启发式调度算法求出问题初始解,应用禁忌搜索算法对工件在第一级的排序进行优化,采用优先级规则进行其他级工件的排序.实验结果表明,该方法大大缩减了搜索空间,能够较好地解决此类调度问题.     

结合优先指派规则的车间作业问题的枚举算法

车间作业调度问题是一个典型的NP完全问题,这种问题的精确求解算法的计算时间会随着问题实例规模的增大而呈指数增加.针对车间作业调度问题的难解性,给出了一个求解该问题的快速枚举算法.该算法是按照枚举算法的一般步骤来进行设计的,在设计过程中对于算法所涉及到的初始解问题、分枝问题以及剪枝策略等问题给出了旨在减少算法计算时间的解决方案.该算法找到了所测试的9个标准算例中4个算例的精确最优解.     

基于启发式信息的蚂蚁算法在车间作业调度中的应用研究

讨论了蚂蚁算法在车间作业调度问题中的应用,针对传统蚂蚁算法执行效率较低的特点,首先分析了影响因素,然后针对这些因素提出了改进方法,通过运行实例仿真说明本算法的有效性和可行性.     

基于演化多目标算法的混合流水作业调度优化

针对供应链网络优化领域中的混合流水作业调度问题提出了一种新的多目标演化优化算法。给出了这类问题的通用优化模型，在此基础上，提出了基于流程的矩阵基因编码方案，动态适应度分配机制，并引入小生境保优策略构造了算法过程，利用收敛进程参数分析了算法的收敛性能。性能分析和算例实验表明算法对于高维多目标优化问题是有效的，且能够以较快的速度收敛。     

求解置换流水车间调度问题的布谷鸟算法

分析了布谷鸟算法的优化机理和特点,针对最小化最大完工时间的置换流水车间调度问题,采用基于最小位置值规则的随机键编码方式,应用布谷鸟算法进行求解.通过选取的标准算例对算法进行了仿真测试,并与萤火虫算法和粒子群算法进行对比,测试结果表明了该算法求解置换流水车间调度问题的有效性和优越性.该方法可作为解决流水线生产调度问题的一种有效方法.     

基于遗传和禁忌搜索算法求解双资源车间调度问题

针对柔性生产环境下的车间调度问题,在考虑遗传算法早熟收敛特性和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法结合起来,提出了基于遗传算法和禁忌搜索算法的双资源作业车间的调度优化问题算法,即不仅考虑到了每个工件有几条可行的工艺路线,而且考虑到了工件的调度受到机床、工人等资源制约的影响,并用实例对该算法进行了仿真研究.结果表明此算法有很好的收敛精度,是可行的,与传统的调度算法相比较,体现出其明显的优越性.     

A SAA—based Novel Hybrid Intelligent Evolutionary Algorithm for Job Shop Scheduling Problem

Through systematic analysis and comparison of the common features of SAA,ES and traditional LS(local search)algorithm,a new hybrid strategy of mixing SA,ES with LS,namely HIEA(Hybrid Intelligent Evolutionary Algorithm),is proposed in this paper,Viewed as a whole,the hybrid strategy is also an intelligent heuristic searching procedure.But it has some characteristics such as generality,robustness,etc.,because it synthesizes advantages of SA.ES and LS,while the shortages of the three methods are overcome.This paper applies Markov chain theory to describe the hybrid strategy mathematically,and proves that the algorithm possesses the global asymptotical convergence and alalyzes the performance of HIEA.     

一种混合蚁群算法在JSP问题中的应用研究

作业车间调度问题（JSP）是最困难的组合优化问题之一,也是目前管理科学领域的热点研究问题。针对JSP问题,利用回溯相邻交换方法对传统的蚁群优化算法进行改进,同时对蚁群优化算法中的全局信息素更新规则进行调整,求解生产周期最小的排程方案。最后通过仿真实验,验证了该算法的有效性。     

基于改进遗传算法的柔性作业车间调度问题研究

针对柔性作业车间调度问题的特点,以产品的加工周期最短为目标,提出了一种改进的遗传算法,采用双子串的方式来进行编码,并且基于此给出了独特的交叉和变异法则。同时通过具体的实例仿真分析说明该算法的有效性。     

改进混合蛙跳算法求解考虑运输时间的柔性作业车间调度问题

【目的】考虑到工件在机器间的转移,对具有运输时间的柔性作业车间调度问题进行研究。【方法】建立以最小化最大完工时间为目标的数学模型,并设计一种改进的混合蛙跳算法(Improved shuffled frog leaping algorithm,ISFLA)。在该算法中,从全局和局部的角度产生高质量的初始种群,考虑运输时间的贪婪插入解码能够合理地安排工件在机器上的加工顺序。批处理的模因组搜索方法能够充分利用模因组内其他个体信息,扰动策略可以防止算法陷入局部最优。此外,基于关键路径设计两种局部搜索策略以进一步提升解的质量。【结果】通过21组不同规模的算例进行测试,测试结果证明了ISFLA的有效性。【结论】ISFLA能够有效解决考虑运输时间的柔性作业车间调度问题。     

改进型蚁群算法在Job Shop问题中的应用

应用改进型蚁群算法解决车间作业调度问题。在原有标准蚁群算法的基础上采用了新的状态转移规则,讨论了各种不同的轨迹更新规则对仿真结果的影响,并通过统计数据验证了改进型蚁群算法优于标准的蚁群优化算法。由于算法中的参数对算法的求解效率和求解结果都有一定的影响,所以对此也进行了初步的研究,得到了运行较好的参数取值范围。