工件可拒绝平行机排序

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.     

两个带有分批费用的单机平行分批排序问题

假定工件和批处理机都在零时刻到达,工件被成批进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用。第1个问题对目标函数为任意的正则函数与分批费用之和的情形,利用动态规划方法给出了拟多项式时间算法;第2个问题对目标函数为误工工件数与分批费用之和的极小化问题,同样利...     

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

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

带有准备时间的可拒绝供应链排序

考虑可拒绝排序中生产与配送的集成问题.有一个制造商和多个客户,不同的客户订购不同种类的工件.机器在加工不同种类的工件前要有一个准备时间.对于客户的工件制造商可以选择接受或拒绝加工,但当工件被拒绝时制造商需要支付相应的拒绝费用.每个工件有自己的工期并且生产完成后需要配送到相应的客户处,每一批配送需要花费一定的时间和费用.该文研究了排序理论中几个主要的目标函数,给出了相应的动态规划算法并分析了算法的复杂性.     

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

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

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

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

带退化效应和不可用区间的并行批处理机问题

本文研究的是一类带有不可用区间和线性退化效应的单机无界并行批处理机排序问题。工件开始加工时间的线性递增函数看成其实际的加工时间。批工件中加工时间的最大者为这批的加工时间,同批工件同时开始加工,且批一旦开始加工就不可中断,同批中工件的完工时间都相同并为这批的完工时间。本文通过对最优解性质的分析,分别给出了求解极小化最大费用和极小化总费用的拟多项式时间算法。特别当k固定、目标函数为误工工件数时,该问题为多项式时间可解的,并用数值例子验证了算法的有效性。     

带退化效应和不可用区间的并行批处理机问题

本文研究的是一类带有不可用区间和线性退化效应的单机无界并行批处理机排序问题。工件开始加工时间的线性递增函数看成其实际的加工时间。批工件中加工时间的最大者为这批的加工时间,同批工件同时开始加工,且批一旦开始加工就不可中断,同批中工件的完工时间都相同并为这批的完工时间。本文通过对最优解性质的分析,分别给出了求解极小化最大费用和极小化总费用的拟多项式时间算法。特别当k固定、目标函数为误工工件数时,该问题为多项式时间可解的,并用数值例子验证了算法的有效性。
     

工件有工期并且可拒绝单机最小化最大提前时间的排序问题

研究工件有工期并且可拒绝的单机最小化最大提前时间的排序问题.若工件被拒绝,则需支付一定的惩罚费用;若工件被接受,则将该工件安排在机器上加工.目标函数是最小化被接收工件的最大提前完工时间与被拒绝工件的惩罚费用之和.通过对该排序问题的Pareto最优点的分析,得到该问题的多项式算法.     

带有恶化率的可拒绝单机排序及批配送

首次考虑了加工时间带有线性恶化率的可拒绝单机排序及其批配送的问题.如果工件被拒绝,则要付出一定的拒绝费用;如果工件被接受,则要安排加工并配送.目标函数是极小化接受工件的加权总完工时间或最大延误时间,配送费用与拒绝工件的拒绝费用这三部分的和,我们不仅证明了这些问题都是NP-hard的,而且还提出了基于动态规划的伪多项式时间算法.     

最优公共交货期单机提前/拖后调度和对应的批次送货

本文考虑了一个包含工件生产和工件送货的单机调度问题。目标是寻找所有工件的公共交货期和每个工件的送货时间使得工件所受到惩罚(提前／拖后惩罚,送货费用等)的值最小。完成的工件按照批次进行送货,所有在公共交货期前完工的工件在最优交货期时间一起交付,对批次送货没有量的约束。本文确定了最优公共交货期,并给出了相应的排序。     

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

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

带有维修活动和工件可拒绝的单机排序问题

讨论了带有交货期、维修活动和工件可拒绝的单机排序问题,这一问题是将所有的工件分成2个集合,分别是被接受的工件集和被拒绝的工件集。规定每个被接受的工件都有一个待定的交货期,且所有工件的交货期的大小相同。如果工件在交货期内完工,则不产生任何费用,否则工件提前或延误,会产生相应的提前或延误的费用。而对于拒绝工件而言,它的费用只与工件有关。维修活动需要在一个固定的时间长度内完成,排在维修活动之后的工件的加工时间将会减少。这类问题的总费用是2个工件集的费用之和,目标函数是确定被接受工件的最优排序,极小化接受工件和拒绝工件的总费用,该问题在多项式时间可解,在今后的应用中能发挥作用。     

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

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

数据网格中基于预测访问代价的作业调度算法

为解决数据网格中数据密集型作业的有效调度问题,提出了一种考虑等待队列中的作业潜在行为的基于访问代价的作业调度算法.分析了等待队列中的作业潜在行为的特点和作业访问代价的影响因素,给出了一个基于预测访问代价的作业调度算法.在OptorSim中的实验结果表明,该方法在作业平均处理时间和副本复制次数方面优于传统基于访问代价算法.     

交货时间区间内加权完工工件个数最大的分批排序算法

讨论了只有一台批处理机时,在交货期区间内使加权完工工件数最大的分批排序问题,给出了求解这一问题的动态规划算法.     

线性加工时间单机成组排序问题

讨论一类线性加工时间成组排序问题．在这一模型中，工件的加工时间是其开工时间的线性函数，全部工件分成若干组．工件的加工必须满足成组技术限制，同组工件间没有安装时间，各组间有与顺序无关的安装时间．目标函数为极小化最大完工时间．基于对问题的分析，给出了多项式算法。     

公共交货期窗口待定的单机成组分批排序

研究有组安装任务的单机窗时排序问题,所有工件的提前/延误惩罚费用相同;公共交货期窗口大小给定但位置待定,由线性定位费用衡量;最优排序是使所有这些费用的和最小.给出了最优排序的一些性质,提出一个多项式时间算法.     

一类加工时间与位置有关的单机排序问题

研究一类工件加工时间和位置有关的单机排序问题．在这一问题中。全部工件有一个待定的共同工期d，目标函数是提前时间，延误时间和工期的加权和达到最小，即惩罚函数最小．通过对问题的分析，将其转化为指派问题，从而证明该问题具有多项式算法．并用一个例子作了说明。     

工件可拒绝的分批配送问题研究

考虑工件可拒绝的分批配送问题:一个制造商为一个客户加工n个工件,每个工件既可以被接受加工,也可以被拒绝加工(但要支付拒绝费用),工件加工完之后要安排车辆运送给客户,完工时间为工件送达客户的时间.目标函数为被接受工件的总完工时间、总配送费用和被拒绝工件的总拒绝费用三者之和,文中对处理机为单机的情形给出了多项式时间算法,且证明了两台平行机的情形下该问题是NP-完备的,并给出了伪多项式时间算法.