检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

带有拒绝工件的公共窗口指派单机排序问题

沈阳航空航天大学学报 2022年第2期39卷 91-96页

作者：徐景孝吕丹阳王吉波沈阳航空航天大学理学院沈阳110136

讨论具有工件可拒绝的单机公共窗口指派单机排序问题,公共窗口指派指的是公共窗口的开始时间和窗口长度都是决策变量。如果工件在窗口期内完工,将不会产生任何额外费用,否则工件将会产生提前或者延误费用;若工件被拒绝,则会产生拒绝费... 详细信息

讨论具有工件可拒绝的单机公共窗口指派单机排序问题,公共窗口指派指的是公共窗口的开始时间和窗口长度都是决策变量。如果工件在窗口期内完工,将不会产生任何额外费用,否则工件将会产生提前或者延误费用;若工件被拒绝,则会产生拒绝费用。目标是确定可加工的工件集、可加工工件集中的工件排列顺序与公共窗口的位置使得排序费用(包括提前、延误与公共窗口指派的费用)和拒绝费用的加权和最小,其中权重只与工件被排在序列中的位置有关,即位置权重。证明了此问题是多项式时间可解的,并给出了具体求解算法。

关键词：单机排序拒绝工件窗口指派多项式时间

带到达时间、不可用区间、拒绝工件的单机排序问题

在线全文

学校读者我要写书评

暂无评论

重庆师范大学学报（自然科学版） 2013年第1期30卷 17-20页

作者：刘澈罗成新沈阳师范大学数学与系统科学学院沈阳110034

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个... 详细信息

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件。本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出了一个近似算法,并通过引理1证明出此算法是3-因子算法;其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O(n2/ε)

关键词：到达时间拒绝工件不可用区间时间表长

带有拒绝工件和机器具有不可用区间的单机排序问题

在线全文

学校读者我要写书评

暂无评论

重庆师范大学学报（自然科学版） 2014年第2期31卷 5-9页

作者：赵升华罗成新沈阳师范大学数学与系统科学学院沈阳110034

本文考虑带有拒绝工件和机器具有不可用区间的单机排序问题。目标是最小化被接受工件的特定加权总完工时间与被拒绝工件总费用的和。工件有不同的释放时间和权,权等于它们的加工时间。这个问题是一般NP-难的。为了能在较少的运行时间内... 详细信息

本文考虑带有拒绝工件和机器具有不可用区间的单机排序问题。目标是最小化被接受工件的特定加权总完工时间与被拒绝工件总费用的和。工件有不同的释放时间和权,权等于它们的加工时间。这个问题是一般NP-难的。为了能在较少的运行时间内得到该问题较好的近似解,利用削减状态空间的方法得到了一个全多项式时间近似方案(FPTAS),该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n3/ε2),其中n为输入工件的个数,ε是误差界。

关键词：释放时间拒绝工件不可用区间特定加权流时间全多项式近似方案

带有拒绝工件和学习效应的资源约束排序问题研究

在线全文

学校读者我要写书评

暂无评论

重庆师范大学学报（自然科学版） 2021年第1期38卷 114-120页

作者：国峰王吉波沈阳航空航天大学理学院沈阳110136

【目的】研究工件加工时间具有学习效应以及工件可拒绝的单机排序问题。在线性和凸资源分配函数的两种模型下,为求得可接受加工的工件集合、可拒绝工件的集合以及确定可接受工件集合中的最优工件排序,使工件的时间表长、总完工时间、资... 详细信息

【目的】研究工件加工时间具有学习效应以及工件可拒绝的单机排序问题。在线性和凸资源分配函数的两种模型下,为求得可接受加工的工件集合、可拒绝工件的集合以及确定可接受工件集合中的最优工件排序,使工件的时间表长、总完工时间、资源耗费费用和工件拒绝费用的加权和最小。【方法】对于线性资源分配函数问题,在拒绝工件数给定的情况下,此问题可转化为指派问题。对于凸资源分配函数问题,此问题可以用动态规划算法进行求解。【结果】对于带有拒绝工件和学习效应的资源约束排序问题给出了最优求解算法,且它们的时间复杂度分别为O(n4)和O(n3),其中n为工件的个数。【结论】算法分析和CPU运算时间表明给出的求解算法非常有效。

