带有学习与恶化效应的共同工期指派问题

【目的】研究在共同工期指派模型下,工件的实际加工时间既有学习效应(与所排位置有关)又有恶化效应(与开工时间有关)的排序问题,其中机器限定为一台。【方法】为求得最优排序,使得工件的提前、延误和工期成本的线性加权和最小,其中权重为位置权重,工件的共同工期为决策变量,此问题可转化为经典的运筹学方法求解,即求解指派问题。【结果】这个问题在位置权重、学习与恶化效应下依然是多项式时间可解的。【结论】算法分析和实例表明给出的求解算法是非常有效的。     

同时具有学习效应和恶化效应的机器可用限制性排序问题

针对单机和两台机器的平行机排序问题,建立了工件同时具有学习效应和恶化效应,机器有可用性限制的排序模型.考虑了目标函数为极小化总完工时间的单机、两台机器的同型机问题和两台机器的同类机问题.对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法.     

同时具有学习和恶化效应的单机成组排序问题

讨论了一类工件的加工时间具有学习效应且安装时间带有恶化的成组排序问题,目标函数分别为极小化最大完工时间和极小化总完工时间,1｜pij=aij-bijt,S=δit,GT｜Cmax,1｜pij=aij-bijt,S=δit,GT｜∑Cij,并分别给出了求最优解的多项式时间算法,其中极小化总完工时间问题是在bij=b,δi=δ的特殊情况下给出的。     

带有恶化效应和维修恶化的单机工期指派问题

本文研究了同时带有恶化工件和机器恶化维修的单机工期指派问题。工件的实际加工时间是与工件基本加工时间和工件在排序中的实际加工位置相关的一般函数。机器维修时间与其开始维修时间有关,是其线性恶化函数。研究的目标函数是加权提前、延误和工期之和,目的是确定工件的最优加工顺序、公共工期及维修位置,使目标函数最小。将此问题转化为指派问题,从而证明了该问题在多项式时间内是可解的。对于问题的一种特殊情况进一步给出了一个复杂性为O(n2logn)的最优算法。
     

带有恶化和拒绝的工期指派的单机排序问题

讨论带有恶化和拒绝工件的工期指派的单机排序问题。工件的实际加工时间是其开始加工时间的线性增函数。如果工件被拒绝,则有一个惩罚费用,否则工件被加工。每个工件都要确定一个工期,文章讨论的工期指派分为CON(共同工期指派)和SLK(相同松弛工期指派)两种情况。对于CON工期指派问题,其目的是确定最优公共工期及工件的加工顺序,使工期、提前、延误和拒绝的总费用最小。将该问题归结为一系列指派问题,从而得到了一个复杂性为O(n4)的算法来求解此问题。对于SLK工期指派问题,目的是确定最优的松弛量及工件的加工顺序,使松弛、提前、延误和拒绝的总费用最小。将其归结为一系列指派问题,给出了求解此问题的多项式时间的最优算法。     

具有恶化效应、资源分配、速率修正和松弛工期的排序问题

研究带有松弛工期指派的单机排序问题,工件的实际加工时间同时受到恶化效应、凸资源分配与一次机器速率修正活动的影响。为确定工件的最优排序、速率修正活动的最优位置、最优的公共容许流和最优的资源分配量,使2个约束目标函数极小化。第1个目标函数是在满足资源总量有限的条件下,极小化总惩罚费用,即提前、延误、公共容许流和时间表长的加权和;第2个目标函数是在总惩罚有限的条件下,极小化资源消耗总费用。将上述问题分别转化为指派问题。当速率修正活动位于不同的位置时,选取使得目标函数最小的解为最优解。对2个问题分别给出多项式时间算法,算法的复杂度为O(n4),其中n为工件的数量。用数值算例分别验证2个算法,说明给出的求解算法比较有效。     

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

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

退化条件下的工期指派的单机排序问题

研究退化条件下的工期指派的单机排序问题。每个工件均有一个关于工期的连续非减的惩罚函数。工件的加工时间是退化的,即工件的加工时间是其开始加工时间的一个线性增函数,所有工件都有一个相同的退化率。目标是确定工件的最优加工顺序、最优工期和最优开始加工时间,使总工期、误工工件数及总完工时间之和最小。工件在工期之后完成则称为误工工件,工件在工期之前完成则是提前工件。工期指派分两种情况,一种是所有的工件工期都相等,另一种是不同的工件有不同的工期。对于上述两种情况分别给出了最优解的3个性质,并且证明了这个问题是多项式时间可解的。     

具有工期限制的退化工件单机排序问题

