两个带机器准备时间的半在线排序

研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3.     

工件可选择的平行机在线排序

研究了一类平行机在线排序问题,且工件可以选择.用三参数法表示该模型为:Pm|on-line,rj,D|∑,fJ.其中D指机器使用期限,fj为工件Jj的加工利润,目标函数是使得在机器使用期限内所获总利润最大.本文给出了该模型fj=1情形(即工件费用相同)的所有在线g法竞争比的上界1/2,进而给出了两台机器、fj=1且工件序列只含两类工件情形(小工件加工时间为1,大工件加工时间为d≥2)的在线算法(ξ)1,其竞争比为1/2,为最具竞争性的     

体能测试时间安排——数学建模实例详解

利用动态规划方法建立了该校体能测试时间安排的数学模型.首先,对该校的学生和班级以及进行体能测试的机器状况和场地作了详尽、细致、深入的分析,只要合理的安排测试流程,那么当所有的学生测完台阶项目时,其它的四个项目都已完成.为了保证整个测试时间段最少,在安排测试流程时主要考虑台阶机器不停的工作所用时间与所用录入时间最少即可.在此前提下,再考虑尽量让学生的等待时间最短,所以在具体的安排流程时按班级人数分两种情况来讨论.分别给出不同的流程图.同时,笔者对学校以后的体能测试栽所涉及到的机器数、测试场所的人员容量、班级的分组情况也提出了一些建议.     

“合成链”算法与一类链优先约束的单机分批排序问题

讨论问题1| chains,B|Cmax具体可描述为:有m条链,其中一条链上有n个工件,其余的m-1条链上的工件数之和为常数k,且工件的加工时间不限制,目标函数为最大完工时间.我们对该问题B=2的情况进行了深入的探讨,在研究过程中首次提出“合成链“算法,给出了时间复杂性为O(nk)的多项式时间算法.     

具有学习效应且交货期可指派的单机排序问题

探讨了工件具有CON/SLK交货期指派且机器具有与位置有关的学习效应目标为极小化交货期指派费用、无误工工件的提前费用以及误工工件的惩罚费用之和排序问题.所探讨的问题在无误工工件数确定的情况下可以转化为指派问题,由于误工工件数最多有n种可能且指派问题能在O(n3)时间内解决,故排序问题是多项式时间可解的,并给出最优算法;在恶化工件具有CON/SLK交货期指派的基础上同时考虑了机器具有学习效应的排序,并给出了两种问题的多项式时间最优算法.     

基于LBT算法的多用户动态接入Wi-Fi通信系统的性能分析

考虑到快速增长的移动终端给蜂窝网络部署带来的挑战，提出多用户动态接入Wi-Fi频谱的通信框架.该框架结合设备至设备(Device-to-Device, D2D)通信技术，形成协作(Cooperative D2D,C-D2D)网络框架.首先，用户端利用先听后发(listen-before-talk, LBT)算法检测空闲Wi-Fi频谱；然后依据是否存在空闲Wi-Fi频谱，系统动态接入带内C-D2D或带外D2D模式；最后，推导带内C-D2D和带外D2D模式下D2D用户链路和基站与转发用户间链路中断概率的数学解析表达式.性能分析表明，动态接入Wi-Fi频谱能降低链路中断概率.     

带有霸王工件的单机在线分批排序

研究了一个带有霸王工件且允许重启的单机在线分批排序,其目标函数值为求时间表长．对于批容量无限的情况,给出了一个最坏竞争比为2的在线算法．     

关系数据集成中的语义查询处理技术

为解决基于语义的关系数据集成中的查询处理正确性问题,形式化定义了SPARQL查询语句的语义.在查询重写过程中,发现查询相关的数据表并将其分解为最小可连接单元,再根据查询语义连接最小可连接单元来产生正确的查询.给出了基于语义的查询重写和查询转换算法.对算法复杂性进行了讨论,在最坏情况下,查询分解算法可在O(n2)时间内完...     

一类有尺寸大小的在线分批排序问题

研究了工件有尺寸大小的一致性在线分批排序．就所有工件有两个到达时间ri,i=1,2(不妨设r1=0,r2=r)对于0时刻到达的工件中加工时间最大的批满足一定的约束条件下的一致性在线分批排序给出一个在线算法,并证明了算法的竞争比不超过2．357．     