关键词：排序拒绝工件资源分配学习效应

在线全文

学校读者我要写书评

暂无评论

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

重庆师范大学学报（自然科学版） 2012年第6期29卷 15-19页

作者：张敏娇罗成新沈阳师范大学数学与系统科学学院沈阳110034

考虑带有拒绝工件和机器维修区间的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要支付拒绝惩罚)的和。这个问题是一般意义下NP-难的,因此需要快速寻找满足指定精确度要求的近似解。为了... 详细信息

考虑带有拒绝工件和机器维修区间的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要支付拒绝惩罚)的和。这个问题是一般意义下NP-难的,因此需要快速寻找满足指定精确度要求的近似解。为了能在较少的运行时间内得到该问题的较好的近似解,利用削减状态空间方法得到了一个全多项式时间近似方案(FPTAS)。该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n2/ε2),其中n为输入工件的个数,ε>0为任意小的实数。

关键词：单机排序维修区间拒绝工件 NP-难近似算法

带到达时间和不可用区间以及拒绝工件的排序问题

在线全文

学校读者我要写书评

暂无评论

带到达时间和不可用区间以及拒绝工件的排序问题

作者：刘澈沈阳师范大学

学位级别：硕士

排序问题是一类重要的组合最优化问题。在经典排序里，研究者通常假定工件加工商必须接受加工买家要求的全部工件，也就是说，不能拒绝加工任意一个工件。但是，这并不符合生产者的利益要求，工件加工商为了使利益最大化，或者更为通俗... 详细信息

排序问题是一类重要的组合最优化问题。在经典排序里，研究者通常假定工件加工商必须接受加工买家要求的全部工件，也就是说，不能拒绝加工任意一个工件。但是，这并不符合生产者的利益要求，工件加工商为了使利益最大化，或者更为通俗地说，为了创造更大的生产效益，就不会去加工那些加工时间很长，但是获取利益却很小的工件，同时也会因此而赔款。此种情况放在排序问题里，称为带有拒绝工件。在加工生产时，机器可能因为发生故障或者其他意外，使得机器在一段时间里不能进行工作。此种情况放在排序问题里，称为机器带有不可用区间。由于这些问题很可能在现实生产中发生，所以，越来越多的学者对既有不可用区间又有拒绝工件的排序问题进行了大量的研究。本文对带到达时间和不可用区间以及拒绝工件的排序问题进行了研究，主要内容如下：第一章介绍排序问题的定义及三参数表示法，并介绍带有不可用区间和拒绝工件的排序问题的一些研究现状以及本文工作。第二章我们采用构造输入数据的方法处理带到达时间和不可用区间以及拒绝工件的单机排序问题，我们的目标是最小化加工工件的时间表长和拒绝工件的惩罚的和，设计了一个全多项式时间近似方案。第三章我们通过改变动态规划算法的执行过程来处理带到达时间和不可用区间以及拒绝工件的单机排序问题，最小化的函数是所有放在机器上加工的工件的时间表长与所有被拒绝的工件的惩罚的和，给出了一个全多项式时间近似方案。第四章研究的是带到达时间和不可用区间以及拒绝工件的两台平行机排序问题。

关键词：到达时间拒绝工件不可用区间时间表长全多项式时间近似方案

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

加工时间可变和带有拒绝工件的排序问题

加工时间可变和带有拒绝工件的排序问题

作者：赵升华沈阳师范大学

学位级别：硕士

排序问题是组合最优化中一类重要问题。经典的排序问题中，所有的工件必须被接受，工件的加工时间为固定常量。然而，在某些实际问题中，工件可以被拒绝，工件的加工时间往往与其所排位置、开工时间或分配的资源有关。本文包括五个部... 详细信息

