三机流水作业问题若干特殊情形的NP困难性

本文研究以加工总为目标函数的三台机器流水作业问题的特殊情形的计算复杂性,证明了下列情形为ＮＰ困难的：所有工作在第二台机器上有相同的加工时间;所有工作在第一和第三台机器上有相册的加工时间;每个工件至少有一个零工序;每个工件有一个丢失的工序。     

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器(分别称为机器M_1和M_2)上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择:模式1是将两个任务都安排在机器M_2上加工;模式2是将任务A和B分别安排在机器M_1和M_2上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.     

具有退化工件和工期窗口安排的排序问题

针对具有退化工件的排序模型,考虑了单机排序和两台机器流水作业的工期窗口安排问题,在这一模型中,工件的加工时间是与其开工时间和退化率有关的一个线性函数。目标是找到一个最优排序和确定工期窗口的开始时间及大小以便最小化所有工件的费用函数,费用函数由四部分组成:提前、延误、工期窗口开始时间和工期窗口大小。对所研究的单机问题,详细地讨论了符合现实情况的几种类型问题,并得到了问题的最优解;对两台机器流水作业问题,给出了多项式算法。     

带转包选项的自由作业排序

本文研究两机自由作业排序问题,工件的两个工序既可以在制造商的两台自由作业环境机器上加工,也可以转包给两承包商加工.每承包商有一台单机,仅能加工指定的工序.工件被转包时制造商需要付出一定数量的转包费用.制造商需要同时确定转包工件集及未转包工件的加工顺序,目标是极小化转包费用与未转包工件时间表加工总长之和.本文根据转包费用系数的不同,分析问题     

基于退化效应的两台机器流水作业可拒绝排序

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.     

车床管理优化模型

本文讨论了自动化车床连续加工零件工序定期检查和刀具更换的最优策略 .针对问题一 ,应用管理成本理论结合概率统计方法 ,建立定期检查调节零件的平均管理成本的优化设计模型 ,通过计算机求解、模拟 ,得到工序设计效益最好的检查间隔和刀具更换间隔 .针对问题二 ,在问题一的基础上 ,利用概率知识调整了检查间隔中的不合格品数带来的平均损失 ,同时加上了因工序正常而误认为有故障停机产生的平均损失 ,然后建立起目标函数 ,得到工序设计效益最好的检查间隔和刀具更换策略 .对于工序故障采用自动检查装置 ,设计出了自动检查调节系统 ,并给出了算法框图 ,有效地避免工序正常而误认为有故障停机损失 ,提高工序效益     

机器具有优势关系下的工件加工时间可控的流水作业排序问题

本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.     

同型机和两台批处理机组成三阶段流水作业的最小加工全程问题

讨论一类三阶段流水作业的问题,第一阶段由m台同型机组成,第二阶段和第三阶段分别为1台批处理机,目标函数为最小加工全程.在同型机和两台批处理机上工件的加工时间分别相同情况下,给出了一般情况和几类特殊情况的算法.     

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器（分别称为机器M₁和M₂）上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择：模式1是将两个任务都安排在机器M₂上加工;模式2是将任务A和B分别安排在机器M₁和M₂上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.     

费用有限的柔性两机自由作业与流水作业排序问题

研究制造商加工环境为两机自由作业和流水作业柔性排序问题,即工件既可以在制造商两台机器上加工,又可以转包给承包商机器加工.承包商有足够多机器,使得每台机器至多加工一个工件.工件在制造商及承包商机器上所需加工时间及费用均不同.本文需要确定被转包的工件集及未转包工件的加工顺序,在加工及转包总费用不超过给定值的情况下,分别极小...     

含有批处理机的三机流水作业加工总长问题的计算复杂性

研究含有批处理机的三台机器流水作业加工总长问题的计算复杂性.不仅考虑了批处理机容量有限的情形,还考虑了批处理机容量无限的情形.证明了当第二台机器是批处理机、其余两台机器是单机时,该问题是NP困难的.至此,含有批处理机的三台机器流水作业加工总长问题在所有情形下的计算复杂性得到了解决.     

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

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

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

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

活动长度有限制的多工序批量加工生产计划研究

