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

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

在退化维修活动下具有多窗口及退化效应的单机排序问题

【目的】对多窗口和具有退化效应与退化维护活动的单机排序问题进行求解。【方法】假设任务的实际加工时间是关于该任务加工位置的函数,一个窗口不能包含另一个窗口。由于机器存在退化效应,适时地对机器进行维护能提高机器的生产效率。一旦维护活动结束,机器恢复到最初状态,并且任务的退化效应更新,机器维护活动持续的时间取决于维护活动的开始时间。将所有任务分成若干个任务集,任务集个数已知,每一个任务集共用一个窗口。目标是得到每个任务集最优窗口的位置、大小和最优维护活动的位置及任务的最优加工顺序使得任务的提前惩罚费用、延误惩罚费用、窗口开始时间及宽度费用之和最小。【结果】证明了此问题可以通过转化为指派问题求得最优解。【结论】并给出一个多项式时间算法来解该问题。     

工期窗口指派可控处理时间资源约束最大费用最小化排序问题

【目的】研究具有公共工期窗口指派的凸资源单机排序问题。【方法】任务的处理时间与所在位置有关,并且可以通过分配一定的资源加以控制,是所获得的资源量的凸函数。目标函数是所有任务费用中的最大值。考虑两个问题。第1个问题是在资源总量有上界限制条件下,确定任务的最优排序、公共工期窗口位置和大小以及资源分配方案,使得最大费用最小。第2个问题是在最大费用有上界限制条件下,求出最小资源总量、任务排序和公共工期窗口位置和大小,使得资源总量最小。【结果】将上述问题转化为非线性凸规划问题和指派问题加以处理。证明了两个问题均可以在多项式时间内求解。【结论】对于考虑的两个问题分别给出了多项式时间最优算法。     

在退化维修活动下具有多窗口及退化效应的单机排序问题

【目的】对多窗口和具有退化效应与退化维护活动的单机排序问题进行求解。【方法】假设任务的实际加工时间是关于该任务加工位置的函数,一个窗口不能包含另一个窗口。由于机器存在退化效应,适时地对机器进行维护能提高机器的生产效率。一旦维护活动结束,机器恢复到最初状态,并且任务的退化效应更新,机器维护活动持续的时间取决于维护活动的开始时间。将所有任务分成若干个任务集,任务集个数已知,每一个任务集共用一个窗口。目标是得到每个任务集最优窗口的位置、大小和最优维护活动的位置及任务的最优加工顺序使得任务的提前惩罚费用、延误惩罚费用、窗口开始时间及宽度费用之和最小。【结果】证明了此问题可以通过转化为指派问题求得最优解。【结论】并给出一个多项式时间算法来解该问题。
     

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

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

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

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

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

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

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

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

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

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

带有学习与恶化效应的共同工期指派问题

【目的】研究在共同工期指派模型下,工件的实际加工时间既有学习效应(与所排位置有关)又有恶化效应(与开工时间有关)的排序问题,其中机器限定为一台。【方法】为求得最优排序,使得工件的提前、延误和工期成本的线性加权和最小,其中权重为位置权重,工件的共同工期为决策变量,此问题可转化为经典的运筹学方法求解,即求解指派问题。【结果】这个问题在位置权重、学习与恶化效应下依然是多项式时间可解的。【结论】算法分析和实例表明给出的求解算法是非常有效的。     

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

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

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

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

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。     

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。
     

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

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

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

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

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为 0.4117 ,分支定界算法的效率比较高,处理 100 个工件所用的最大时间不超过 460s 。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。
     

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为0.411 7,分支定界算法的效率比较高,处理100个工件所用的最大时间不超过460s。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。     

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

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

交货期窗口待定的有界同时加工排序问题的最优算法

结合窗时排序与同时加工排序,考虑单机器上批容量有限的情形,为享有公共交货期窗口[e,d]的n个工件分批并排序,以最小化总的赋权提前和延误的工件个数;将最早交货期e和窗口大小K作为未知参数,与最优序列一起确定使得总费用最小。在给出的最优排序的若干性质基础上提出了多项式时间算法。