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

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

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

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

带有退化效应的多个交货期窗口单机排序问题

讨论带有退化效应的多个交货期窗口的单机排序问题。其目标函数有2种:第1种是带有提前、延误、交货期的开始位置、交货期的大小及最大完工时间的总费用;第2种是带有提前、延误、交货期的开始位置、交货期的大小和所有工件完工时间之和的总费用。目标是找到多个交货期窗口的最优位置、交货期的大小、属于每个交货期窗口的工件集合和工件的最优排序,使目标函数值最小。将该问题转化为指派问题,并证明其多项式时间可解。     

带有交货期和加工时间可控的单机排序问题

讨论了带有交货期和工件的加工时间可控的单机排序问题.本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序.然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的.最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nlogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序.     

带有交货期窗口和加工时间可控的排序问题

讨论了带有交货期窗口和加工时间可控的单机排序问题。工件的加工时间是关于分配资源量的凸函数模型。工件若在交货期窗口前完工,则产生提前费用;若在交货期窗口后完工,则产生延误费用。分别研究了多窗口问题和单窗口问题。目标是在关于提前、延误、交货期窗口开始时间、交货期窗口大小和最大完工时间的函数约束条件下,确定工件的最优加工顺序、最优加工时间、极小化资源费用函数。通过将2个问题分别转化为指派问题,证明了2个问题是多项式时间可解的,问题的计算复杂性是O(n3)。     

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

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

交货期窗口大小给定和待定情况下的单机排序问题

研究有公共交货期窗口的单机排序问题,其目标是最小化提前和延误的赋权工件数.首先考虑交货期窗口大小给定的情况,进而讨论了当其大小待定且有线性时间惩罚的情形.分别给出最优排序的一些性质,根据这些性质提出了多项式时间的最优算法以最小化所有费用的和.     

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

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

带有维修活动和加工时间有关的单机排序

讨论带有维修活动区间且与时间有关的单机排序问题.工件的实际加工时间是关于这个工件开始加工时间的线性函数,其在加工工件的过程中需要进行维修,维修过程中及不能加工工件,且维修与时间有关.维修过后机器加工工件的速度也发生变化.目标是确定维修的位置及排序,从而使目标函数最小.     

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

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

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

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

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

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

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

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

带有退化工件和机器维修区间的单机排序问题

考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的。     

具有安装时间和共同交货期的单机排序问题

研究了在逆一致性条件下,工件同时具有与已加工工件的实际加工时间有关的安装时间和学习效应的一类排序问题,目标函数为最小化超前有奖延误受罚之和。由于1||∑nj=1(αjTj-βjEj)是NP-难的,探讨了该模型的4类多项式时间可解的特例,并对一般情形给出了一分枝定界算法。     

带有公共交货期窗口和加工时间可控的单机排序问题 (运筹学与控制论)

讨论了带有公共交货期窗口和工件的加工时间可控的单机排序问题。假设工件的加工时间是所分配资源的线性非增函数,且分配资源会产生费用。交货期窗口的开始时间是固定且不受限制的,交货期窗口的结束时间是不确定的决策变量(即交货期窗口的大小不确定)。如果工件在窗口中完工则不产生费用,否则工件提前或延误,则会产生相应的提前或延误的费用。目标函数是极小化总完工时间,提前时间,延误时间,交货期窗口的结束时间(即窗口的开始时间与窗口大小的和)和资源分配的总费用。给出了最优解的一些性质,并且证明了这个问题是多项式时间可解的。     

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

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

带有多个工期窗口及退化维护的单机排序问题

【目的】讨论带有多个工期窗口及退化维护的单机排序问题。【方法】工件的加工时间是一个和资源分配、工件在排序中的位置以及退化效应有关的凸函数。目标是确定多个最优工期窗口的位置和大小、指派给每个工期窗口的工件集合、分配给每个工件的资源、最优的维修位置和最优的工件排序,最小化提前、误工、工期窗口的开始时间、工期窗口的大小、资源分配、时间表长的总费用。【结果】证明了带有多个工期窗口及退化维护的单机排序问题仍然是多项式可解的。【结论】最优算法是可以在O(n4)时间内求出最优解。     

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

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

带有线性退化工件和退化维护时间的单机窗口排序

排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。