工件有尺寸的单机批调度问题的在线算法

16160的在线算法,并给出了此问题的一个下界。     

工件尺寸不同的并行机批调度问题

考虑并行批加工机上不同尺寸工件的调度问题;目标是极小化最大完工时间.给出了一个(2+ε)-近似算法,ε＞0可以任意小.     

具有前瞻区间和不相容工件族的流水车间在线排序问题

研究对多台单位流水车间上具有前瞻区间的不相容工件族无界批处理的在线排序问题。通过组合优化的方法分类讨论得到问题的下界，对算法Am（β）进行了竞争比分析说明这是该问题最好可能的在线算法。给出了该问题的下界为1+η，其中η是方程(2f－1)η2+(f+β)η+β－f=0的一个正根，这里0≤β<1。同时提供了一个最好可能的在线算法Am（β）。通过竞争比分析说明了算法的可行性。     

轧辊热处理过程中具有组批的并行机调度问题

研究了在轧辊热处理过程中加热炉体积相同的情况下,具有组批的并行机调度问题.以使最长完成时间最小化为目标建立了该问题的数学模型.提出了辊坯组批启发式算法和批次调度启发式算法,并将二者结合形成了一个两阶段启发式算法,对模型进行求解.通过对实验结果的比较与分析,验证了方法的有效性.针对不同规模的问题给出了相应的最优求解方法,提高了轧辊的生产效率,为决策者合理安排生产提供了有效的策略.     

最小化时间表长的带有多个工件组单机无界继列批在线排序

考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序间题.每个工件具有各自的安装时间和加工时间(s,p),属于不同组的工件不能在同一批中加工,目标函数是最小化最大完工时间,给出了此问题的一个竞争比为2的最好可能的在线算法.     

预先知道工件最大加工时间的带机器费用的排序

对大多数排序问题来说，机器集往往是事先给定的，而且在算法进行过程中，机器集是不变的。Imreh和Noga第一次提出了在排序中考虑机器费用的模型。他们研究了所谓的List Model problem，并给出了竞争比为（1＋5的平方根）／2≈1．618的在线算法，同时证明了该模型的任意在线算法的竞争比至少是4／3。本文研究List Model problem的一个半在线情形，我们假设工件的最大加工时间预先知道，我们将给出一个竞争比为19／12≈1．583的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是4／3。这表明部分信息有利于设计更好的算法。     

最小化时间表长和最大加工运输时间的单机继列批在线排序

研究了目标函数为时间表长和最大加工运输时间的单机继列批在线排序问题.对于时间表长问题,给出了当批容量无界时竞争比是5～(1/2)+1/2的最好可能的在线算法和当批容量有限时竞争比不超过2的在线算法;对于最大加工运输时间问题,证明了当批容量无界时的竞争比不超过2.     

最大化接收工件总权值的批处理机在线排序

研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p0,一个到达时间r_j≥0,一个权值w_j0,一个必须交货期d_j0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m~2-m)~(1/2)/(2m~2-m).     

基于人工蜂群算法求解不同尺寸工件单机批调度问题

采用人工蜂群算法对工件尺寸有差异的单机批调度问题的制造跨度进行优化的提出,是针对问题的离散优化特征,采用遗传算法中的变异操作方法产生蜂群路径的邻域解. 在解码时采用Batch First Fit算法,将蜂群的路径转化为可行的批调度方案,来获得制造跨度. 仿真实验中对问题的各种不同复杂度的随机算例均进行了编程实现,结果表明人工蜂群算法在求解该问题时是有效的.     

工件分簇的半连续型批处理机调度问题

半连续型批处理机调度问题是从钢铁工业加热炉对管坯的加热过程中提炼出来的,其中把加热炉看作批处理机,同一时刻可以有C个工件被加工。工件以批方式进行加工,批中工件的进入、加工和离开都是按周期进行,同一批中的工件都有自己的开始加工时间和完工时间,且加工时间均等于这批工件中加工时间的最大者,批的大小为这批工件的个数。半连续型批处理机调度问题包含如何分批及安排各批间的加工顺序。考虑了单机且工件分簇的情况,其中在同一簇中工件的加工时间相同。目标函数为极小化总完工时间。对于工件的簇数是F的情况,通过最优解的性质给出了一个复杂性为O（F^2）的动态规划算法,能够获得对应问题的最优解。     

工件有尺寸的同型机分批排序问题

首次研究了工件有尺寸的同型机分批排序问题,用3元素法将其表示为,pm│B,sj│Cmax,并对这一问题给出了一个近似比为5/2-1/m的离线算法.     

链组约束下部分批处理平行机在线排序

研究了一台是批处理机而另一台是正常机器、工件具有链组约束、最小化时间表长的两台恒同机在线排序问题.给出该问题竞争比为(5+1)/2的最好可能的在线算法.     

带机器准备时间的两台机器半在线排序

研究了两台机器的两个半在线排序问题.当机器为有准备时间的同类机时,总加工时间已知;当机器为有准备时间同型机时,最大加工时间已知.对这两个问题,给出了各自的半在线算法,证明了他们的竞争比分别至少为b 1/2b 1和2/3,其中b,为机器速度,b1=1,1＜b2=b.     

基于缓冲区的同型机物资调度优化

现代物流运输车辆调度方法复杂多变。将缓冲区引入物流调度中,解决物资冗余的问题;分析了带缓冲区的两台同型机半在线调度优化问题,目标为最大化最小机器加工时间,给出了一个竞争比至少为2/3的半在线算法。     

局内车辆选线问题的比较策略及其竞争比分析

对现实物流配送中遇到的无法预测的线路堵塞问题,建立了具有堵塞点的局内车辆选线问题的数学模型,并分别介绍了局内运输车辆调度的贪婪策略和复位策略．在全面分析了这2种基本策略在竞争性能上的优劣之后,给出了比较策略及其算法模型．最后,讨论了该策略的竞争性能．结果表明,比较策略实现了对局内运输车辆的优化调度．     

具有维修时间的两台平行机在线排序

在排序问题中,机器可能出现故障或其他原因而需要维修,因此,在加工工件时把维修时间考虑进去是很必要的.对机器维修时间完全重合、可中断的两台平行机排序问题,本文考虑它的在线情形.通过分析不同情形,给出其任意在线算法竞争比的下界为2,并给出一个最好可能的在线算法.     

两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题

研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法—层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.     

用时序在线建模法进行加工尺寸的预报控制

本文基于AR模型参数的Livenson-Durbin算法提出了一种AR模型的在线建模算法,与已有的递推最小二乘法相比,具有相同的精度,而计算量要少得多.通过对精镗孔加工尺寸预报控制的模拟计算表明,应用本文提出的在线建模方法进行加工尺寸的预报控制是完全可行的.