工件权重带限制的最小化最大加权完工时间的单机在线排序问题

本文考虑了最小化最大加权完工时间的单机在线排序问题,要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性,即apj≤wj≤bpj(a≥(5√−1)/2b,b≥a)且若wi>wj则pi≥pj,如果wi=wj则pi=pj。工件以时间在线的方式到达,只有工件Jj在达到释放时间rj后,决策者才知晓工件的基本信息,如加工时间pj和权重wj。对于此问题,首先利用对手法证明了其下界为1+b/(b+a),随后给出了竞争比为1+b/(b+a)的最好可能的在线算法。特别地,当a=(5√−1)/2b时,该算法的竞争比为(5√+1)/2。

面向飞机装配批架次完工时间的仿真预测方法

针对传统离散事件仿真方法缺乏对产品间差异化分析的局限性,提出一种面向飞机装配批架次作业过程的仿真预测方法。围绕飞机架次标签,研究对批架次装配作业过程中各类基本要素与交互关系的形式化定义,由此完成站位、整线仿真模型的构建;研究支持产品差异化分析的仿真推进框架与执行机制;以仿真结果数据为基础,提出基于区间估计法的架次完工时间预测方法。实验结果表明:该方法能准确地输出各架次预计完工时间的置信区间,为现场提供可靠的评估依据。

极小化总完工时间批调度问题的两种蚁群算法

针对考虑工件尺寸不同,求解目标为极小化总完工时间的批调度问题,考虑不同的编码方式,提出了基于工件序列的蚁群算法和基于批序列的蚁群算法。基于工件序列的蚁群算法算法采用传统的工件序列编码,需要启发式规则进行分批;基于批序列的蚁群算法算法利用蚁群算法构建性编码的特点,不需要启发式规则,而采取直接分批的方式编码,充分发挥蚁群算法自身的搜索能力。针对总完工时间的优化目标,基于批序列的蚁群算法算法引入批权重构建启发式信息;针对批调度特有性质,基于批序列的蚁群算法算法加入新的信息素更新变量,设置不同的信息素初始值,并采用局部优化技术等改进措施,以克服传统蚁群算法收敛速度慢,易陷入局部最优的缺点。通过对比实验验证了所提算法的有效性。

自动化制造单元最小完工时间调度问题的混合启发式算法

自动化制造单元最小完工时间调度问题属于NP-hard难题,目前尚缺乏有效的调度方法。为此,提出基于遗传和禁忌搜索的混合启发式算法,用以搜索一组最满意的机器人搬运作业排序。以遗传算法为基本结构,在初始种群产生和交叉、变异操作中引入禁忌搜索技术,以提高优化质量。基于搬运作业规则的初始种群构造算法和两阶段交叉、变异算子克服了传统算子对可行搬运作业排序的破坏,而邻域移动算子则保证了禁忌搜索的多样性和集中性。最后,随机实验结果验证了算法的有效性。

具有学习效应的总完工时间流水作业问题

研究工件具有学习效应的2台机器流水作业排序问题。工件的学习效应指工件的加工时间为所排位置的指数函数。目标函数为极小化总完工时间。给出该问题的数学规划模型。同时对大规模问题给出3个启发式算法,计算结果表明,用这3个算法解决所研究问题比较有效。

极小化加权总完工时间的分批排序问题

本文讨论了分批排序中极小化加权总完工时间的两个问题.就所有工件的加工时间都相等这一特殊情况,分别给出两个算法,并证明了算法的最优性.

最小化总完工时间的流水作业调度混合算法

针对有效求解NP难的总完工时间最小流水作业调度问题,提出了一个有效的混合启发式算法产生初始解,并使用禁忌搜索算法对初始解邻域进行搜索的算法框架.基于不同的启发式算法,获得了3个混合禁忌搜索算法HA1,HA2和HA3.使用Taillards基准程序随机产生的大量实例,进行模拟实验,结果表明,所提出的3个算法通过扩大搜索范围提高了解的质量,在性能上均优于目前最有效的启发式算法.与目前最有效的算法相比,产生最好解的平均百分比偏差均下降至少30%,最优解所占比例皆有显著提高.

云计算中最小化任务完工时间的多资源调度算法

