具有非线性恶化函数和安装时间的 单机排序问题

研究了具有非线性恶化函数的加工时间,同时工件的安装时间与已加工完工件的实际加工时间有关（即p-s-d）的单机排序问题.证明了极小化最大完工时间,极小化完工时间和是多项式时间可解的.另外极小化加权完工时间和,极小化总延误以及极小化最大延误在一定的条件下是多项式时间可解的.     

带有拒绝、恶化效应和安装时间的单机排序

研究带有安装时间、工件加工时间具有恶化效应及工件可拒绝的单机排序问题。工件的安装时间依赖于已完工工件的加工时间总和,且工件的加工时间同时受到双重恶化效应的影响。工厂可以拒绝加工工件,因而将工件分为接受与拒绝工件集,拒绝工件需要支付拒绝惩罚。目的是确定接受工件的集合、拒绝工件的集合以及接受工件集合中工件的最优排序,分别使最大完工时间、总完工时间、总完工时间的绝对差以及总等待时间的绝对差与总拒绝惩罚之和最小。将上述4个目标函数对应的问题分别转化为指派问题进行求解,给出了一个多项式时间算法,并证明了其时间复杂度。利用数值算例进行了验证,说明给出的求解算法有效。     

具有共同松弛时间的恶化型工件排序问题研究

研究工件加工时间具有恶化效应的单机松弛工期排序问题.其中恶化效应指的是工件的实际加工时间是其开工时间的递增函数且所有工件的恶化率相同,工件的松弛工期等于其实际加工时间加上共同的松弛时间.目标是确定工件的一个排序和工件工期的共同松弛时间使得工件的提前时间、延迟时间和工期的共同松弛时间的线性加权和达到最小.用运筹学方法证明了该问题可以转化为两个向量的乘积问题,从而多项式时间可解,并给出了求解的最优算法.     

工件可拒绝的在线同类机排序

针对带有惩罚费用的工件在同类平行机上的在线排序问题,目标函数为极小化被接收工件的最大完工时间加上被拒收工件的总拒绝费用,给出了一在线算法,证明了该算法的竞赛比不超过,有Z^on/Z^OPT≤1＋ρ。     

具有学习效应和非线性安装时间的单机排序问题

讨论了加工工件具有学习效应和安装时间的单机排序问题。文中工件的加工时间不是固定不变的,不仅与工件的加工位置有关,同时还与已加工完成工件的加工时间有关。安装时间分为线性安装时间和非线性安装时间,本文主要讨论的是具有非线性安装时间的情况。工件的安装时间是依赖于已加工完的工件的实际加工时间和工件所排列位置的函数形式。在文中主要证明了极小化最大完工时间,极小化完工时间总和问题是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误问题是多项式可解的。     

具有安装时间和共同交货期的单机排序问题

研究了在逆一致性条件下,工件同时具有与已加工工件的实际加工时间有关的安装时间和学习效应的一类排序问题,目标函数为最小化超前有奖延误受罚之和。由于1||∑nj=1(αjTj-βjEj)是NP-难的,探讨了该模型的4类多项式时间可解的特例,并对一般情形给出了一分枝定界算法。     

工件带安装时间平行机排序问题的列生成算法

研究了工件带与加工次序有关的安装时间的平行机排序问题，给出它的整数规划模型，并结合动态规划和分支定界方法，给出它的列生成算法．通过试验表明：算法对中等规模的问题是有效的，它可以计算到10台机器和60个工件甚至含有更多大工件的大规模问题．     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

带有安装时间以及可分批加工的供应链排序问题

研究了单制造商多客户的供应链排序问题;同一客户的工件可以分批进行加工,不同客户的工件不可以在一批中加工;当相邻的两批工件属于不同客户时则需要相应的安装时间.以生产和运输总费用最小为目标函数,建立了集成排序模型;分别用工件的加权总完工时间和最大延迟作为排序目标,采用动态规划的技巧给出了最优算法,并分析算法复杂性.     

具有通用机的四组工件排序问题

为解决实践中对多组任务的优化排序问题，文中提出了一种改进的最长工作优先安排（LPT）的算法，利用“最大相对加工时间”准则和“首先空闲”准则，讨论了将四组工件安排在四台速度相同的专用机、一台同速度的通用机上的Gmax问题，得到了利用该近似算法所得的解丁与最优解T^＊的一个估计：T/T^＊≤5/4，结果表明，采用该近似算法对工件排序，在最差情况下要比最优排序多出1/4的时间。     

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.     

