带有不可用区间及拒绝的最大完工时间单机排序问题

研究带有退化效应、拒绝工件及不可用区间的单机排序问题。该问题中,工件可以被排在机器上进行加工,也可以被拒绝,但是需要支付一定的拒绝惩罚。加工工件的开始加工时间越晚,则工件的实际加工时间越大。机器带有不可用区间,在此区间内任何工件都不能被加工。目标函数为所有拒绝工件的拒绝惩罚与接受工件的最大完工时间之和。首先给出了拟多项式时间的动态规划算法,最后得到了一个全多项式近似方案。
     

带有不可用区间的单机排序问题

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。一个工件或者被拒绝加工,或者被接受。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。在张丽琦工作的基础上增加了一个不可用区间,机器在此区间内不能加工工件,并且在同一时刻至多加工一个工件。目标函数是最小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出一个动态规划算法,然后通过构造输入,将拒绝惩罚进行取整运算,再通过动态规划算法,得到拒绝惩罚取整后的一个最优排序,按照这个工件排序得到原问题的一个可行排序,最后借助一个3—因子算法得到一个全多项式时间近似方案。     

带有退化、拒绝和不可用区间的单机排序问题

【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个NP-难问题,在不可用区间前、后,工件按照基本加工时间a_j的非减顺序排列可以得到最优解,给出一个拟多项式时间动态规划算法和一个完全多项式时间近似策略。【结论】推广了已有文献的模型。     

单机带有不可用区间的松弛工期的排序问题

研究了在单机情形下具有不可用区间的松弛工期问题,不可用区间意味着在此区间不允许工件加工,且工件中断可恢复。松弛工期是工件加工时间加上1个给定的常数,这个常数为决策变量,排序的任务是给所有工件分配工期,同时确定工件的加工次序以使得目标函数值最小。目标函数值包括由于工件误工、提前及工期分配而导致的相关损失。根据不同的损失系数关系讨论了松弛工期的范围,提出动态规划算法。证明了动态规划的时间复杂性为O((P+T－pmin)nP2)。通过算例分析说明了算法的可行性。     

带有不可用区间、工件可拒绝的单机调度问题

从企业生产经常发生的一些实际问题中提炼出一类带有不可用区间、工件可拒绝的单机调度问题.目标函数是最小化加工工件的总完工时间与拒绝工件的惩罚和.对于这个已证明为NP难的问题提出一个动态规划算法最优求解小规模问题,为求解大规模问题,改进了已有最坏性能为4的启发式算法,并进一步证明了该算法的最坏性能为2+4/5+2■2k+8(k为算法的迭代次数).     

极小化最大完工时间及拒绝费用的单机可拒绝分批排序

首次考虑了工件可拒绝的单机分批排序问题,目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和.对于工件同时到达的情况,本文通过动态规划算法给出了多项式时间的精确算法,借助于数据结构中的堆排序,我们将算法复杂性降低为O(n2logB).     

带有不可用区间的批运输排序问题

在实际生产中,因机器在加工过程中发生故障或维修等原因而使机器在某一区间不可用。在同一批的工件一起运输给客户,且批的完工时间依赖于这批中最后一个工件的完工时间,即批的完工时间等于这批中最后一个工件的完工时间。文章中批交货期等于批的完工时间,因此工件的流水时间等于该工件所在批的批交货期。考虑的是n个独立的工件在单台及2台平行机的问题,并且机器带有不可用区间且是不可恢复的排序问题。运输费用依赖于批数。目标函数是极小化总流水时间及运输费用之和。对于机器在任意时间段维修的情况,分别给出了单台及2台平行机的排序问题的拟多项式的动态规划算法及相对应的时间复杂性。     

带有退化、拒绝和不可用区间的恒速机排序

考虑带有退化工件、拒绝和不可用区间的2台恒速机排序问题,其中一台机器上带有一段固定的不可用区间.该问题以实际生产环境为背景来研究机器的工件调度问题.在此模型中,每个工件的实际加工时间与它的基本加工时间、退化率和开始加工时间有关,工件的实际加工时间是其开始加工时间的线性递增函数,工件可以被拒绝,被拒绝的工件需要支付惩罚成...     

极小化加权总完工时间的可拒绝单机排序问题