云计算中Hadoop平台上默认调度方式FIFO是以公平性为目标,然而考虑单一因素会使资源利用率低下以及任务完成时间过长。在公平性和完成时间的权衡中,运行时间指标更为重要。据此,建立云计算下多资源和应用程序任务以及调度的数学模型和其目标函数,运用归约方法和具有强大计算能力的工具MINI SAT SOLVER去求解问题。仿真实验结果表明,在不同的资源供给条件下,基于MINI SAT SOLVER的次优算法比YARN(Yet Another Resource Negotiator)中默认的调度算法FIFO缩短了任务的完工时间,优化比率最高可以达到30%。

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案(英文)

本文考虑n个工件的无限批量机器调度问题.一台机器可以同时加工B≥n个工件.每个工件具有一个正权因子、一个释放时间和一个加工时间.一个批次的加工时间是该批次所包含所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.对于最小化加权完工时间和问题,本文给出了第一个多项式时间近似方案(PTAS).对任意给定精度,该算法的运行时间为线性的.

极小化加权完工时间和的无界批量机器并行调度问题(英文)

考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).

极小化加权完工时间和的Flowshop问题的算法(英文)

本文讨论了极小化加权完工时间和的Flowshop问题.我们给出了一个最坏情况误差界为m的启发式算法,对于m=2的情况,如果工件具有一致权因子,即pi<pj意味着wi≥wj,(i,j=1,2,…,n).最坏情况误差界为2β/α+β,其中α和β分别是全部工序加工时间的最小值和最大值.此外,分析了m=2的两种特殊情况,给出了多项式算法.

平行批排序最小化最大完工时间在线算法的一个注记(英文)

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5+1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1+α)r+αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.

极小化完工时间和的有界批调度问题(英文)

考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.

极小化最大完工时间的单机分批加工问题(英文)

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b<n) 个工件．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间．对于极小化最大完工时间问题,本文给出了一个多项式时间近似方案(PTAS)．该算法的总运行时间为O(n log n+C·n),C仅与精度∈有关．这一结果改进了已有的两个多项式时间近似方案．

反相容工件系统的加权完工时间和的重新排序问题(英文)

重新排序问题是指在原始工件已经安排好的情形下,新到的工件集与原始工件集一起重新再排序,这是实际工作中常见一类优化问题。本文考虑了单机上当工件加工时间与权重反相容时,在最大错位量约束下的加权完工时间和最小化的重新排序问题。对于提出的四个问题,即在最大序列错位、最大时间错位、总序列错位和总时间错位约束下的加权完工时间和重新排序,基于问题的结构性质,运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法。

特殊工艺约束下最小完工时间调度问题的新并行遗传算法

针对在特殊工艺约束下非等同并行机最小完工时间调度问题,设计了一个基于向量组编码的新的遗传算法。此算法的编码方法简单,能有效地反映实际调度方案,并能保证交叉和变异后染色体满足约束条件,收敛速度快。同时为更好地适应调度实时性和解决大型企业此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性。

网格作业完工时间与作业分割粒度的关系

对可分割的计算密集型大型作业在并行且不间断运行情况下的完工时间与作业分割粒度之间的关系进行研究。首先分析了子作业之间无通信和有通信两种情况下可分割计算密集型大型作业的完工时间和分割粒度的关系,然后对可分割计算密集型大型作业在专用网格资源上的完工时间与分割粒度的关系进行仿真。仿真结果显示,大型作业的完工时间随着分割粒度的增大先减小后增大;当单个子作业的计算时间和通信时间之比增大时,作业的分割粒度可以更细,作业完工时间的最小值减小。因此完工时间最优的作业分割粒度不能过粗或过细。

单台机器总完工时间排序问题的反问题

运筹学和最优化的种种问题(“正问题”)是在已知各有关参数或者数据的条件下,找出最优(最快、成本最省或者效益最大)的方案.所谓的“反问题”,是指已经有一个方案,但在目前的情况下,该方案并非最优,需要考虑如何最小限度地改变现有参数,使这个方案成为最优的方案.如果说“正问题”的研究有助于一个新系统的设计和确定,那么“反问题”的研究对改善现有系统的性能具有重要的意义.本文以数学规划为工具。

极小化最大完工时间的批到达同时加工排序问题

考虑工件成批到达的同时加工排序问题,目标函数为极小化最大完工时间.给出模型在特殊情况下的统筹算法和针对一般情况的局部统筹算法,并通过大量的实例计算来验证两启发式方法的有效性.

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究 3台机器调整时间可分离的无等待 Flow Shop排序问题 ,目标函数为极小化折扣加权总完工时间。对某些特殊情况 ,给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待 Flow Shop排序问题的分派规则。