三台机并行工件排序问题的改进的下界

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。     

带等级约束的多重工件在线(半在线)排序问题

论文提出了带等级约束的多重工件排序问题,每个客户提交多个加工时间和等级相同的工件。目标是寻找一个调度方案,使得机器的最大完工时间最小。当客户的信息未知时,论文设计了一个竞争比为5/3的在线算法。当所有工件的加工时间总和已知时,论文设计了一个竞争比为3/2的半在线算法。这些结论对经典带等级约束的两台平行机排序问题进行了推广。     

恒速机上的MapReduce在线排序算法下界研究

本文研究源自于MapReduce模型系统的一类排序问题。给定两台恒速机和一批按列表到达的工件,每个工件包含两类任务:Map任务和Reduce任务。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得这批工件的最后完工时间最小。对|M_j|≥|R_j|的情形,我们证明了任意在线算法的竞争比不小于1+(1/(2s+2)).     

工件加工时间在某一区间的可中断半在线排序

排序(又称为调度)问题是组合优化领域中的一类重要问题，在计算机系统控制、机器加工制造业、生产计划调度管理等方面有着广泛的实际应用背景。在理论上，它又和算法设计与分析、计算复杂性理论密切相关。在经典排序理论中，根据在确定排序时了解的工件信息的多少，常将排序问题分为“在线”和“离线”两种。在在线问题中，工件一个个地到达，每个工件只有在到达后才知道它的信     

三台等级机器上带重排的半在线问题

研究了3台机上带2种等级的重排问题,当所有工件都被分配之后,在等级约束下,可以重排一台机器上的最后一个工件,目标是最小化最大完工时间。3台机上带2种等级分为2种情形：第1种是有1台机器的等级为1,另2台机器的等级为2;第2种是2台机器的等级为1,另1台机器的等级为2。针对第1种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为5/3的在线算法;针对第2种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为12/7的在线算法。     

工件加工最优排序算法研究--相对优势递推法

本文对世界上仍在研究的N个工件在M台机器上加工的最优排序的理论及其算法问题,从相对优势递推的观点进行了研究,给出了相应的理论和算法。利用该方法,不仅可以解任意多个工件在任意多台机器上加工的最优排序确定,并计算出最省时的加工工时,其计算机排序工作量要比文中提及的“枚举法排序”少得多。     

并行排序算法的设计与分析

排序作为最基础的算法之一,已广泛应用于许多行业领域中。文章在对并行算法的概念、目标和设计方法的基础上,切实结合并行算法的主要思想,给出了并行算法的具体设计。     

无线网络中的在线信道分配问题

研究一个无线网络中信道分配的最大化问题.对该问题的离线版本给出了一个O(n2)时间的算法.对在线问题的一般情况,证明了k-look-ahead算法的下界至少为(k 2)*/(k 1);还给出了一个竞争比为2的1-look-ahead算法.     

差异工件并行批调度问题中遗传算法研究

本文考虑了遗传算法在包含差异工件的并行批处理机调度中的应用问题.工件具有不同的尺寸和到达时间.首先基于问题假设提出了一个数学规划模型,并采用BF、ERT-LPT实现工件的分批排序调度.然后考虑到这是一个NP-Hard问题,设计了新的选择、交叉、变异操作并结合遗传算法进行求解.最后通过仿真实验对比,验证了算法的有效性.     

一种新的并行归并排序算法

文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。     

多台机器下的最小期望延误的随机排序问题

论文针对多台机器下,任务的预期时间为随机变量的排序问题,首先用LPT排序方法把任务安排到不同的机器上,然后用简单的随机方法来确定任务在机器上的特殊加工次序。由于随机预期时间是相互独立的并且服从指数分布,考虑将参数进行最大延误。     

工件从大到小到达的带处理器费用的半在线调度算法

对大多数调度问题来说,处理器集往往是事先给定的,而且在算法进行过程中,它是不变的.Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型.他们研究了所谓的ListModel问题,给出了竞争比为1.618的在线算法,同时证明了任意在线算法的竞争比至少是4/3.该文研究List Model问题的一个半在线情形,即假设工件是从大到小到达的,给出一个竞争比为3/2的半在线算法.同时证明对该问题的这一半在线情形,任意半在线算法的竞争比至少是4/3.     

单台和多台机器可解的误工排序问题

本文讨论带有子集约束的单台和多台机器使误工工件个数为最少的排序问题，提出两个多项式算法求其最优解。     

复合并行机排序问题的启发式算法研究