在经典的排序问题中,工件的加工时间是固定不变的。然而,在实际生产中,工件的实际加工时间会发生变化。同时,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,即机器的不可用区间。研究带有到达时间、退化效应和拒绝工件,及机器带有不可用区间的单机排序问题。在这一模型中,工件的开始加工时间越晚,其实际加工时间越大,实际加工时间是与其开始加工时间有关的函数。该问题中工件允许被拒绝。如果工件被拒绝,那么需要支付拒绝惩罚。讨论的目标函数是接受工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先说明该问题是一般意义NP-难的,进而利用划分程序的方法给出了一个全多项式近似方案,最后分析了该近似方案的时间复杂性。     

机器带有不可用区间的可拒绝平行机排序问题（英文）

主要研究了机器带有拒绝和不可用区间的可拒绝排序问题.针对这一问题的两种情形进行研究.一方面,考虑了每台机器有一个不可用区间,且目标函数是极小化总完工时间与拒绝费用之和的平行机排序问题.另一方面,考虑了工件的实际加工时间是开始时间的按比例函数的平行机排序问题,并且每台机器在一段特定的区间内不可用.当然,可以通过支付拒绝惩罚费用而拒绝加工工件,这一问题的目标是极小化总加权完工时间与拒绝费用之和.对于以上两个问题,分别给出了时间复杂性为O(nm(∏mi=1Si)(P_n)~m)和O(n∏mi=1(S_i-t_0)∏mi=1T_i(A_n)~m)的伪多项式时间动态规划算法.     

带有不可用区间中断可恢复的平行机排序问题

讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间,在不可用区间内不能加工工件。工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解。首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε0为误差精度。     

带有退化效应和不可用区间的并行批排序问题

在制造业中,处理机由于长时间使用而发生故障或进行维护、保养等原因,产生一些不可用区间;并且工件的实际加工时间往往与它的开始加工时间有关。研究一种带有退化效应和不可用区间的无界单机并行批处理机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数。而并行批处理机中,同批工件同时开始加工,同时完工,且批一旦开始加工就不可中断;每批的加工时间等于这批工件中加工时间的最大者;同批中工件的完工时间都相同,为这批的完工时间。讨论的目标函数为最大完工时间问题。通过对最优解性质的分析,给出了求解此问题的多项式时间的最优算法。     

带有分段线性递减加工时间和拒绝工件的单机排序问题

讨论了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中,工件的实际加工时间是关于开始时间的分段线性递减函数,目标函数是极小化被接受工件的最大完工时间和被拒绝工件的总惩罚之和。这一问题是NP-难的。基于对问题的分析,给出了一个全多项式近似策略。全多项式近似策略的计算复杂性为O(n4 L4/ε3)。     

带有一个不可用区间的两台平行机可拒绝排序问题（英文）

本文主要研究两台平行机排序问题,其中一台机器上有一个固定的不可用区间。此外,生产商可以通过支付惩罚费用来拒绝工件。目标是极小化最大时间表长与惩罚费用之和。本文针对工件可恢复和不可恢复两种情形,分别给出了时间复杂性为O(ns_1P~2)和O(np_(max)s_1P~2)的伪多项式时间动态规划算法.     

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

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

带有维修区间与退化效应的单机排序问题

讨论带有安装时间、维修区间和退化效应的单机排序问题。在排序中,工件是成组加工的,且在组内工件加工是不可中断的。在每组间需要维修活动与安装时间,其中安装时间是之前工件实际加工时间之和的线性函数。假设维修活动使机器恢复到最初的状态,维修活动的长度是前一组工件实际加工时间的线性函数。工件的实际加工时间与工件所在的组、工件在组内的位置有关,工件在加工过程中会产生退化效应,退化率为非减函数。考虑了工件的实际加工时间与组和位置有关、只与位置有关2个问题,分别给出了2个问题的多项式算法,并给出了数值例子。目标是找到工件的最优排序与维修活动的数量、极小化最大完工时间,并证明了该问题在多项式时间内是可解的。     

带拒绝和到达时间的单机排序问题

研究了一个单机带拒绝的排序问题,目标函数是最小化接受工件的最大完工时间与所有被拒绝工件的拒绝费用之和。首先给出了此问题的混合整数规划模型,并得到了最优解的一些性质。最后给出了一个分支定界算法,并给出了数值模拟的结果。     

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

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