3台平行机上带有2个服务等级的离线负载均衡

排序问题是一类重要的组合最优化问题,在生产计划、计算机控制等领域有着广泛应用,一直是理论界研究热点.对带服务等级的3台平行机排序问题进行研究,每台机器和每个工件都有等级标号,每个工件只能被某台服务等级不高于该工件等级的机器加工,目标是最小化最大机器的完工时间.运用新的算法思想解决离线状态等级约束下的3台机器负载均衡问题...     

JIT方式下的单机分批调度问题的一种算法

在现代生产管理中,合理安排工件的加工顺序使所有的工件准时完工极为重要．文中研究工件不允许拖期的单机分批调度问题,目标是使加工．总成本最小,目标函数不仅考虑了工件提前完工有提前惩罚成本,还考虑了批加工成本费用．提出了一种多项式时间的最优算法．     

Deterministic and randomized scheduling problems under the lp norm on two identical machines

Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p＞1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine's load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.     

工件加工时间退化且可拒的带优势关系流水作业问题的动态规划算法

The permutation flow shop scheduling problems with deteriorating jobs and rejection on dominant machines were studied. The objectives are to minimize the makespan of scheduled jobs plus the total rejection penalty and the total completion time of scheduled jobs plus the total rejection penalty. For each objective, polynomial time algorithms based on dynamic programming were presented.     

关于简单线性恶化问题的平行机排序的一个全多项式逼近算法

In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.     

双操作系统任务调度策略及其改进简

双操作系统是虚拟机运行在主操作系统,然后通过虚拟机来运行从操作系统.从操作系统的任务调度只能等到主操作系统任务调度空闲才能调度.导致不能及时响应高优先级别的任务,系统容易崩溃.因此如果先运行虚拟机,再运行主从操作系统,最后通过虚拟机来调度主从操作系统任务,同时改进双操作系统间的任务调度策略.那么就能保证整个双操作系统任务之间的平滑调度,从而使整个系统稳健可靠运行.     

基于μC/OS-Ⅱ实时系统分层混合调度算法的研究

对于实时混合型任务调度,基于NP问题的分析研究,在分层中采用基于阈值的双优先级调度算法,该算法结合了抢占式与非抢占式调度算法的优点,可以提高任务集的调度成功率,并减少由于任务切换引起的系统开销。对阈值的分配是调度算法的核心。在基本优先级已知的条件下,基于回溯技术的阈值分配算法利用低端任务阈值单向影响高端任务最大响应时间的特性,可以在有限的时间内为任务集找出一组具有极大值特征的阈值。该组阈值可以将任务切换次数降至最低,使各队列能够将任务的分配达到一个利用率很好的程度。     

两个加工时间恶化的半线性平行机排序问题的启发式MBLS 算法

The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered. In the first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, bj ∈[0, α], where 0 〈α≤ 1 and bj denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is known in advance, that is, b = max1≤j≤n {bj }. For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same time, the worst-case ratio of the list （LS） algorithm is investigated and it is proved that all the ratios are tight.     

工件加工排序问题的研究

通过对在给定设备、按规定工序下多种工件加工排序问题的研究,得出了基于最短加工时间规则和优化加工顺序规则基础上的工件加工排序模型。该模型按工件加工时间长短,从短到长顺序排列,同时要求最紧张设备等待时间最小化。在设备等待时间最小化的前提下,优先加工在该设备上加工时间最短的工件,兼顾启发性的搜索方法,使平均流程时间最短。最后通过实例分析证实了该算法的有效性与实用性。     

Deterministic and randomized scheduling problems under the 1p norm on two identical machines

Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problemP2|decr|l _p (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of thel _p norm of every machine's load. It is shown thatLS algorithm is optimal for anyl _p norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problemsP2|online|l _p andP2|decr|l _p are presented. Project supported by the National Natural Science Foundation of China (Nos. 10271110, 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China     

带同类恶化工件机器排序的多用户模型

We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs,i.e.,jobs whose processing times are an increasing function of their starting times.Traditionally,such scenarios are modeled by assuming that each customer has the same criterion.In practice,this assumption may not hold.Instead of using a single criterion,we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria.We examine three basic scheduling criteria:minimizing makespan,minimizing maximum lateness,and minimizing total weighted completion time.We demonstrate all the scheduling problems considered are polynomially solvable.