带有学习效应和退化效应的加工时间与资源有关的单机排序问题

研究了同时带有学习效应和退化效应的加工时间与资源有关的多窗口单机排序问题。工件实际的加工时间是关于分配资源量的凸函数,并且是关于开始加工时间的线性递增函数。每个工件都有一个交货期的窗口。若工件在此窗口中完工,则不会产生惩罚费用;否则工件在此窗口之前或之后完工,则会产生相应的提前或延误费用。目标是确定工件最优的加工顺序和最优的资源分配量,从而极小化总费用函数。考虑两个问题,第一个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小、资源分配量以及最大完工时间有关的函数;第二个问题的目标函数是关于提前、延误、窗口的开始时间、窗口的大小、资源分配量以及最大完工时间的函数。针对这两个问题也分别给出了两个多项式时间算法。
     

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

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

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

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

具有截断控制参数学习效应的单机排序问题

讨论具有截断控制参数学习效应和退化效应且工件的加工时间依赖于资源分配的单机排序问题。分别在线性资源和凸资源消费函数条件下研究问题。每个任务有一个松弛工期窗口,任务的实际加工时间依赖于截断控制参数、工件的开始加工时间和分配方案的资源数量。目标是求出任务的最优排序、每个任务的工期窗口位置、最优资源分配,使由任务总提前、延误、工期窗口的开始时间、窗口大小、时间表长、总完工时间及资源总费用的加权和最小。将问题转化为指派问题,证明了该问题是在多项式时间内可解的,并分别给出了2个多项式时间的最优算法。     

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

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

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

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

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。     

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

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

加工时间可控的单机排序问题

研究带有学习效应和恶化效应的单机排序问题。在此模型中,工件的学习效应是与工件加工位置相关的减函数,工件的恶化效应是与其开始加工时间相关的线性函数。在无资源约束的情况下,分别讨论了目标函数为最大完工时间、总完工时间及总完工时间的绝对差之和的排序问题,证明了这些问题都是多项式时间可解的。对于带有资源约束问题,若分配一定的资源,工件加工时间会减少。讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配量的交货期排序问题,其中所有工件有一个共同的交货期。目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配量之和最小,通过将其转化为指派问题,证明问题是多项式时间可解的。     

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.     

具有指数学习效应和恶化效应的可拒绝单机排序问题

讨论了带有工期窗口的单机排序问题。规定每个被接受的工件都有1个待定的交货期窗口,且所有工件的交货期窗口大小相同。工件的实际加工时间为与其开始时间和位置有关的指数函数。1个工件或者被拒绝,或者被接受。被拒绝就要支付拒绝的费用;被接受就会产生相应的提前、延误惩罚以及最大加工时间的惩罚。研究了2个问题,都需要确定工件的最优排序和窗口的开始时间,第1个问题的目标函数是与窗口的开始时间、窗口的大小、提前时间、延误时间、最大完工时间以及拒绝费用有关的函数。第2个问题的目标函数是与窗口的开始时间、窗口的大小、提前和延误的工件数、最大完工时间以及拒绝费用有关的函数。该问题在多项式时间可解,给出了问题的多项式时间算法。     

带指数学习效应和凸资源分配的单机排序问题研究

【目的】研究在全部工件加工时间可变的情况下具有指数学习效应和凸资源分配的单机排序问题,其中工件的实际加工时间具有指数学习效应,并依赖于分配它的不可再生资源数量。目标是确定资源的最优分配和工件最优排序,使得最大完工时间和资源消耗费用的3种组合最优,即最大完工时间和资源消耗费用的加权和最小、资源消耗费用限制下的极小化最大完工时间和最大完工时间限制下的极小化资源消耗费用问题。【方法】对给定排序,用约束优化和无约束优化问题的最优性条件能够求得其最优资源分配。【结果】分析最优解满足的性质,证明最优解能够通过多项式时间得到,并给出了具体求解算法。【结论】算法分析表明求解算法的时间复杂度为O(nlog n),其中n为工件个数。     

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

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

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

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

带有学习效应的加工时间可控退化工件单机排序问题

讨论了带有学习效应、加工时间可控的退化工件的单机排序问题。工件的实际加工时间是一个关于所排位置、开始加工时间和所分配资源的函数。加工时间可控是指工件的实际加工时间是一个依赖资源分配量的函数。目标是确定工件的最优排序、最优加工时间和最优资源分配量、极小化最大完工时间、总完工时间、完工时间差和资源消耗的总费用。考虑了2种情形:学习因子与工件有关的线性资源函数;将学习效应与工件的实际加工时间、依赖开始时间结合在一起的凸资源函数。通过分析最优解的一些重要性质,将这2个问题分别转化为指派问题,给出了2个计算复杂性为O(n3)的最优算法,证明了该问题是多项式时间可解的。     

具有一般截断因子和资源约束的单机工期窗口排序问题

【目的】研究具有一般的与任务有关的截断学习效应的凸资源单机窗口排序问题。【方法】任务的实际加工时间是所获得的资源量、与任务有关的学习效应以及控制参数的函数。在资源总量有限的条件下确定最优资源分配方案、最优公共工期窗口的位置及大小、最优的任务排序,使得由工件的提前惩罚、延误惩罚、窗口的开始时间和宽度、时间表长等构成的总费用最小。【结果】在上述总费用具有上界的前提下,求出最优决策变量使得资源总费用最小。【结论】分别给出了求解相应问题的多项式时间最优算法。     

带有学习效应和退化效应的可拒绝排序问题

讨论了具有学习效应和退化效应的多窗口的可拒绝单机排序问题。工件的实际加工时间与开始加工时间和所排位置有关。工件集分为接受工件集和拒绝工件集,对于被拒绝加工的工件而言,它的费用只与工件有关,目标是确定接受工件集的最优加工顺序和拒绝费用,从而极小化2个费用函数。考虑2个问题,第1个问题的目标函数是与提前、延误、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,第2个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,并且针对这2个问题分别给出了多项式时间算法。     

具有一般截断因子和资源约束的单机工期窗口排序问题

【目的】研究具有一般的与任务有关的截断学习效应的凸资源单机窗口排序问题。【方法】任务的实际加工时间是所获得的资源量、与任务有关的学习效应以及控制参数的函数。在资源总量有限的条件下确定最优资源分配方案、最优公共工期窗口的位置及大小、最优的任务排序,使得由工件的提前惩罚、延误惩罚、窗口的开始时间和宽度、时间表长等构成的总费用最小。【结果】在上述总费用具有上界的前提下,求出最优决策变量使得资源总费用最小。【结论】分别给出了求解相应问题的多项式时间最优算法。
     

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

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

资源约束下加工时间可变的工期窗口指派问题

研究单机排序下加工时间可变的工期窗口指派问题,任务的加工时间是关于所获资源分配量的一个凸函数,同时也考虑了学习、退化效应对任务加工时间的影响,即任务的实际加工时间依赖于该任务的加工位置和开始加工时间以及分配到该任务的资源量。每个任务都有一个独立的工期窗口,但所有任务的工期窗口宽度相同。目标是确定最优的工期窗口开始时间、工期窗口宽度、最优的资源分配量以及最优的任务排序。最小化提前、误工工件惩罚、工期窗口开始时间、工期窗口宽度、资源分配以及最大完工时间的总费用。证明了此问题是多项式时间可解的,并给出了最优算法。