排序问题是组合最优化中一类重要问题。经典的排序问题中，所有的工件必须被接受，工件的加工时间为固定常量。然而，在某些实际问题中，工件可以被拒绝，工件的加工时间往往与其所排位置、开工时间或分配的资源有关。本文包括五个部分。首先介绍了排序问题的一些背景知识和本文所做的工作。第二章讨论带有退化效应，学习效应和资源分配的交货期指派的单机排序问题。所有工件有一个共同的交货期，工件如果在交货期内完工不产生费用，而在交货期之前或之后完工产生相应的提前或延误费用。工件的实际加工时间为与资源分配、开工时间和在排序中位置有关的函数。目标是确定最优交货期的位置、交货期的大小、最优资源分配和工件最优排序，最小化包括提前、延误、交货期位置、交货期大小和资源消耗的总费用。证明该问题是多项式可解的，并给出了一个最优算法。第三章考虑带有拒绝工件和机器具有不可用区间的单机排序问题。工件有不同的权和释放时间，权等于工件的加工时间。目标是最小化被接受工件的特定加权总完工时间和被拒绝工件总费用的和。这个问题是一般NP-难的。给出了一个全多项式时间近似方案。第四章讨论在同类机环境下，带有退化效应和拒绝的排序问题。工件的加工时间是与开工时间有关的线性不减函数。对于每一个工件能通过支付一定的费用而拒绝加工。目标为最小化接受工件的最大完工时间和拒绝工件总费用的和。给出一个全多项式时间近似方案，从而证明了这个问题是一般NP-难的。最后，对本文内容进行了总结，并提出了未来某些可进一步研究的问题的方向。

关键词：排序学习效应退化效应资源分配拒绝工件

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

带有拒绝工件的资源分配排序问题研究

带有拒绝工件的资源分配排序问题研究

作者：国峰沈阳航空航天大学

学位级别：硕士

研究带有拒绝工件的资源约束排序问题,工件的加工时间可以表示为资源的线性函数和凸函数两种模型。在考虑带有拒绝工件时,产生两种目标费用,即接受集中的加工时间费用和拒绝集中的拒绝费用。本文主要研究内容如下:第一章介绍了组合优化... 详细信息

研究带有拒绝工件的资源约束排序问题,工件的加工时间可以表示为资源的线性函数和凸函数两种模型。在考虑带有拒绝工件时,产生两种目标费用,即接受集中的加工时间费用和拒绝集中的拒绝费用。本文主要研究内容如下:第一章介绍了组合优化中排序问题的衍生和发展,以及带有拒绝工件和资源约束排序问题的研究背景与意义。第二章和第三章分别研究了带有拒绝工件和恶化效应的线性和凸资源约束排序问题。在工件具有过去独立安装时间的约束下,对于不同恶化因子情况,本文提出利用指派问题求解接受集中的加工时间费用(包括最大完工时间(总完工时间,总完工时间偏差和,总等待时间偏差和)与资源消耗费用)和拒绝集中的拒绝费用加权和最小问题。对于相同恶化因子情况,利用动态规划算法极小化如下问题:1)接受集中的加工时间费用和拒绝集中的拒绝费用的加权和,并得到其算法复杂度为O(n3),其中n为工件总数量;2)在拒绝集中的拒绝费用有限制的条件下,极小化接受集中的加工时间费用;3)接受集中的加工时间费用有限的条件下,极小化拒绝费用。对于2)和3)这两个NP-难问题,分别提出伪多项式时间算法,其算法复杂度分别为O(n3E)和O(n3T),其中E,T为给定常数。本文对于不同和相同恶化因子条件下,给出了数值模拟,实验结果表明本文算法是非常有效的。第四章为结论与展望,对本论文研究内容进行归纳总结与展望。

关键词：排序拒绝工件资源约束指派问题动态规划

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

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

重庆师范大学学报（自然科学版） 2013年第6期30卷 17-21页

作者：陈东赵传立沈阳师范大学数学与系统科学学院沈阳110034

讨论了带有交货期窗口和工件可拒绝的单机排序问题﹐这一问题是将所有的工件分成两个集合﹐一个是被接受的工件集﹐一个是被拒绝的工件集。假设被接受的每个工件都有一个待定的交货期窗口﹐且所有工件的交货期窗口的大小是相同的﹐如果... 详细信息

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

关键词：排序单机交货期窗口拒绝工件接受工件