具有错位限制且工件可退化的单机重新排序问题

重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法.     

关于机器随机故障完工时间方差最小化单机调度问题

讨论了机器随机故障时,工件完工时间方差的期望最小化单机调度问题,其中描述机器故障的计数过程为广义泊松过程.推导出了目标函数等价的确定形式,而后进一步给出了工件加工时间相同时问题的最优解.     

一个单台机器排序问题的下界

本文考虑下述n个工件在一台机器上加工的排序问题。其中d_i,C_i,w_i和h_i分别为工件i的应交工时间、完工时间、延误权因子和成本权因子。工件i所需的加工时间为p_i,所有工件在时间t=0时同时到达机器旁,机器不允许空转,工件被加工时不允许中断。本文用一O(n)快速方法给出(P)的一个下界。对问题(P),当取O≤u_i≤w_i,i=1,2,…,n时,     

对球面工件的一种新测量方法的最优设计研究

崔文泉、李娟．对球面工件的一种新测量方法的最优设计研究．本文针对一种新的适用于车间在线测量的球面工件测量方法———气动方式的多测头、多测点的方法进行了布点最优设计的研究，给出了布点设计的最优性条件、使被测球半径达到最大精度的设计等，最后给出了设计示例     

带运输机的流水车间调度的最优算法

研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.     

具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

订单带多工类工件时的极小迟后范围问题

本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．     

工件具有子工件工期的排序问题

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较.     

平行机上带有前瞻区间的不相容工件组在线排序问题

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.     

工件具有加工位置上限最小化加权总误工量的单机排序问题（英文）

考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件J_j都具有一个加工位置上限k_j.也就是说,如果工件J_j是一个可行排序中的第x个工件,那么就需要满足x≤k_j.证明了(ⅰ)当工件具有相同工期时,该排序问题是二元NP-难的并且是拟多项式时间可解的,(ⅱ)当工件具有单位权重时,该排序问题是一元NP-难的.     

具有学习效应的排序对策

建立了具有学习效应的排序对策模型,在这类排序对策中,工件的实际加工时间不再是常数,而是关于工件位置的递减幂函数。当所有工件的正常加工时间相等时,松弛可行顺序的条件,相应的排序对策是均衡的,但不一定是凸对策。     

相容工件系统的最小化最大延迟与误工和的重新排序

在单机重新排序问题中,一个原始工件集已经排好顺序,使得给定的目标函数最小．当一个新的工件集到来时就会产生一些错位,决策者需要插入新工件到原来排序中而还不能过分打乱它们的顺序．该论文首先研究了当工件加工时间和工期相容时,在错位量限制的条件下最小化最大延迟问题;也研究了当工件加工时间相同或工件工期相同时,在错位量限制的条件下最小化误工和问题．对这些问题,给出了好的算法．     

具有老化效应的单机共同工期安排和工件可拒绝排序问题

研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。     

磨床几何误差对外圆端面磨削精度的影响

本文分析了外圆端面磨削时砂轮与工件的瞬时接触线;进而导出了外圆端面磨削的工件轴向截形方程;最后计算了工件轴线与砂轮轴线不平行偏差对工件端面平面度影响的两种特例.     

钛合金插铣过程温度场的数学建模与有限元分析

从金属切削理论出发分析了钛合金插铣过程的切削热产生机理,推导出工件的热传导方程式,并在此基础上建立钛合金插铣的数学模型,应用Galerkin有限元方法对工件的热传导方程进行推导计算,随后利用Matlab进行数值模拟,最终得到工件稳定后温度分布图.通过数值计算结果与实验结果对比,验证了有限元模型具有可靠和高精度优点.对钛合金插铣过程加工参数的优化和刀具的设计提供了重要参考依据.     

一种新的学习效应的机器排序问题研究

近年来有关学习效应的排序模型越来越受到关注. 由于机器操作的逐渐熟练,对于工件加工位置有关的学习模型具有更现实的意义. 考虑到工人在加工工件的过程中经验的增加, 与已经加工过的工件之和有关的学习模型也具有一定的现实意义. 本文研究工件加工位置和已经加工过的工件加工时间之和有关的学习模型,对于单机, 流水作业排序的情形作了一些分析,并给出了多项式时间算法.     

多重抽样方案的概率计算

<正> 在产品验收中,采用多重抽样方案时平均检验的产品件数较少,所需经费、人力、时间也相应的少。但是在抽样过程中概率的计算难度较大,不易被操作者掌握,因此未得到广泛的应用,本文介绍一种多重抽样方案概率计算的简便方法。     

同类机下的供应链排序及转包策略

研究了一类工件排序与转包关联的模型,即工件既可以在制造商的同类机上加工,也可以较高费用转包给某个承包商加工.需要确定被转包的工件集,以及未转包工件的加工顺序,使得工件加工与转包费用在工件最大完工时间满足限制条件下达到极小.证明了该问题的NP困难性,用数学规划方法构造多项式时间近似算法,并分析算法性能比.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．