具有到达时间和禁用区间的单机平行批排序

研究工件带有到达时间且机器带有可用性限制(禁用区间)的单机平行批排序问题.假设机器在一些不交的时间区间上不可用.工件以平行批的形式在机器可用的时间区间上加工,并且不可中断.一个批的加工时间是这一批中加工时间最长的工件的加工时间.对任意的正则目标函数,当工件带有到达时间且机器带有可用性限制时,给出了单机平行批排序问题的一个拟多项式时间算法.     

到达时间与工期同序的串行批处理机排序问题

笔者考虑的工件带有到达时间,且到达时间与工期同序、目标函数为加权误工工件数的单台串行批处理机排序问题是NP-难的,其中批处理机的容量无限。当同一批中的工件都到达后,此批才可以开始加工。同一批中工件的开始加工时间相同,批的加工时间为此批中所有工件的加工时间之和,且完工时间也相同,为这批中最后一个工件的完工时间;每批开始加工之前都有一个固定的调整时间,而批内工件间无调整时间,在批的调整时间内机器不能加工任何工件。研究工件带有2个不同到达时间,且到达时间与工期同序的情况。对于目标函数为加权误工工件数问题,分析了其最优解的性质,给出了拟多项式动态规划算法及其时间复杂性。     

带到达时间、不可用区间、拒绝工件的单机排序问题 (三峡地区资源环境生态研究)

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件。本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出了一个近似算法,并通过引理1证明出此算法是3-因子算法;其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O(n2/ε)     

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

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

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

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

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

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

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

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

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

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

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

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

带有安装时间和学习效应的供应链排序问题

考虑了机器带有安装时间和具有学习效应的单机供应链排序问题.在一条供应链系统中,有单个制造商和多个客户,不同的客户订购不同种类的工件,机器加工不同种类的工件前需要一个安装时间,且加工相同客户的工件时具有学习效应,即随着工件的加工后面工件的实际加工时间逐渐减小.完工的工件需要成批运输给相应的客户,每一批运输都有相应的时间和费用.目标是分别极小化加权最大配送时间、总配送时间、最大延迟时间与总运输费用的和.给出了相应的算法,并分析了算法的复杂性.     

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

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

二机流水作业带不可用区间、工件可拒绝的调度问题

考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3.     

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

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

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

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

恶化工件具有p-s-d安装时间的非同类机排序

主要讨论了恶化工件具有p-s-d安装时间的非同类机排序问题.工件的实际加工时间与开工时间有关,安装时间是依赖于所在机器上已加工完的工件的加工时间的简单函数,即p-s-d形式.本文所考虑的问题是如何确定工件在非同类机上的加工顺序使得所有工件的总完工时间最小.在每台机器上加工的工件数确定的情况下,将该排序问题转化为一个指派...     

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

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

单台机器有使用限制的排序问题

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.     

带有机器维修和工件派送的单机排序问题

研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型.不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的车辆批次交付给顾客,车辆派送完一批后需要返回派送中心交付下一个批次,工件派送到不同客户处所需的时间不同.目标函数是最小化最大完工时间.本文主要研...     

最小化时间表长的带有多个工件组单机无界继列批在线排序

考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序间题.每个工件具有各自的安装时间和加工时间(s,p),属于不同组的工件不能在同一批中加工,目标函数是最小化最大完工时间,给出了此问题的一个竞争比为2的最好可能的在线算法.     

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

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