检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

可拆分恒速机排序问题的一个近似算法

广西大学学报（自然科学版） 2011年第2期36卷 274-278页

作者：郑秋亚申尊焕王维琼长安大学理学院陕西西安710064 西安电子科技大学理学院陕西西安710071 西安电子科技大学经济管理学院陕西西安710071

为缩短工件的完工时间,研究目标为极小化最大完工时间的可拆分恒速机排序问题。在这个问题中,对工件拆分方式进行了限制,要求尽量少拆分工件,且拆分后子工件长度不小于给定阀值。该问题是NP难的。借助LPT算法的思想,提出了一个近似算法... 详细信息

为缩短工件的完工时间,研究目标为极小化最大完工时间的可拆分恒速机排序问题。在这个问题中,对工件拆分方式进行了限制,要求尽量少拆分工件,且拆分后子工件长度不小于给定阀值。该问题是NP难的。借助LPT算法的思想,提出了一个近似算法。多个实例的数值结果表明,本文算法可行、性能良好,能获得好的近似最优解。

关键词：算法完工时间排序拆分恒速机

在线全文

学校读者我要写书评

暂无评论

带有拒绝的若干恒速机排序问题

带有拒绝的若干恒速机排序问题

作者：富晓双沈阳师范大学

学位级别：硕士

在现实生活中,经常会遇到一些工件的加工时间取决于开始加工时间的情况,工件开始进行加工的时间越晚,实际加工的时间就越长。同时,工人在重复执行相同或者相似的任务后,他们可以获取经验,生产效率会随着时间而不断提高。因此,工件的排... 详细信息

在现实生活中,经常会遇到一些工件的加工时间取决于开始加工时间的情况,工件开始进行加工的时间越晚,实际加工的时间就越长。同时,工人在重复执行相同或者相似的任务后,他们可以获取经验,生产效率会随着时间而不断提高。因此,工件的排序越靠后,加工的时间就会变得越短,这种现象被称为学习效应。另外,由于资源有限,决策者可能会选择部分工件来加工,这样就会对没有加工的工件产生一些惩罚,叫做拒绝惩罚。除此之外,通常由于机器维修或故障等原因,机器在一定时间内不能工作,这也就是机器的不可用区间。本文讨论带有拒绝的若干恒速机排序问题。具体内容概括如下:1.对于极小化接受工件的最大完工时间和拒绝工件的总惩罚之和的问题,进行了如下研究:(1)讨论了带有退化、学习效应和拒绝的m台恒速机排序问题。首先,对目标函数进行了修改,对于这个NP-难问题,每台机器上接受的工件按照最短基本加工时间优先顺序排列可以得到最优解,给出了一个全多项式近似策略(FPTAS),并且分析了其时间复杂性为O(n3m+2L2m+2/ε2m+1)。(2)讨论了两台带有退化、拒绝和不可用区间的恒速机排序问题。在不可用区间前、后,及另一台机器上,工件按照{a,/b,}不减顺序进行排列可以得到最优解,给出了 FPTAS,时间复杂性为O(n6L4/ε3)。(3)讨论了两台带有拒绝和不可用区间的恒速机排序问题。首先,对目标函数进行了修改,给出最优解的性质,进而提出了一个FPTAS,其时间复杂性为O(n4L4/ε3)。2.对于极小化接受工件的总完工时间和拒绝工件的总惩罚之和的问题,讨论了带有退化、拒绝和不可用区间的两台恒速机的排序模型,其中的一台机器上带有一段不可用区间。对于这个NP-难的问题,依据最优解的性质,给出一个FPTAS,其时间复杂性为O(n9L6/ε5)。

关键词：排序恒速机退化拒绝不可用区间

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

两台恒速机两代理最大完工时间排序问题研究

两台恒速机两代理最大完工时间排序问题研究

作者：张峥上海财经大学

学位级别：硕士

本文主要考虑两台机器下工件加工可/不可中断的两代理排序问题,其中两台机器加工速度恒定;目标为其中一个代理最大完工时间满足不超过约束时间的情形下,最小化另一个代理最大完工时间。针对工件加工可中断问题,我们以单代理问题的最优... 详细信息

本文主要考虑两台机器下工件加工可/不可中断的两代理排序问题,其中两台机器加工速度恒定;目标为其中一个代理最大完工时间满足不超过约束时间的情形下,最小化另一个代理最大完工时间。针对工件加工可中断问题,我们以单代理问题的最优算法为基础,设计了求解两代理问题多项式时间最优算法并通过实例展示算法过程。针对工件加工不可中断问题,我们基于枚举思想,设计了拟多项式时间动态规划算法,最后设计了完全多项式时间近似方案(FPTAS)并给出证明与数值模拟。