为有效解决复合并行机排序的极小化最大完成时间问题,提出了分支定界算法和改进的启发式动态规划算法。利用分支定界算法的3个工具:分支模型、边界和优先规则,构建出分支搜索树。按优先规则进行定界搜索,从而减小了问题求解规模。将原始作业转换为虚拟作业,根据Johnson法则,求解出原问题的最优排序。改进的动态规划算法复杂度分析和计算实验表明,这两个算法可靠性高并且可以解决实际问题。     

并行拓扑排序算法PTSA的设计与实现

文章对AOV网首次提出了一种基于层次的混合数据结构,按分层处理的方法实现并行拓扑排序算法PTSA,求得了AOV网中顶点的所有拓扑序列,克服了以往基于栈结构只能求得一种拓扑序列的缺陷。PTSA算法为工程中各子工程的串行或并行安排提供了确定的选择,提升了拓扑排序算法的实用价值。     

带两个服务等级的3台机半在线算法

This paper studies a semi-online hierarchical scheduling problem on three identical machines. In the problem, there is only one machine with hierarchy 1 and two machines with hierarchy 2, and the goal is to minimize the makespan. When the total size of low-hierarchy is known, an online algorithm with the competitive ratio of 5/3 and the lower bound of 3/2 is given. When the total size of high-hierarchy is known, an online algorithm with the competitive ratio of 9/5 and the lower bound of 3/2 is given. When the total size of each hierarchy is known, an online algorithm with the competitive ratio of 3/2 and the lower bound of 4/3 is given. When the total size of jobs is known, a best possible online algorithm with the competitive ratio of 3/2 is given.     

空间众包环境下的3类对象在线任务分配

随着移动互联网技术与O2O（offline-to-online）商业模式的发展,各类空间众包平台变得日益流行,如滴滴出行、百度外卖等空间众包平台更与人们日常生活密不可分.在空间众包研究中,任务分配问题更是其核心问题之一,该问题旨在研究如何将实时出现的空间众包任务分配给适宜的众包工人.但大部分现有研究所基于的假设过强,存在两类不足:（1）现有工作通常假设基于静态场景,即全部众包任务和众包工人的时空信息在任务分配前已完整获知.但众包任务与众包工人在实际应用中动态出现,且需实时地对其进行任务分配,因此现存研究结果在实际应用中缺乏可行性;（2）现有研究均假设仅有两类众包参与对象,即众包任务与众包工人,而忽略了第三方众包工作地点对任务分配的影响.综上所述,为弥补上述不足,本文提出了一类新型动态任务分配问题,即空间众包环境下的三类对象在线任务分配.该问题不但囊括了任务分配中的三类研究对象,即众包任务、众包工人和众包工作地点,而且关注动态环境.本文进而设计了随机阈值算法,并给出了该算法在最差情况下的竞争比分析.特别的是,本文还采用在线学习方法进一步优化了随机阈值算法,提出自适应随机阈值算法,并证明该优化策略可逼近随机阈值算法使用不同阈值所能达到的最佳效果.最终,本文通过在真实数据集和具有不同分布人造数据集上进行的大量实验验证了算法的效果与性能.     

最小化误工工件个数的两代理单机排序问题

针对研究了两代理情形下的单机排序问题,考虑两类问题：一是在误工工件个数不超过一个给定值的情况下使得总误工最小,另一个是代理[A]的工件加工时间和权重满足反一致关系时,在误工工件个数不超过一个给定值的情况下使得总加权完工时间之和最小。对于这两类问题采用动态规划方法分别给出最优性质和相应的拟多项式时间算法。     

基于链表的m*n不同顺序工件排序算法的研究

在单件、多品种、小批量机械制造业的生产计划编制中,m*n不同顺序工件排序问题(也称Job-Shop调度问题)是一个重要的问题。对m*n不同顺序工件排序算法的研究不仅是对排序理论的一个补充,而且对于解决单件、多品种、小批量机械制造业的现代化管理也会起到积极的推动作用和影响。本文提出了一种基于链表的求解m*n不同顺序工件排序问题的算法,经分析及实验验证,利用这种算法求解m*n不同顺序工件排序问题可得到十分满意的结果。     

软计算求解并行多机成组工件提前/拖期惩罚调度问题

1　问题描述成组工件提前 /拖期惩罚调度在实际生产中普遍存在、急待解决又十分复杂 .目前在国内外相关杂志上 ,还未见报道能够有效解决实际规模问题的方法 ,本文提出了软计算方法( SC) ,实验结果证明了它可以有效地解决大规模实际问题 .N个工件 ( b组 ,每组 ni个工件 ) ,M台机