m×n流水型排序问题关键零件法的改进

关键零件法用于解m×n流水型排序问题时存在两点不足:一是没有给出适用条件,影响了优化程度;二是没有确定优化程度,不知何时得到满意解.为了解决这些不足,改进后的关键零件法给出了近似最优解解法严格的适用条件、近似适用条件以及新的零件排序规则.改进的解法优化程度明显,非常接近最优解,而且可以判断距最优解最大的距离.

基于改进型交叉算子的混合流水车间排序求解

混合流水车间是置换流水车间的扩展,其作业排序更复杂。合理的排序方案能够提高企业设备的利用率和经济效益。在前期研究的基础上,将提出的改进型交叉算子扩展应用到混合流水车间排序问题中。介绍了求解该问题的遗传算法实现流程,剖析了改进型单点交叉算子的操作原理和特点。最后,针对企业实例进行求解,结果表明该算法寻优性能良好。

二机器流水作业排序问题全部最优解的结构(英文)

排序问题F2||Cmax,Johnson条件只是最优解的充分条件，不是必要的．本文绘出一个充分必要条件，由此得到生成全部最优解的算法．主要理论是基于一种序论方法．

带运输时间和自动机的流水作业排序问题的复杂性

研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题,同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内,存在称为运输时间的时间间隔,所有的运输工作均由自动机来完成,自动机在同一时间内最多运输一个工件,文章研究该问题及其特殊情况下的复杂性.

线路条数法在m×n流水型排序问题中运用的探讨

传统的m×n流水型排序问题近似最优解解法只是给出一个方案而已,没有考虑进一步调优,因此影响优化程度。为了解决这一问题,提出了调优线路条数法。该方法简单适用,便于掌握,优化程度高,而且在多数情况下比较容易得到最优解。

强制工期相等的双机流水车间排序问题

讨论了强制工期相等的n个工件在双机流水车间的加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会不可行排序.先讨论问题的可行性,如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后,给出一个多项式时间算法,在预排序列的基础上,通过调整最先加工的工件来获得最优排序.

一类3×n流水型排序问题新近似最优解法的探讨

3×n流水型排序问题解法较多,有些方法虽简单,但效果不佳。同时也没给出适用条件。为了解决这一问题,针对3×n流水型排序的特点,提出了新的解法及其适用条件。新解法从缩短关键线路的长度的角度出发,利用均衡原理,虽比关键加工中心法稍微复杂,但优化程度明显,更接近最优解,此外,新解法在多数情况下可以判断是否达到最优解,且比较容易得到最优解。

带服务器的3台机器流水作业排序启发式算法

研究了带服务器的流水作业排序问题的复杂性和启发式算法.每个工件在机器上加工之前,必须由服务器先进行安装,在任何时刻服务器只能在1台机器上安装工件,目标是使最大加工时间达到最小.在只有3台机器的情况下,利用3-划分到该问题的一个归约来证明该流水作业排序问题仍然是强-困难的.为此,引入一个新的启发式算法,并证明该启发式算法的紧界为2.

带运输时间和单自动机的流水作业排序

本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性,并给出新的启发式算法,证明该算法的最坏性能比是3/2,且上界是紧的。

使总完工时间达到最小的流水作业排序问题

研究带单服务器且服务时间相等的流水作业排序问题,该流水作业排序问题的目标函数是使总完工时间达到最小.利用目标和的数字匹配这个强NP-困难问题到带单服务器且服务时间相等的流水作业排序问题的归约,证明带单服务器且服务时间相等的流水作业排序问题问题也是强NP-困难的.引入加工顺序为最小加工时间优先的新启发式算法,并证明该启发式算法的上界是6/5,且该上界是紧的.

“非流水型n×m排序问题”简便方法的改进

一、问题的提出《排序问题》是运筹学中的一个问题.它可表述为:“n个不同零件需在m台设备上加工,怎样安排零件的加工顺序,使加工所耗的总工时最少?”这一问题,由于加工顺序的编排受多种因素的制约,情况异常复杂,因此,寻找最优排序方案非常困难.只有少数几种简单的情形,它才得到了完善的解决.其中主要有:1.当m=2时,即n种不同零件在两台设备上加工,且工艺顺序相同,或各零件在加工时所通过的设备顺序相同.这种问题的优化,已由Johnson于1954年提出了解决的方法.Johnson规则是:“如果各零件都需先在设备A上加工,然后转入设备B上加工,那末若加工时间短的工序是在A设备上进行的,则安排其零件先加工。

带单机器人的流水作业排序问题的复杂性

研究n个工件在2台机器上加工的流水作业排序问题,目标函数是使完工时间达到最小.当一个工件在一台机器上完工后到下一台机器上加工之前的时间间隔,称之为运输时间的时间间隔,所有运输均由单运输机来完成,机器人在同一时间只运输一个工件,证明对于这种特殊的排序问题仍然是强NP-困难的.

非流水型排序问题解法初探

一般的非流水型排序问题,目前还没有较理想的数学解法。本文提出的排序方法,可求得较优的排序方案,为合理安排作业任务,缩短生产周期,提高设备利用率,提供了较科学的依据。

带单服务器的流水作业排序问题的复杂性

研究了一个带单服务器且加工时间相等的两机流水作业排序问题,其目标函数是使总完工时间达到最小.研究表明,该流水作业排序问题是强NP-困难的.针对该流水作业排序问题构造了一种新的加工顺序,并证明该加工顺序的紧界为7/6.

基于改进遗传算法的网状流水线作业计划

在分析实际生产中流水作业种类的基础上提出了网状流水线作业计划的概念,它由两条或两条以上多阶段平行流水线构成;相邻阶段若干流水线之间存在交叉,在该交叉处前阶段加工完成的工件可向多条流水线后续设备流动;在传统遗传算法中引入多阶段编码、虚基因、自适应交叉操作等方法构成了改进遗传算法,以适应网状流水线作业计划的需要;建立了基于改进遗传算法的网状流水线作业计划方法,使各阶段网状流水线之间工件数动态平衡;用算例证明了网状流水线的优点和算法的有效性。

具有指数和位置学习效应的机器排序问题

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型。工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置。单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法。此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法。流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法。

冷卷热处理生产调度模型的启发式算法

针对某钢铁公司冷轧厂热处理车间冷卷热处理生产调度中车间大、炉区小的实际状况,建立了以热罩和冷罩为机器,冷卷为工件的一类不允许等待的混合流水车间排序模型.利用参数排序策略,实现炉区之间冷卷的重新分配;利用值排序策略,确定新的热处理顺序,使得所有冷卷最长热处理时间最短.在此基础上开发的冷卷热处理生产调度系统正在冷轧厂试运行,目前系统运行稳定、速度较快、功能较强,预计每年可创直接经济效益5 000多万元.

流水作业排序问题的启发式算法

研究了n个工件在2台机器下的流水作业排序问题,目标是使加权完工时间最小.同一工件在一台机器上完工后与在另一台机器上开工前存在一定的时间间隔,将其定义为运输时间,所有运输过程均由单自动机完成.讨论了该排序问题的复杂性,并引入了一种启发式算法,证明了该问题是强NP困难的,该算法的紧界为3/2.

一种可控的两台机流水作业排序问题

在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法.