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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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