关键词：排序问题两代理恒速机最大完工时间 FPTAS

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

具有周期维护的恒速机调度问题研究

具有周期维护的恒速机调度问题研究

作者：周菊贵州大学

学位级别：硕士

调度问题既存在于实际工业生产中,又存在于交通运输、通讯网络等领域中,有着广泛的应用背景.传统的调度问题通常假设机器可以一直被使用,在短期调度环境中,这种假设是合理的.然而,机器长期运行会导致机器过度磨损,甚至出现安全事故.因此... 详细信息

调度问题既存在于实际工业生产中,又存在于交通运输、通讯网络等领域中,有着广泛的应用背景.传统的调度问题通常假设机器可以一直被使用,在短期调度环境中,这种假设是合理的.然而,机器长期运行会导致机器过度磨损,甚至出现安全事故.因此,需要对机器设备进行预防性维护以提高生产效率,保证生产安全.基于此,本研究主要考虑了三类需要周期维护的恒速机调度问题,具体研究内容如下:首先,研究了加工时长均相等的最小化时间表长调度问题QmPM|pj=p|Cmax.由于该问题是P-问题,在多项式时间内可以获得精确解,故而针对不同情况设计了相应的精确算法,并给出最优时间表长表达式.其次,研究了加工时长不相等的最小化时间表长调度问题Q2PM|w≤T/3|Cmax,该问题是NP-难问题.在设计了混合整数规划模型以解决小型问题后,为解决中大型问题提出了启发式算法LLM,并证明了该算法的最坏情况界不超过2.最后,通过数值实验验证了 LLM算法的优越性.最后,研究了加工时长不相等的最小化总完工时间和调度问题Q2PM‖∑Ci,该问题是NP-难问题.首先,构建了以最小化总完工时间和为目标的混合整数规划模型.其次,总结了最优调度应有的性质,提出了MLL优化策略以及启发式算法ROPT.最后,通过数值实验验证了 ROPT算法的优越性.

关键词：周期维护恒速机时间表长总完工时间和数值实验

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

带激活费用的恒速机的有限资源博弈排序问题

带激活费用的恒速机的有限资源博弈排序问题

作者：桑琳曲阜师范大学

学位级别：硕士

本文主要研究在资源有限前提下带激活费用的恒速机上工件的博弈排序问题.机器初始状态未被激活,激活每一台机器都会产生一定的激活费用.没有中心权力者来控制排序,每一个工件相当于一个局中人,它们会极小化个体成本来选择机器进行加工,... 详细信息

本文主要研究在资源有限前提下带激活费用的恒速机上工件的博弈排序问题.机器初始状态未被激活,激活每一台机器都会产生一定的激活费用.没有中心权力者来控制排序,每一个工件相当于一个局中人,它们会极小化个体成本来选择机器进行加工,其中每一个工件的个体成本是它选择的机器的完工时间与其所要承担的那部分激活费用之和.用无序代价(POA)来衡量最差的纳什均衡(NE)排序的社会成本与最优值之间的差异.本文将有限台恒速机、激活费用综合考虑,分别对带激活费用的两台和m台恒速机的博弈排序问题的不同目标函数进行了研究.第一章主要介绍了排序问题、博弈理论和博弈排序问题的研究背景、相关理论知识和研究现状,并简要说明了本文的主要研究成果及创新点.第二章主要研究带激活费用的两台恒速机上工件的博弈排序问题的模型(?).模型中,两台机器的速度分别为1和α,机器的激活费用B与其速度相同.社会成本(?)为所有工件的个体成本Cj之和,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界α+1,证明并给出了POA下界α-1的一个实例.第三章主要研究带相同激活费用的m台恒速机上工件的博弈排序问题的两个模型,即(?).模型中,有m台速度不同的机器,机器Mi的速度为α1,假设α1机器的激活费用B均为1.模型一的社会成本(?)为所有工件的个体成本Cj之和,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界(?);模型二的社会成本Cmax为工件的最大个体成本,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界(?).第四章主要研究带不同激活费用的m台恒速机上工件的博弈排序问题的模型Qm(·),B=αi|ut=-Cj|Cmax.模型中,有m台速度不同的机器,机器Mi的速度为αi,激活费用B也为αi,假设α1<α2<…<αm且α1=1.社会成本Cmax为工件的最大个体成本,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界(?).

