在退化维修活动下具有多窗口及退化效应的单机排序问题

【目的】对多窗口和具有退化效应与退化维护活动的单机排序问题进行求解。【方法】假设任务的实际加工时间是关于该任务加工位置的函数,一个窗口不能包含另一个窗口。由于机器存在退化效应,适时地对机器进行维护能提高机器的生产效率。一旦维护活动结束,机器恢复到最初状态,并且任务的退化效应更新,机器维护活动持续的时间取决于维护活动的开始时间。将所有任务分成若干个任务集,任务集个数已知,每一个任务集共用一个窗口。目标是得到每个任务集最优窗口的位置、大小和最优维护活动的位置及任务的最优加工顺序使得任务的提前惩罚费用、延误惩罚费用、窗口开始时间及宽度费用之和最小。【结果】证明了此问题可以通过转化为指派问题求得最优解。【结论】并给出一个多项式时间算法来解该问题。
     

带有维修活动和交货期窗口的单机排序问题

【目的】带有维修活动和交货期窗口的单机排序问题在现实生活中有着广泛的应用。每个工件都有属于自己的交货期窗口,工件在交货期窗口外完工,就会产生相应的提前、延误惩罚。因此,确定交货期窗口位置具有重要意义。【方法】考虑了 2 种维修活动:依赖于时间、资源的维修活动;依赖于位置、资源的维修活动。针对不同的维修位置,将问题转化为指派问题。【结果】给出了计算复杂性是 O ( n4 )的多项式时间算法。【结论】证明了该问题是多项式时间可解的。
     

带有学习效应和退化效应的加工时间与资源有关的单机排序问题

研究了同时带有学习效应和退化效应的加工时间与资源有关的多窗口单机排序问题。工件实际的加工时间是关于分配资源量的凸函数,并且是关于开始加工时间的线性递增函数。每个工件都有一个交货期的窗口。若工件在此窗口中完工,则不会产生惩罚费用;否则工件在此窗口之前或之后完工,则会产生相应的提前或延误费用。目标是确定工件最优的加工顺序和最优的资源分配量,从而极小化总费用函数。考虑两个问题,第一个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小、资源分配量以及最大完工时间有关的函数;第二个问题的目标函数是关于提前、延误、窗口的开始时间、窗口的大小、资源分配量以及最大完工时间的函数。针对这两个问题也分别给出了两个多项式时间算法。
     

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

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

具有一般截断因子和资源约束的单机工期窗口排序问题

【目的】研究具有一般的与任务有关的截断学习效应的凸资源单机窗口排序问题。【方法】任务的实际加工时间是所获得的资源量、与任务有关的学习效应以及控制参数的函数。在资源总量有限的条件下确定最优资源分配方案、最优公共工期窗口的位置及大小、最优的任务排序,使得由工件的提前惩罚、延误惩罚、窗口的开始时间和宽度、时间表长等构成的总费用最小。【结果】在上述总费用具有上界的前提下,求出最优决策变量使得资源总费用最小。【结论】分别给出了求解相应问题的多项式时间最优算法。
     

重加工具有退化与学习现象的单机批排序问题

本文对同一台机器下次品工件可重加工生产的问题进行研究。工件要求成批加工,每批包括连续加工的两个子批。第一子批的工件加工后,一部分工件是按照要求得到的优良品,另一部分工件是次品。次品的工件接着在第二子批重加工,而次品工件在等待重加工时会产生退化与学习现象,加工完成后得到的工件是优良品。同一子批的工件同时完工,工件的完工时间是该子批中最后一个工件的完工时间。假设每批生产的工件次品率是相同的。每一批工件开始加工和重加工时都有安装时间。目标函数是使总安装时间,重加工和库存持续费用最小,并且优良品工件的需求得到满足。对于该问题的一般情形给出了动态规划算法。接着当批工件的完工时间和批的规模满足一致关系,给出多项时间算法。
     

带有机器维修和多个工期的单机排序问题

针对具有恶化工件和机器维修的单机排序模型,讨论了多个工期的指派问题。在这一模型中,机器在加工过程中产生恶化使效率降低,工件的实际加工时间是关于开始加工时间的线性递增函数;机器的维修区间是关于开始维修时间的线性递增函数,维修工作完成后,机器将恢复到初始状态,工件的恶化也重新开始。目标是确定最优排序、最优工期和最优维修位置以便极小化工件的提前、延误和工期的总费用。对于这一问题,给出了最优解的一些相关性质,证明了这个问题是多项式时间可解的。     

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

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

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

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

带有线性位置恶化及维修区间的单机排序问题

讨论带有线性位置恶化及维修区间与加工时间有关的单机排序问题。工件的实际加工时间与其所在的位置线性相关,维修区间长度与其前一组工件的完工时间线性相关。每次维修后都将机器恢复到最原始状态。目标函数为最大完工时间和总完工时间的和。证明在最大完工时间情形下工件满足组平衡原则。对于总完工时间问题,可以转化为线性指派问题。最后分别给出这两个问题的多项式时间算法。
     

退化条件下具有维修活动的单机排序问题

在现实的环境中,工件的加工时间可能与其在机器上的开工时间有关,工件的开工时间越晚其加工时间越长,这种现象称为“退化效应”(Deteriorateing effect).针对机器具有退化效应和维修活动(Rate-modifying activity,RMA)的单机排序模型,考虑一个序列无关的,在简单线性退化条件下工件的加...     

带有交货期窗口和工件可拒绝的单机排序问题(运筹学与控制论)

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

运筹学与控制论两台平行机环境下加工时间退化的可拒绝排序问题

研究两台平行机环境下加工时间线性退化的可拒绝排序问题,工件的实际加工时间是关于该工件开始加工时间的线性函数,每个工件都有一个独立的截止工期,在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚。工件允许被拒绝,如果工件被拒绝则需要支付一定的拒绝费用。目标是分别确定接受工件和拒绝工件的任务集合,找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和。证明了此 NP 难问题可以通过动态规划方法求得最优解,并通过动态规划运用简化执行空间的方法给出了复杂度为o(n5D2/ε2)的全多项式近似策略（FPTAS）,其中 n 表示工件的数量,ε 是允许误差界。