首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 171 毫秒
1.
求解具有公共交货和提前-滞后惩罚的单机排序问题是很困难的,其计算复杂性是强NP完全问题,作者研究这类问题的最优解的结构特征,得出了对于完工时间比公共交货期大的工件按WSPT序排列,对于完工时间少于公共交货期的工件按WLPT序排列,一般情况下的最优解具有V形结构的结论。  相似文献   

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

3.
工件加工时间随工件开工时间线性增加的成组排序问题   总被引:9,自引:0,他引:9  
本文讨论了工件加工时间随工件开工时间线性增加的成组排序问题,考虑的目标函数是最大完工时间,在成组技术假设下得到了最大完工时间问题是多项式时间可解的。  相似文献   

4.
多目标排序是研究多个优化目标的排序问题,它在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。1956年Smith研究在没有工件误工的、所谓"完美的"(perfect)排序中寻找使平均完工时间为最小的排序问题,开创了研究多目标排序的先河。然而,在实际问题中往往是允许工件误工的,也就是说,工件可以在交货期之后完工,即允许工件有延迟或者延误,只是针对不同的问题对工件的延迟或者延误有不同的要求。研究以延迟和延误为第1目标的四个约束多目标排序问题,在最大延迟L_(max)、总延迟∑L_j、最大延误T_(max)或者总延误∑T_j不超过给定的量的约束条件下,寻找使平均完工时间为最小的排序,分别提出相应的算法。  相似文献   

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

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

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

8.
讨论工件加工时间为随机变量的单机静态列表排序极大化期望按期完工工件数问题。对于单机排序加工时间为独立同分布随机变量问题1/Xi-F/E∑Uj以及EXi≥EXjD di≤dj时,该文给出了预期按期完工工件和预期误工工件的最优划分算法。对于一般问题,对给定的置信度,该文采用倒序算法逐个剔除累计按期完工概率增量最大工件,完成预期按期完工工件集与预期误工工件集的划分,并以此为依据给出排序,最后通过搜索最优置信系数得出排序结果。  相似文献   

9.
最短准备时间排序   总被引:1,自引:0,他引:1  
本文证明了最短准备时间(SRT)排序使总的完工时间取得最小,并进一步分析了带有准备时间的带权误工工件数排序问题的一些性质.  相似文献   

10.
研究了加工时间依赖资源的成组排序问题.在这类问题中,加工时间是资源的线性函数,工件被分成若干个组,同组内的工件需连续加工,不允许分开,各工件组有固定的安装时间,目标函数为极小化加权总完工时间.针对这类问题构造了一个有效的下降算法.  相似文献   

11.
提出了一种基于S 粗集理论工件滚动调度策略 ,基于S 粗集理论的动态迁移特性和副集特性 ,研究了它在动态环境下滚动调度中的应用 .算例研究表明在有调度急加工工件、工件完成期改变和新加工工件到来等情况下 ,该方法是行之有效的 ,不仅能适应加工环境的动态变化 ,获得满意的调度结果 ,而且减少了调度问题求解的规模  相似文献   

12.
考虑多个工件在平行机上加工的生产调度问题,这些工件相互独立且有相同的交货期窗口,但交货期窗口的位置待定,其目标是最小化提前和延误的赋权工件数及交货期窗口定位费用的和.本文给出了这个强NP-困难问题的一个多项式时间近似序列(PTAS).  相似文献   

13.
以优势准则构建一个分枝状精确算法,最小化一个存在共同宽容交货期单机调度(排序)问题的加权超前延误工件总数,分枝个数可减少50%.  相似文献   

14.
不误工工件加工时间之和最小的最优解   总被引:1,自引:0,他引:1  
误工排序问题是经典排序论中最基本的问题之一。1968年Moore提出解决这个问题的算法,可以在时间O(nlogn)内得到最优解。误工问题推广到以下情况:或者某些工件必须不误工;或者工件的加工时间与工件的权有反向一致性;或者工件的加工时间与工件的权具有反向一致性,并且某些工件必须不误工等等。对于这些误工问题及其推广问题提出了多项式时间算法,证明了算法的最优性,并且证明了算法得到的最优解是所有最优解中不误工工件加工时间之和是最小的。  相似文献   

15.
研究了一般性的两个阶段的调度问题,第一阶段加工不同价值的工件,第二阶段把加工完的工件分批,并以不同的方式运送到指定的目的地.目标函数是使运输时间和运输费用的总和达到最小.由于本问题不仅包含了加权完工时间这一传统的评价尺度,并且包含了运输安排和费用,这两个条件都是物流调度的重要因素,所以我们称这个问题为整批运输的物流调度问题.  相似文献   

16.
针对网络运维现场作业调度中大量作业任务请求时效率低下、作业任务有所改变时无法自行调整等问题,提出基于改进遗传算法的网络运维中现场作业调度算法.该算法基于作业任务-资源的间接编码方式,结合网络运维中现场作业资源调度的特点,通过对每个维护人员设置作业任务数量的上限,避免某个维护人员负担任务数量过多,有利于提高服务质量以及资源的利用率.经过仿真实验,结果表明使用遗传算法可有效解决网络运维中资源调度问题.  相似文献   

17.
本文讨论的问题是在单台机器成组加工中为已经到达的工件集确定公共的交货期和工件的加工顺序,使因确定交货期所化代价和因误工造成的损失之和为最小。本文对满足成组技术假设和不满足成组技术假设这两种情况分别给出寻找最优解的多项式算法。  相似文献   

18.
本文研究了当所有工件同时到达且工期相同时的单机有界分批排序问题,给出了求解加权总误工数∑WJUJ问题的多项式时间算法.  相似文献   

19.
在工业生产中,生产决策者为了获得最大利润,可能接收一个工件,也可能拒绝一个工件.为了解决哪些工件应该被接收,哪些工件应该被拒绝问题,本文研究了工业生产中一个带有拒绝费用的工件排序问题,对该问题设计了一个动态规划算法.  相似文献   

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

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