关键词：激活费用恒速机博弈排序纳什均衡(NE) 无序代价(POA)

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

处理机具有准备时间的恒速机排序问题

系统工程学报 2001年第2期16卷 111-115页

作者：赵传立唐恒永张庆灵东北大学理学院沈阳110005 沈阳师范学院数学系沈阳110034

讨论任务的加工是不可中断 ,处理机是恒速机且处理机具有准备时间的排序问题 ,对一般情况的 L PT排序的界做了改进 ,同时对 m =2的情况给出了一个与处理机加工速度有关的 L

关键词： LPT算法误差界排序问题恒速机处理机

在线全文

学校读者我要写书评

暂无评论

带有退化、拒绝和不可用区间的恒速机排序

沈阳师范大学学报（自然科学版） 2021年第3期39卷 224-229页

作者：赵玉芳富晓双田野沈阳师范大学数学与系统科学学院沈阳110034 北京市第五中学通州校区北京101100

考虑带有退化工件、拒绝和不可用区间的2台恒速机排序问题,其中一台机器上带有一段固定的不可用区间。该问题以实际生产环境为背景来研究机器的工件调度问题。在此模型中,每个工件的实际加工时间与它的基本加工时间、退化率和开始加工... 详细信息

考虑带有退化工件、拒绝和不可用区间的2台恒速机排序问题,其中一台机器上带有一段固定的不可用区间。该问题以实际生产环境为背景来研究机器的工件调度问题。在此模型中,每个工件的实际加工时间与它的基本加工时间、退化率和开始加工时间有关,工件的实际加工时间是其开始加工时间的线性递增函数,工件可以被拒绝,被拒绝的工件需要支付惩罚成本,在不可用区间内,机器无法加工工件。目标是极小化接受工件的最大完工时间与被拒绝工件的总拒绝惩罚之和。对于这个NP-难问题,在不可用区间前、后及另一台机器上,工件按{aj/bj}不减顺序排列可以得到最优解,通过过程划分的方法,提出了一个完全多项式时间近似策略(FPTAS),最后确定了其时间复杂性为O(n^(6)L^(4)/ε^(3))。

关键词：排序恒速机退化拒绝不可用区间

带有退化、拒绝和不可用区间的恒速机排序问题

在线全文

学校读者我要写书评

暂无评论

平顶山学院学报 2021年第5期36卷 9-18页

作者：富晓双赵玉芳田野沈阳师范大学数学与系统科学学院辽宁沈阳110034 北京市第五中学通州校区北京101100

考虑带有退化工件、拒绝和不可用区间的两台恒速机排序问题,其中第一台机器上有一个固定的不可用区间,每个工件的加工时间是它开始加工时间的简单的线性递增函数,一个工件可以通过支付惩罚而被拒绝.目标是极小化接受工件的总完工时间与... 详细信息

考虑带有退化工件、拒绝和不可用区间的两台恒速机排序问题,其中第一台机器上有一个固定的不可用区间,每个工件的加工时间是它开始加工时间的简单的线性递增函数,一个工件可以通过支付惩罚而被拒绝.目标是极小化接受工件的总完工时间与被拒绝工件的总惩罚之和.对于这个NP-难问题,提出了一个全多项式近似策略(FPTAS).

关键词：恒速机退化拒绝不可用区间

在线全文

学校读者我要写书评

暂无评论

具有周期维护的恒速机调度问题研究

数学的实践与认识 2021年第18期51卷 132-141页

作者：周菊程贞敏贵州大学数学与统计学院贵州贵阳550025

研究了m台需要周期维护的恒速机调度问题,其中m1台恒速机的加工速度为a、m-m1台恒速机的加工速度为1、目标函数为最小化时间表长.对m1=0以及m1=m这两种特殊情况,提出了最优算法EDL及相应的最优时间表长;对于一般情况0机器完... 详细信息

研究了m台需要周期维护的恒速机调度问题,其中m1台恒速机的加工速度为a、m-m1台恒速机的加工速度为1、目标函数为最小化时间表长.对m1=0以及m1=m这两种特殊情况,提出了最优算法EDL及相应的最优时间表长;对于一般情况0机器完成时间优先分配机制提出了MJCT算法,基于时间表长下界提出了MWA算法,并根据MJCT算法以及MWA算法得到了对应的最优时间表长.最后给出实例进行验证.研究结果在一定程度上推广了具有周期维护的恒速机的应用,推动了周期维护理论的发展.

关键词：恒速机周期维护调度算法时间表长