首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 78 毫秒
1.
交货时间区间内完工工件个数最多的近似算法   总被引:1,自引:0,他引:1  
在现代生产管理中,合理安排工件使所加工的工件准时交货是极其重要的,工件提前完工和延误完工都会增加费用,使尽量多的工件在其对应交货时间区间内完工的排序问题是NP困难的。本文讨论了m台平行机交货时间区间内完工工件个数最多的排序问题,给出了一个求解这一问题的多项式时间近似算法。  相似文献   

2.
讨论了具有就绪时间与先后约束的工件可拒绝排序,其目标函数是所拒绝加工工件的总拒绝费用与加工工件的带权总完工时间之和。应用线性规划松弛方法设计了近似算法,得到(3+√3)-近似算法。  相似文献   

3.
研究了工件可拒绝排序问题.考虑目标函数是拒绝费用与带权总完工时间之和,应用线性规划松弛方法设计了近似算法,当工件之间没有优先关系时得到3-近似算法,当工件之间具有优先关系时得到4-近似算法.  相似文献   

4.
研究以工件总完工时间为第1目标的多目标不相容分批排序问题,对于加权总完工时间和最大延误为第2目标的排序问题给出了多项式时间的算法。对于误工工件个数和工件总延误为第2目标的排序问题的不同情况进行了讨论,给出了多项式时间算法或证明了其复杂性。  相似文献   

5.
研究了多个工件在多台机床上顺序加工,满足不同工件时间约束下总体加工时间最短的排序问题。建立了该问题的0-1整数优化模型,编写了基于LINGO软件的求解方程,算例表明了该模型的有效性。  相似文献   

6.
该文讨论工件加工时间为随机变量的单台机排序极大化期望按期完工工件数问题。在确定性排序问题中,Moore算法给出问题的最优解,但事实上Moore算法的期望值版本不能给出期望按期完工工件数最大化问题的最优解。文章从研究排序中工件的按期完工置信系数人手,结合Moore算法,提出了一个启发式算法,有效地解决了该随机排序问题的实际计算。  相似文献   

7.
工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.基于此,讨论了带准备时间和强制工期的n个工件在单机上加工,在机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,考虑了工件加工时间相等的特殊情形.先讨论问题的可行性,针对可行问题,提出了一个算法在多项式时间内获得最优排序.  相似文献   

8.
研究了工件可拒绝排序问题.考虑目标函数是拒绝费用与带权总完工时间之和,应用线性规划松弛方法设计了近似算法,当工件之间没有优先关系时得到3-近似算法,当工件之间具有优先关系时得到4-近似算法.  相似文献   

9.
把分批排序和可控排序问题相结合,讨论了加工时间可控的分批排序问题.目标函数是使最大完工时间和加工时间可控所需费用的总和最小.对工件具有动态的到达时间,设计多项式时间的动态规划算法。  相似文献   

10.
本文以合理安排生产任务、提高设备利用率、缩短生产周期为目的,提出一种新的计算设备空闲时间及工件等时间的简便方法,即表格计算法,该方法可以很容易地计算出各设备等待工件的空闲时间以及各工件等待设备的等待时间和工艺周期,为进一步编制更详细的生产调度计划提供可靠的依据。  相似文献   

11.
对超大规模集成电路芯片(VLSI)的缺陷修复可归结为受二分图约束的顶点覆盖问题,该问题属于NP完全问题。目前仍不能在多项式时间内对该问题求解。本文应用参数计算理论,将问题化简为与输入问题规模无关的问题来求解。并利用二分图的特性,提出了一种简单、高效的算法,大大提高了修复速度。  相似文献   

12.
研究了可中断的带有到达时间的使总完工时间最小的恒速机排序问题.工件最多被截断2N次,其时间复杂性为N(nlogn).此问题是NP-难的,对一些特殊情况进行分析,给出了最优算法.  相似文献   

13.
钢铁生产中的加热炉调度问题是一类复杂的组合优化问题。本文进一步考虑不同轧制位对应的候选板坯集存在交集的生产实际,建立了以板坯住炉时间最小为优化目标的数学模型,提出了三阶段的启发式算法,确定各轧制位板坯的入炉和出炉时间。仿真实验表明,给出的模型和求解算法对加热炉调度问题的优化效果很好。  相似文献   

14.
针对毫微微基站(FBS)在不同时间段用户数量的差异,研究了最大化下行总信息量的功率分配问题.不同时间段包含忙时和闲时2个阶段,忙时用户数量较多,闲时用户数量较少.通过部署一个无人机携带的微微基站(PBS-UAV)为多个FBSs闲时的用户提供服务.FBS和PBS-UAV都具有能量收集功能.在FBS忙时,FBS和PBS-UAV同时从宏基站收集能量,并且向用户发送数据.FBS闲时,由PBS-UAV接替多个FBSs,与用户进行下行通信.将功率分配问题建模为最优化问题,以最大化FBS和PBS-UAV的下行信息量为目标,同时满足FBS和PBS-UAV能量消耗及发射功率的约束条件.由于建立的最优化问题是凸优化问题,可通过引入增广拉格朗日乘子法获得最优解.仿真结果表明,与PBS-UAV参与的等功率及部分功率固定的方法相比,所提出的方法在总信息量方面有不同程度的增加.  相似文献   

15.
用加强学习方法解决基于神经网络的时序实时建模问题   总被引:1,自引:0,他引:1  
提出了将基于神经网络的时序一步预测模型的实时建模预测问题归结为加强学习问题,从而提出用时差法和误差反向传播法分别解决时间信用赋值问题和结构信用赋值问题.实验结果表明,该方法可以提高预测精度.  相似文献   

16.
针对目前无线Mesh网络尚未解决多网关接入时最小链路调度时间下限估计的问题,提出一种计算该时间下限的方法,其本质是基于资源分配的Pareto 优化计算过程. 采用拉格朗日方法进行求解,并通过Lyapunov函数找出基于最优速率的多网关接入的最小链路调度时间. 该方法不仅能准确地计算出最小链路调度时间下限,并用于评估网络性能,还能优化无线Mesh网络上行链路调度速率,提高链路的吞吐量.  相似文献   

17.
针对复杂双容水箱系统,以控制两个下水箱液位跟踪设定值为设计目标。为实现良好的水箱液位控制效果,首先构造液位控制的无穷时域性能指标,建立了复杂双容水箱无穷时域性能优化问题的数学描述;随后将基于时间分解协调的递阶优化和预测控制的滚动优化思想引入水箱液位控制,将优化时域较长所引起的大规模参数优化问题分解为各时间点上独立的小规模参数优化问题,从而得出显式优化解,取得较优的水箱液位控制效果。  相似文献   

18.
排课就是解决时间和空间对资源的争夺引起的冲突问题.20世纪70年代中期,美国人S,VEN等论证了课表问题是N P完全类问题,但同时也说明了课表问题有其自身固有的数学模型,即课表问题存在解,并且能找到解.直到今天,国内外对课表问题的研究活动依然很活跃.  相似文献   

19.
旅行推销员问题(TSP问题)是算法研究的经典问题,该问题属于典型的NP难题。研究解决此问题尽可能少计算时间的算法具有重要意义。本文通过研究一种启发式搜索算法,把TSP问题的矩阵通过一种启发式准则约简和搜索,尽量地简少了搜索的范围。  相似文献   

20.
介绍了一种适合于支持NetBios协议下的所有以太局域网络环境的实时数据通信的实现方案,解决了在这些网络环境下实时数据由一台工作站的内存到另一台工作站的内存的实时传输问题,并给出了在这种通信方式下可能出现问题的解决方法.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号