共查询到20条相似文献,搜索用时 406 毫秒
1.
不误工工件加工时间之和最小的最优解 总被引:1,自引:0,他引:1
误工排序问题是经典排序论中最基本的问题之一。1968年Moore提出解决这个问题的算法,可以在时间O(nlogn)内得到最优解。误工问题推广到以下情况:或者某些工件必须不误工;或者工件的加工时间与工件的权有反向一致性;或者工件的加工时间与工件的权具有反向一致性,并且某些工件必须不误工等等。对于这些误工问题及其推广问题提出了多项式时间算法,证明了算法的最优性,并且证明了算法得到的最优解是所有最优解中不误工工件加工时间之和是最小的。 相似文献
2.
混合整数规划和约束规划在订单排产中的应用 总被引:3,自引:0,他引:3
实际生产中 ,为提高生产效率 ,按加工相似性把工件分为不同的批组 ,而不同批组工件在单机上进行加工处理时需要序独立的机器调整时间 .针对这一问题 ,以订单的最大延期为优化目标 ,提出 0 -1混合整数规划和约束规划两种求解模型 ,并通过使用OPLStudio编程来验算、比较两种模型在中小问题规模下的最优解 ,仿真结果表明 ,利用约束规划模型得到的最优解更有效 ,同时其结果可用于验证其他启发式算法的有效性 . 相似文献
3.
连续型批处理机调度问题是从钢铁生产线提炼出来的一种新型的批调度模型,该调度模型中,批的加工时间取决于该批的大小、批中工件的最大加工时间及机器的容量。研究目标函数为最小加权总完工时间的单机连续型批调度问题,分析最优解的性质,讨论最优的批内、批间序及分批策略,给出工件权值与加工时间逆序情况下的动态规划算法。 相似文献
4.
杨汉兴 《武汉钢铁学院学报》1995,18(3):346-351
求解具有公共交货和提前-滞后惩罚的单机排序问题是很困难的,其计算复杂性是强NP完全问题,作者研究这类问题的最优解的结构特征,得出了对于完工时间比公共交货期大的工件按WSPT序排列,对于完工时间少于公共交货期的工件按WLPT序排列,一般情况下的最优解具有V形结构的结论。 相似文献
5.
该文讨论工件加工时间为随机变量的单台机排序极大化期望按期完工工件数问题。在确定性排序问题中,Moore算法给出问题的最优解,但事实上Moore算法的期望值版本不能给出期望按期完工工件数最大化问题的最优解。文章从研究排序中工件的按期完工置信系数人手,结合Moore算法,提出了一个启发式算法,有效地解决了该随机排序问题的实际计算。 相似文献
6.
沈灏 《杭州电子科技大学学报》2005,25(6):86-89
讨论工件加工时间为随机变量的单机静态列表排序极大化期望按期完工工件数问题。对于单机排序加工时间为独立同分布随机变量问题1/Xi-F/E∑Uj以及EXi≥EXjD di≤dj时,该文给出了预期按期完工工件和预期误工工件的最优划分算法。对于一般问题,对给定的置信度,该文采用倒序算法逐个剔除累计按期完工概率增量最大工件,完成预期按期完工工件集与预期误工工件集的划分,并以此为依据给出排序,最后通过搜索最优置信系数得出排序结果。 相似文献
7.
范静 《上海第二工业大学学报》2016,(1)
在文中所研究的单机供应链排序问题中,机器可用时间段的长度不大于给定常数,且每个不可用时间段长度确定。工件仅可以在机器的可用时间段内被加工,完工后可与其他完工工件组成一批,由一个容量无限制的运输工具发送给客户。运输工具在机器的每个可用时间段结束时间进行发送,且每次发送的费用固定。问题的目标是安排工件的加工、发送,以及机器的不可用时间段,以使总发送时间与总发送费用之和达到最小。对于工件允许中断的情况,可在多项式时间O(n log n)内得到最优序(n为工件的个数)。对于工件不允许中断的情况,证明了问题是强NP-难的,并提出了2-近似算法。 相似文献
8.
工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.基于此,讨论了带准备时间和强制工期的n个工件在单机上加工,在机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,考虑了工件加工时间相等的特殊情形.先讨论问题的可行性,针对可行问题,提出了一个算法在多项式时间内获得最优排序. 相似文献
9.
该文讨论按期完工工件数最大化的窗时排序问题。文章首先提出一个基于EDD序的枚举算法,很大程度降低了纯枚举算法的计算复杂性。然后以改进的枚举法作基础构造了一个启发式算法——遗传算法求解该问题。算法采用0-1编码,基于EDD序规则调整各个工件的排列顺序。该算法在处理大规模的单机排序问题时,能够在较短的时间内得到近似最优解。实例计算证明,该遗传算法近似程度好,可操作性强,可以在实际应用中推广。 相似文献
10.
研究工件带有两道工序的单台机排序问题。在该问题中,工件的第一道工序先于第二道工序加工,并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间,目标是极小化所有工件的总完土时间。文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形。通过引入忌一连续加工的概念和分析最优解的性质,根据延迟时间的大小,分别设计了两个算法并证明了算法所得的排序为最优排序。 相似文献
11.
讨论了核为︱x-s︱~(-1)ln︱x-s︱的一种强奇异积分∫baln︱x-s︱/︱x-s︱f(xdx),给出了它的Hadamard有限部分积分的定义,并利用Lagrange线性插值构造了函数这类强奇异积分的数值算法,最后分析和讨论了算法的误差估计。 相似文献
12.
吕绪华 《武汉理工大学学报(信息与管理工程版)》2000,22(5)
研究了装配式流水作业排序问题的一个新模型,并对该模型相应的排序问题的计算复杂性进行了探讨,且证明了其在优化指标为作业排序长度的条件下该问题是NP-完全问题,没有多项式时间算法. 相似文献
13.
李跃波 《武汉理工大学学报》1994,(1)
在统计工作中,常常需要用到统计量|S|分布函数。本论文给出了求|S|分布函数的全过程,目的在于提供一种求|S|分布函数的方法.并据此给出了二元|S|的分布函数。论文内容新颖,方法独特。 相似文献
14.
为了实现李超代数osp(1|2)的范畴化,osp(1|2)的括号积在奇部分上的限制通过gl(2,)的BGG范畴和Harish-Chandra双模范畴之间的正合函子得到了范畴化.李超代数的括号积在奇部分上的对称性在上述范畴化结果中表现为2个gl(2,)的Harish-Chandra双模同构. 相似文献
15.
给出资源约束排序问题1|rj=bj-aj,∑uj≤U|Cmax中任务排列确定时,寻求最优资源分配的一个算法,并对该问题的最优排序做出了初步的探索. 相似文献
16.
以甲基三氯硅烷为原料,采用氯化、醇解和酯交换等反应,合成了1-氯甲基杂氮硅三环,并通过单因素实验方法对合成工艺条件进行了优化。在最佳条件下,1-氯甲基杂氮硅三环的总产率可达到54.5%,与文献报道的比较,具有产率高、能耗低等优点。并对反应过程中的副产物氯化氢气体进行了回收,减少了环境污染。 相似文献
17.
调整Newman结点组为Yn={αn-1,αn-2,…,α0=1},α=b-1n(b>1),当1b0>e时,得到其有理插值函数rn(Yn,x)对|x|(x∈[-1,1])的逼近速度分别为3b-n与3 exp(2(b4-1)b147lnb)-n。 相似文献
18.
李立亚 《南方冶金学院学报》2007,28(6):56-58
研究了两台平行同类机的一个半在线排序问题.当机器是有准备时间的同类机时,总加工时间已知,给出了一个竞争比至少为b 2/b 3的半在线算法,同时给出了证明. 相似文献
19.
以丙二酸二乙酯为原料,在强碱的作用下与氯乙酸乙酯反应得到乙烷-1,1,2-三羧酸三乙酯.采用新的非质子性溶剂N,N-二甲基甲酰胺,通过单因素实验,研究了反应条件对产物收率的影响.发现氢化钠为碱时收率最高,故在氢化钠为碱时,进一步通过正交实验,优化了反应工艺条件.得到的最优条件为投料比n(丙二酸二乙酯):n(氢化钠):n(氯乙酸乙酯)=1.4:1:1,反应温度为40℃,时间为8h,氯乙酸乙酯的滴加时间为45 min,在该条件下产品收率达到83.3%.产物用IR和1H NMR进行了表征. 相似文献
20.
张建科 《西安邮电学院学报》2011,16(5):83-86
针对含误差数据的混合0-1多项式优化问题,给出一种鲁棒优化方法,以提高其最优解的鲁棒性。该方法先将原问题转化为混合0-1线性规划,并在最坏情况下给出混合0-1线性规划的鲁棒对应模型,随后利用该鲁棒对应模型求解原优化问题。数值试验表明,该方法所求出的最优解具有良好的鲁棒性。 相似文献