当前的化工制造中,有很多工厂使用柔性制造设备,并采用批生产模式来组织生产.由于对设备进行准备和清理的成本比较大,加工的排序一般采用多批次加工同一种产品的活动（campaign）模式.在实际的生产中,由于需要保证产品质量和减少库存,应该考虑限制活动的最大长度.本文针对活动长度有限制的多工序批量加工问题进行研究,利用状态-任务-网络概念和层级模型方法,提出了修正的活动计划模型.该模型是基于混合整数线性规划模型,并且以供应网络内总生产成本和物流成本最小化作为目标函数.最后用一个算例来说明所构建模型的有效性.     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$,其中$m$是机器数目。     

应用几何平均法分析工作质量指标

企业中每个工作岗位的工作质量都直接或间接地影响着产品质量.正确分析评价生产者的工作量,奖罚分明,是提高产品质量,提高经济效益的基础和保证. 我厂生产车间的工作质量直接表现为工序质量,工序质量是指工序成果符合设计、工艺技术标准的要求. 我厂生产的插芯门锁由70多只零件组、成.我厂过去用进仓零件合格率指标反映车间工作质量.厂部以全厂统一的进仓零件合格率指标考核各加工车间(厂部核定合格率指标为97%).厂部规定进仓零件合格率指标变动1%奖金系数浮动10%.由于组成锁体的每只零件工序道数不同.有的零件经过一、二道工序就能进入成品…     

自动化车床最优刀具检测更换模型

本文通过对自动化车床 1 0 0次刀具故障的记录进行数理统计分析 ,研究了自动化车床连续加工单一零件时刀具的检测及更换模型 .首先利用概率大样本场合的 D检验方法证明了刀具的故障发生规律服从正态分布 [1] ,继而求出系统工序的寿命分布函数 [2 ] ,列出以合格零件单位期望损失为目标 ,关于检测间隔和刀具定期更换间隔为变量的多目标函数方程 ,最后利用计算机进行列举比较求解 ,从而得出取得最大经济效益的系统工序的最优检测间隔以及最优刀具更换策略 .由于刀具的故障发生服从正态分布 ,我们对模型进行了改进 ,采取有规律的不等间隔的检查方式 ,结果取得了相对于等检查间隔的更优解 .本文利用算法较好地解决了问题 ,得到了问题的优化解 .对于问题 1 ,解得换刀间隔和检查间隔分别为369和 1 8,单位合格零件损失 4 .61 5元 ,采用不等间隔的损失为 4 .4 0 5元 ;对于问题 2 ,由于情况复杂 ,解得换刀间隔和检查间隔分别为 30 6和 2 8,单位合格零件损失 9.2 68元 ,采用不等间隔的损失为 9.0 4 7元 ,从而验证了本文提出的不等间隔检查方式的更优性     

考虑运输时间的MapReduce模型下的同类机调度研究

MapReduce模型在大数据处理及机器调度方面日趋重要.针对MapReduce模型中的每个工件由Map和Reduce两道加工工序组成,其中Map工序允许分割成若干个子任务,并在多台同类机上并行加工,而Reduce工序只能在该工件的Map工序里的子任务全部加工完后才能启动加工,且Reduce工序不能分割,即只能在一台机器上连续加工.在实际生产中,重型工件的两个相邻工序若分配给不同机器,则工件在机器之间需要一定的运输时间.结合工件的到达时间约束,以最小化最大完工时间为目标,构建了混合整数规划模型,设计了采用单纯形差分变异策略的改进磷虾算法来求解模型.利用数值仿真实验,与基本磷虾算法、遗传算法及CPLEX计算结果进行对比.测试结果说明了所提出的改进磷虾算法在解的质量和运行时间方面均优于基本磷虾算法、遗传算法,验证了模型与算法改进的有效性.     

以延误时间为指标的一台设备上的排序问题

在工业生产中常常会碰到这样的问题:有若干种产品要在某台设备上加工,每种产品都有预定的交货日期,并且这台设备不能同时加工两种产品.由于活多时间紧,某些产品免不了要延误交货日期.如何安排这些产品的加工顺序,使各产品延误交货日期的总时间最少?这是属于以延误时间为指标的一台设备上的加工顺序问题.对于这类问题,目前尚未完全解决.本文提出一种近似解法,似比国外流行的一些解法要好些.现叙述如下:     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。