工件具有退化效应的排序问题最近几年受到人们越来越多的关注。所谓具有退化效应的工件是指在排序中,工件的开工时间越晚其实际的加工时间就越长。讨论了一类具有工期限制的线性退化工件单机排序问题。其中线性退化工件指的是工件的实际加工时间是线性增长的函数。文中工件的实际加工时间不是固定不变的,是该工件的开始加工时间的单增函数。目标函数是使完工时间,提前完工时间和误工时间的加权和最小。给出了多项式时间的最优算法。     

一类具有维护和共同工期的单机排序问题

主要讨论了带有维护和共同工期的单机排序问题.工件的实际加工时间是与该工件在排序中的加工位置相关的.目标函数是共同工期相关的费用、提前完工的工件存储费用和不能在工期内完成的工件的惩罚费用之和.最后给出了多项式动态规划算法.     

在退化维修下带有工期指派和加工时间可控的单机排序问题

讨论在一次退化维修下带有3种工期指派和加工时间可控的单机排序问题。其中机器的维修时间是维修开始时间的线性非减函数,工期指派的3种模型包括共同工期指派模型、松弛工期指派模型、无限制工期指派模型,工件的实际加工时间依赖于工件的开工时间、工件的位置以及资源分配的函数。目标是要找到机器的最优维修位置和最优排序,极小化提前时间、延误时间、工期以及资源分配的总费用。当机器的维修位置固定时,证明了该问题可以转化为指派问题;当机器的维修位置不固定时,给出了一个算法,并证明了该问题可以在O(n4)时间内求得最优解;最后以共同工期指派模型为例给出一个实例。     

带有学习及退化效应和资源分配的交货期指派的单机排序问题

本文讨论带有学习及退化效应和资源分配的交货期指派的单机排序问题。所有工件有一个公共的交货期,如果工件在交货期内完工将不产生任何费用,但是在交货期之前或之后完工将产生相应的提前或延误费用。工件的实际加工时间是与开工时间、在排序中位置和资源分配有关的函数。目标是确定最优交货期的位置、交货期的大小、工件的最优排序和最优资源分配,最小化包括提前、延误、交货期大小、交货期位置和资源消耗的总费用。证明了带有学习及退化效应和资源分配的交货期指派问题仍然是多项式可解的,并且最优算法是可以在O n()3时间内求出最优解。     

带有恶化效应和维修恶化的单机工期指派问题

研究了同时带有恶化工件和机器恶化维修的单机工期指派问题。工件的实际加工时间是与工件基本加工时间和工件在排序中的实际加工位置相关的一般函数。机器维修时间与其开始维修时间有关,是其线性恶化函数。研究的目标函数是加权提前、延误和工期之和,目的是确定工件的最优加工顺序、公共工期及维修位置,使目标函数最小。将此问题转化为指派问题,从而证明了该问题在多项式时间内是可解的。对于问题的一种特殊情况进一步给出了一个复杂性为O(n2log n)的最优算法。     

具有学习与退化效应的单机排序问题

研究了具有学习效应与退化现象的单机排序问题,给出了目标函数为最大完工时间、总完工时间的多项式时间算法;并证明工件的权重与加工时间一致时加权总完工时间问题、工期与加工时间一致时最大延迟问题均有多项式时间算法.     

具有学习效应和遗忘效应的间歇批生产的单机排序问题

本文研究具有Dejong学习效应和遗忘效应的间歇批生产的单机排序问题,考虑了批与批之间没有学习效应的传递、有部分学习效应的传递和有总的学习效应传递的三种模型.对目标函数为最大完工时间的情形,指出机器在批与批之间没有学习效应的传递和有部分学习效应传递的情形下是多项式可解的,并进一步对机器在批与批之间有总的学习效应传递的两种特殊情形给出了多项式时间算法.     

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

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

一类具有学习效应的分批排序问题

本文讨论了分批排序中机器具有带学习效应,目标函数为极小化加权总完工时间的几个问题．就所有工件的加工时间都相等的这一特殊情况,给出几个算法,并证明了算法的最优性．     

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

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

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

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

具有学习效应的间歇批生产的单机排序问题

本文研究了目标函数为总完工时间,具有Dejong学习效应和遗忘效应的间歇批生产的单机排序问题.考虑了批与批之间没有学习效应的传递、有部分学习效应的传递和有总的学习效应传递3种模型.首先,在批与批之间没有学习效应传递的模型中,给出了复杂性为O(nlog n)的最优算法.其次,在批与批之间有部分学习效应传递的情形下,对批在...