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

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

具有学习效应且加工时间可控的单机排序问题

讨论一类加工时间可控的单机排序问题.在这一问题的模型中,机器具有学习效应,工件的实际加工时间为同时依赖于所排位置和所分配的资源量的资源消耗函数,其中资源消耗函数又分为线性资源消耗函数和凸资源消耗函数这两种函数.考虑共同工期分派方法和松弛工期分派方法这两种工期分派方法.极小化一个包含加权总误工数的费用、工期分派的费用、最大完工时间的费用和总资源消耗的费用的目标函数.对于工件加工时间的两种资源消耗函数与工期分派方法的不同组合,算法复杂性为O（n4）的多项式时间算法相应地被给出.创新之处是：在Shabtay研究的基础上增加考虑了学习效应后,计算相关问题的算法复杂性仍保持不变.     

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

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

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

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

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

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

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

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

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

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

一类带有可控加工时间的单机排序问题 (运筹学与控制论)

讨论了具有学习效应的工期指派和可控加工时间的单机排序问题。工件的实际加工时间同时依赖于所排位置和所分配的资源消耗相关的函数,资源消耗分为线性和凸资源消耗2种。考虑共同工期、松弛工期和没有限制的工期3种工期分派方法。目标是确定工件最优的加工顺序、工期和资源分配量,极小化一个包含提前、延误、工期分派、总完工时间和总资源消耗的总费用函数。对于上述2种不同资源消耗函数与3种不同的工期分派方法的每一种组合,均给出了多项式时间算法。     

固定区间下的可中断单机双代理总加权误工问题

【目的】研究在固定区间内工件可中断的单机双代理排序问题。【方法】每个代理都有各自对应的工件集合以及目标函数，它们只能共同使用1台机器来完成各自工件的加工，每个代理的目标都是最小化各自的目标函数。第一个代理工件可中断且到达时间与工期满足一致性关系，目标函数为总加权误工费用；第二个代理中工件位于固定时间窗口内进行加工。【结果】排序的目的是为了第二个代理中工件满足加工时间区间等于固定区间条件下，使得第一个代理的目标函数达到最小化。【结论】利用了分块的原则，给出了最优性质刻画和复杂性分析，以及设计了一个伪多项式时间动态规划算法。     

工时依赖位置的宽容期单机排序问题

研究了共同宽容交货期的单机排序问题,即加工时间是位置的函数,所有工件的提前/延误费用相同,共同宽容交货期的开始时间和大小待定,目标函数最小化的总惩罚费用(包括提前、延误、宽容交货期的定位和大小费用四部分).并给出了最优排序的性质,提出了一个多项式时间算法.     

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

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

离散加工时间单机多准则下可控排序问题

讨论了工件具有离散可控加工时间的单机多准则下的排序问题. 目标函数分别为极小化完工时间和与完工时间偏差和的线性组合, 极小化等待时间和与等待时间偏差和的线性组合, 极小化提前时间、延误时间、最早交货期及窗口长度的加权和, 极小化提前时间、延误时间及公共工期的加权和. 用数学规划的方法证明了四类多准则下的单机排序问题可以转化为指派问题,从而这四类问题都多项式时间可解.     

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

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

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

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

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

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

多共同工期分配调度问题算法研究

为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该问题可解。该问题是多项式可解的,并给出了具体求解算法。     

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

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

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

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

退化工件误工数的双机自由作业排序问题

探讨退化工件两台机器自由作业环境下的最小化加权误工工件的排序问题,其中所有工件具有相同的公共交货期。首先证明了最小化误工工件数问题是 NP 困难的;然后对最小化加权误工工件数问题给出了一个拟多项式时间算法;最后对几种特殊情形给出了多项式时间算法。