作业车间调度转换瓶颈算法的不可行解问题

文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法。它是基于反复的解决某些单机调度问题。然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况。另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解。     

作业车间调度转换瓶颈算法可行性研究

讨论了转换瓶颈( SB) 算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan( 完工时间) 问题的有效启发式算法。它是基于反复地解决某些单机调度问题这样的子问题。然而所解决的单机调度问题的解可能会导致算法最终得不到可行解, 即使是单机调度最优解也可能得到不可行解。为此, 给出了一个简单的反例证明了产生不可行解的情况, 并对产生不可行解的原因作了详细分析。该研究有利于对转换瓶颈技术进行更好的理解和应用。     

作业车间调度问题的一种混合式算法

描述了一种解决作业车间调度最短完工时间问题的混合式算法．该算法基于禁忌搜索和转换瓶颈技术．算法中利用了多种禁忌搜索方法．为了得到更好的结果，算法中还引入了倒转技术．从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内，对多个实例得到比当前解决该问题的最高效的启发式算法之一的TSSB算法更好的结果．     

一种基于禁忌搜索技术的作业车间调度算法

描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法．该算法基于禁忌搜索技术．算法中利用了新的禁忌搜索方法．从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内，对多个实例得到比当前没有用转换瓶颈技术的禁忌搜索中最好的算法之一的TSAB算法更好的结果．     

作业车间调度问题的一种启发式算法

论文描述了解决作业车间调度最短完工时间问题的一种快速有效的启发式算法。该算法基于一种优先指派规则,并利用了往前看的思想。从对一组问题标准实例的实验计算结果看,该算法在很短的计算时间内,对多个实例得到最优解或近优解。     

一种基于禁忌搜索的作业车间调度算法

文章描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法。该算法基于禁忌搜索技术和前瞻思想,为了得到更好的结果,还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比2004年提出的ISSB算法和另一种基于禁忌搜索的TSAB算法更好的结果。     

柔性作业车间调度问题的一种启发式算法

为了研究多目标柔性作业车间调度问题,基于甘特图和搭积木经验进行了分析,提出了一种组合优先规则和基于此优先规则的启发式算法.组合优先规则面向完工时间、关键机床负荷和总负荷三个指标,改变规则中各数据项的比例可调整三个指标所占的比例;算法采用随机方式调整三个指标的比例,并微调最优解对应的比例.能随机产生多个高质量调度解.算法...     

一种基于混合遗传算法的车间调度算法

为了克服单独的遗传算法用于车间作业调度缺点,提出一种遗传算法与启发式算法结合的混合遗传算法,在运用该算法的过程中给出了适合的遗传操作和启发式规则的应用方法。结果表明：混合遗传算法优于两种单独的算法。     

一种基于禁忌搜索和转换瓶颈的作业车间调度算法

作业车间调度问题(Job Shop Scheduling Problem)是一种调度问题，同时也可以视为排序问题。一般说来，有不同的任务在只能使用有限资源的条件下要完成，都可以归为排序问题，比如，不同的零件要在机器上加工，几艘货船要进港，多条程序要在计算机上运行等。当然，调度不只是排序，它还根据所得到的排序确定各个任务的开始时间和结束时间。作业加工调度问题实际上就是要解决如何安     

蚂蚁算法在车间作业调度问题中的应用

蚂蚁算法是近年来新出现的一种随机型搜索寻优算法,自从在TSP等著名问题中得到富有成效的应用之后,已引起越来越多的关注和重视。论文进一步将这种新型的生物优化思想进行扩展,提出了一种解决车间作业调度问题(JSSP:JobShopSchedulingProblem)的蚂蚁优化算法,给出了求解的一般步骤和流程。通过计算实例的结果,说明了该算法优于传统算法。     

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

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

瓶颈指向的启发式算法求解混合流水车间调度问题

针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的.     

一种用于车间作业调度问题的智能枚举算法

车间作业调度问题是优化组合中一个著名的难题,即使规模不大的算例,优化算法的时间也很长。文章提出了一种求解车间作业调度问题的快速智能枚举算法,选取了22个标准算例作为算法的测试试验集,该算法在较短的时间内找到了17个算例的最优解,试验结果表明智能枚举算法确实是一种快速的、有效的求解车间作业调度问题的近似算法。     

一种求解Job_Shop调度的变量排序启发算法

该文提出了搜索空间的概率模型,并以模型中的工序开工概率、工序对机床的独立需求概率和机床累计需求三个评价因子,构造了新的变量排序启发算法。仿真结果表明新算法在较小的计算时间代价下,显著提高了系统的搜索效率。