单机上考虑运输的退化工件的在线排序问题

研究了单台机器上工件具有可退化效应并考虑工件运输的在线排序问题.工件按时间在线到达.这些工件先在机器上加工,完工的工件再由一台运输车辆将其运送给顾客.排序问题的目标是最小化最大运输完工时间.对于所讨论的排序模型,给出了问题的下界并给出达到下界的最好可能的在线算法.     

基于蚁群算法的无联系并行机调度问题的仿真研究

针对无联系并行机调度求解问题,引入了蚁群算法的思想.基于转移概率构建的信息素迭代模型,研究了无联系并行机调度问题的求解过程.基于Python的仿真实验结果表明:通过蚁群算法可以得到其近似解;更进一步探求了任务次序对解的影响;通过实验探索了此算法的时间性能.     

综合考虑服务水平和资源占用的平行机调度问题

【目的】对综合考虑服务水平和资源占用的平行机调度问题进行研究,建立以最小化总延误和机器使用数量之和为优化目标的优化模型。【方法】针对该问题的特点,设计了一种改进的模拟退火算法进行求解。采用不同规模的数值实验测试算法的性能,并对问题参数展开灵敏度分析。【结果】改进的模拟退火算法具有良好的求解效率和求解质量。【结论】灵敏度分析表明,增加资源储备可以使企业更好地平衡服务水平和资源占用。模型能够对企业实现资源节约型制造提供指导和决策支持。     

考虑投放期、交货期和机器准备时间的平行机问题改进遗传算法

针对考虑工件投放期、交货期和机器准备时间的平行机问题，分别以最小化最大机器完工时间和最小化工件总延期惩罚费用为优化目标，建立相应的平行机问题模型，提出一种求解该问题的改进遗传算法。该算法中采用了基于工件和机器的多参数级联编码，染色体由工件子串和机器子串连接而成；提出了机器的加工能力、加工能力指数和冗余机器集的概念及相应的初始种群生成方法；对工件子串采用部分映射交叉，而对机器子串不作交叉运算；在变异算子中，提出基于机器负荷的启发式变异算子。     

Parallel Machine Scheduling with Special Jobs

Introduction Parallel machine scheduling problems arise in many fields, including service and manufacturing systems. A parallel machine scheduling problem has a sequence of n jobs with processing times { p1 , p 2 , ... , p n } to be processed on m paralle…     

一个可控制设置成本和提前时间的易腐库存模型

讨论了设置成本和提前时间对易腐物品库存模型的影响。利用最大熵原理可得出在提前时间内的需求为正态分布，假设订货量、设置成本、提前时间是决策变量，则经过讨论给出一个算法，另外给出一个数值例子来例证本算法。     

一类安装时间和加工时间受资源约束的成组排序问题

讨论了安装时间和加工时间同时受资源约束的单机成组排序问题．目标函数为在满足最大完工时间限制条件下极小化安装时间消耗资源量与工件消耗资源量的总和．在讨论了问题若干性质基础上，给出了一个最优多项式算法，并用数值例子作了说明．     

带有交货期窗口和工件可拒绝的单机排序问题

讨论了带有交货期窗口和工件可拒绝的单机排序问题﹐这一问题是将所有的工件分成两个集合﹐一个是被接受的工件集﹐一个是被拒绝的工件集。假设被接受的每个工件都有一个待定的交货期窗口﹐且所有工件的交货期窗口的大小是相同的﹐如果工件在窗口中完工﹐则不产生任何费用;否则工件提前或延误﹐会产生相应的提前或延误的费用。而对于拒绝工件而言﹐它的费用只与工件有关。这类问题的总费用是2个工件集的费用之和。目标函数是确定被接受工件的最优排序﹐极小化总费用﹐给出了一个动态规划算法﹐并证明了这个问题是多项式时间可解的。     

平行工件在线排序问题的下界

通过分析模型Q2m|rj=0,mj,on-line-ncv|Cmax的特点,设计出了实例并证明了模型的下界为2-s/m(s+1),这一下界推广了1995年Shmoys,Wein和Williamso研究的模型Pm|rj,mj,on-line-ncv|Cmax的下界2-1/m.