Online scheduling of jobs with kind release times and deadlines on a single machine

This paper studies online scheduling of jobs with kind release times on a single machine. Here "kind release time" means that in online setting, no jobs can be released when the machine is busy. Each job J has a kind release time r(J) ≥ 0, a processing time p(J) > 0 and a deadline d(J) > 0. The goal is to determine a schedule which maximizes total processing time( p(J)E(J)) or total number( E(J)) of the accepted jobs. For the first objective function p(J)E(J), we first present a lower bound 2(1/2), and then provide an online algorithm LEJ with a competitive ratio of 3. This is the first deterministic algorithm for the problem with a constant competitive ratio. When p(J) ∈ {1, k}, k > 1 is a real number, we first present a lower bound min{(1 + k)/k, 2 k/(1 + k)}, and then we show that LEJ has a competitive ratio of1 + k/k. In particular, when all the k length jobs have tight deadlines, we first present a lower bound max{4/(2 + k), 1}(for p(J)E(J)) and 4/3(for E(J)). Then we prove that LEJ is k/k-competitive for p(J)E(J) and we provide an online algorithm H with a competitive ratio of 2 k/( k + 1) for the second objective function E(J).

Meeting deadlines for approximation processing in MapReduce environments

To provide timely results for big data analytics, it is crucial to satisfy deadline requirements for MapReduce jobs in today＇s production environments. Much effort has been devoted to the problem of meeting deadlines, and typically there exist two kinds of solutions. The first is to allocate appropriate resources to complete the entire job before the specified time limit, where missed deadlines result because of tight deadline constraints or lack of resources; the second is to run a pre-constructed sample based on deadline constraints, which can satisfy the time requirement but fail to maximize the volumes of processed data. In this paper, we propose a deadline-oriented task scheduling approach, named ＇Dart＇, to address the above problem. Given a specified deadline and restricted resources, Dart uses an iterative estimation method, which is based on both historical data and job running status to precisely estimate the real-time job completion time. Based on the estimated time, Dart uses an approach-revise algorithm to make dynamic scheduling decisions for meeting deadlines while maximizing the amount of processed data and mitigating stragglers. Dart also efficiently handles task failures and data skew, protecting its performance from being harmed. We have validated our approach using workloads from OpenCloud and Facebook on a cluster of 64 virtual machines. The results show that Dart can not only effectively meet the deadline but also process near-maximum volumes of data even with tight deadlines and limited resources.

Efficient-Cost Task Offloading Scheme in Fog-Internet of Vehicle Networks

Fog computing became a traditional OffLad Destination(OLD)to compute the offloaded tasks of the Internet of Vehicles(IoV).Nevertheless,the limited computing resources of the fog node leads to re-offload these tasks to the neighboring fog nodes or the cloud.Thus,the IoV will incur additional offloading costs.In this paper,we propose a new offloading scheme by utilizing RoadSide Parked Vehicles(RSPV)as an alternative OLD for IoV.The idle computing resources of the RSPVs can compute large tasks with low offloading costs compared with fog nodes and the cloud.Finally,a performance evaluation of the proposed scheme has been presented and discussed with other benchmark offloading schemes.

面向Deadline约束的网格QoS任务调度

根据调度算法中对QoS的匹配需求,提出了一种基于QoS优先级分组的网格任务调度思想,并且在此基础上引入任务的Deadline约束,综合考虑任务的可接受率以及系统的makespan性能,提出一种面向Dead-line约束的网格任务调度策略QD-Sufferage.实验表明,该算法在makespan、吞吐率等方面的综合性能较以往的算法有较大的提高.

一类带有deadline约束的作业车间提前/拖期调度问题研究

针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。

一种多DAG任务共享异构资源调度的费用优化方法

针对多DAG(Directed Acyclic Graph)共享一组异构资源在调度吞吐量最大化基础上的费用优化问题,本文提出了一种基于总费用变化量探测的费用优化算法PDTC(based on the Probe of the Total Cost Decrease),目的在于尽可能降低有优化条件的多个DAG的总费用.实验表明,该算法不仅能使得各DAG充分利用期限内的冗余时间,也能够在一定程度上降低多个DAG调度执行的总费用.

面向Deadline的云代理资源预留策略

由于传统的代理模式在应对短期用户大量到达高峰和实例利用率上存在优化空间,为节约资源和节省开支,提出了一种新的面向Deadline的云服务代理构想,利用中间件技术整合用户请求和实例资源。分析发现,面向Deadline的云代理能有效平滑需求高峰,并大幅度提高实例利用率。针对用户deadline相同与不同2种模式,分别设计了贪心算法和EDF平移算法,实现了高峰平滑和利用率提升,降低了开支。实验表明,相比于未采用云代理,面向Deadline云服务代理处理大量用户请求时能减少50%以上的费用,具有良好的应用前景。

Long-release-interval-first real-time scheduling algorithm and its schedulability test

To fulfill the requirements for hybrid real-time system scheduling, a long-release-interval-first （LRIF） real-time scheduling algorithm is proposed. The algorithm adopts both the fixed priority and the dynamic priority to assign priorities for tasks. By assigning higher priorities to the aperiodic soft real-time jobs with longer release intervals, it guarantees the executions for periodic hard real-time tasks and further probabilistically guarantees the executions for aperiodic soft real-time tasks. The schedulability test approach for the LRIF algorithm is presented. The implementation issues of the LRIF algorithm are also discussed. Simulation result shows that LRIF obtains better schedulable performance than the maximum urgency first （MUF） algorithm, the earliest deadline first （EDF） algorithm and EDF for hybrid tasks. LRIF has great capability to schedule both periodic hard real-time and aperiodic soft real-time tasks.

多处理器混合关键性系统中的划分调度策略

多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中,其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性,在多处理器平台则更为困难.将目前资源利用率最高的单处理器混合关键性调度算法EY-VD扩展到多处理器平台中.首先,结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF(mixedcriticality partitioned earliest deadline first)划分调度算法.尽管比之前的算法有更好的可调度性能,但传统的划分策略不能有效地平衡不同关键性级别下的负载,故其不完全适用于混合关键性系统.为了克服传统策略的不足,提出了划分调度策略OCOP(one criticality one partition).OCOP允许系统在关键性模式切换时对实时任务集进行重新划分,进而更好地平衡各个处理器在不同关键性模式中的资源利用率.基于OCOP,提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).基于随机生成任务集的仿真实验结果表明,与MC-PEDF和已有的算法相比,MC-MP-EDF能够显著地提高系统的可调度性,尤其是在处理器数量较多的系统中.

Novel radar dwell scheduling algorithm based on pulse interleaving

The problem of scheduling radar dwells in multifunction phased array radar systems is addressed. A novel dwell scheduling algorithm is proposed. The whole scheduling process is based on an online pulse interleaving technique. It takes the system timing and energy constraints into account. In order to adapt the dynamic task load, the algorithm considers both the priorities and deadlines of tasks. The simulation results demonstrate that compared with the conventional adaptive dwell scheduling algorithm, the proposed one can improve the task drop rate and system resource utility effectively.

Is Minimizing Flow Completion Time the Optimal Way in Meeting Flow's Deadline in Datacenter Networks

In modern datacenters, the most common method to solve the network latency problem is to minimize flow completion time during the transmission process. Following the soft real-time nature, the optimization of transport latency is relaxed to meet a flow's deadline in deadline-sensitive services. However, none of existing deadline-sensitive protocols consider deadline as a constraint condition of transmission.They can only simplify the objective of meeting a flow's deadline as a deadline-aware mechanism by assigning a higher priority for tight-deadline constrained flows to finish the transmission as soon as possible, which results in an unsatisfactory effect in the condition of high fan-in degree. It drives us to take a step back and rethink whether minimizing flow completion time is the optimal way in meeting flow's deadline. In this paper, we focus on the design of a soft real-time transport protocol with deadline constraint in datacenters and present a flow-based deadline scheduling scheme for datacenter networks(FBDS).FBDS makes the unilateral deadline-aware flow transmission with priority transform into a compound centralized single-machine deadlinebased flow scheduling decision. In addition, FBDS blocks the flow sets and postpones some flows with extra time until their deadlines to make room for the new arriving flows in order to improve the deadline meeting rate. Our simulation resultson flow completion time and deadline meeting rate reveal the potential of FBDS in terms of a considerable deadline-sensitive transport protocol for deadline-sensitive interactive services.

Optimal bandwidth scheduling of networked control systems (NCSs) in accordance with jitter

Network-induced delay and jitter are key factors causing performance degradation and instability of NCSs (networked control systems). The relationships between the sampling periods of the control loops, network-induced delay and jitter were studied aimed at token-type networks. A jitter-dependent optimal bandwidth scheduling algorithm for NCSs is proposed, which tries to achieve a tradeoff between bandwidth occupancy and system performance. Simulation tests proved the effectiveness of this optimal scheduling algorithm.

Churn-Resilient Task Scheduling in a Tiered IoT Infrastructure

Cloud-as-the-center computing paradigms face multiple challenges in the 5G and Internet of Things scenarios, where the service requests are usually initiated by the end-user devices located at network edge and have rigid time constraints. Therefore, Fog computing, or mobile edge computing, is introduced as a promising solution to the service provision in the tiered IoT infrastructure to compensate the shortage of traditional cloud-only architecture. In this cloud-to-things continuum, several cloudlet or mobile edge server entities are placed at the access network to handle the task offloading and processing problems at the network edge. This raises the resource scheduling problem in this tiered system, which is vital for the promotion of the system efficiency. Therefore, in this paper, a scheduling mechanism for the cloudlets or fog nodes are presented, which takes the mobile tasks’ deadline and resources requirements at the same time while promoting the overall profit of the system. First, the problem at the cloudlet, to which IoT devices offload their tasks, is formulated as a multi-dimensional 0-1 knapsack problem. Second, based on ant colony optimization, a scheduling algorithm is presented which treat this problem as a subset selection problem. Third, to promote the performance of the system in the dynamic environments,a churn-refined algorithm is further put forward. A series of simulation experiments have shown that out proposal outperforms many state-of-the-art algorithms in both profit and guarantee ratio.

卷烟工业物流系统AGV任务调度策略优化

为了解决卷烟工业AGV运输过程中任务堵塞、优先级不可控、空跑、路径欠佳等问题,通过对自动化物流系统AGV调度策略优化,采用任务动态优先级控制、任务捆绑、任务下发数量控制等手段,有效减少了生产断料及等料事件的发生。验证结果表明:采用本调度策略,平均每条AGV任务的响应时间至少缩短40秒,出入库综合效率提高13%,在车间正常生产情况下,AGV减少搬运时间1.5小时左右,取得了良好的实际应用效果。

A novel resource co-allocation model with constraints to budget and deadline in computational grid

To address the issue of resource co-allocation with constraints to budget and deadline in grid environments, a novel co-allocation model based on virtual resource agent was proposed. The model optimized resources deployment and price scheme through a three-side co-allocation mechanism, and applied queuing system to model the work of grid resources for providing quantitative deadline guarantees for grid applications. The validity and solutions of the model were presented theoretically. Extensive simulations were conducted to examine the effectiveness and the performance of the model by comparing with other co-allocation policies in terms of deadline violation rate, resource benefit and resource utilization. Experimental results show that compared with the three typical co-allocation policies, the proposed model can reduce the deadline violation rate to about 3.5% for the grid applications with constraints to budget and deadline. Also, the system benefits can be increased by about 30% compared with the those widely-used co-allocation policies.

Two-stage optimization model for renewing warranty considering warranty deadline

Renewing warranty can provide customers with better service,and thus help manufacturers to gain market opportunities.In engineering practice,the cost for replacement is usually higher than the cost for maintenance,hence manufacturers often face huge challenge to reduce the warranty service cost.With consideration of the warranty deadline,we propose a two-stage optimization model for renewing warranty.In the first stage,a renewing warranty with deadline(RWD)policy is implemented,where the deadline represents the cumulative uptime threshold.When the cumulative uptime exceeds the deadline,the product will be minimally repaired and kept to the residual warranty period.When RWD is expired,the replacement warranty with limited repairs(RWLR)policy is applied.Under the free replacement and pro-rata warranty policy,the corresponding two-stage cost optimization model is established from the manufacturer’s perspective,the aim is to minimize the cost rate and obtain the optimal warranty period.A numerical example is provided to illustrate the validity of the proposed model,and the sensitivity analysis is also carried out.

WORLD NEWS IN BRIEF (January 16-31, 1991)

At 02:30 am Baghdad time on January 17, the U. S. and allied forces carried out 1000 sorties air and 100 ship-launcnea cruise missile strikes, blasting Iraqi targets to free Kuwait from Iraqi occupation. The attack began less than 19 hours after the expiration of the UN-mandated deadline. From the following day to the end of the month, the U.S.-led allied air forces continued massive bombing&against targets in Iraq and occupied Kuwait. From

Priority probability deceleration deadline-aware TCP

In modern data centers, because of the deadline- agnostic congestion control in transmission control protocol （TCP）, many deadline-sensitive flows can not finish before their deadlines. Therefore, providing a higher deadline meeting ratio becomes a critical challenge in the typical online data intensive （OLDI） ap- plications of data center networks （DCNs）. However, a problem named as priority synchronization is found in this paper, which de- creases the deadline meeting ratio badly. To solve this problem, we propose a priority probability deceleration （P2D） deadline-aware TCP. By using the novel probabilistic deceleration, p2D prevents the priority synchronization problem. Simulation results show that P2D increases the deadline meeting ratio by 20% compared with D2TCP.

An Adaptive Genetic Algorithm for Multiprocessor Real-time Task Scheduling

Real-time task scheduling is of primary significance in multiprocessor systems.Meeting deadlines and achieving high system utilization are the two main objectives of task scheduling in such systems.In this paper,we represent those two goals as the minimization of the average response time and the average task laxity.To achieve this,we propose a genetic-based algorithm with problem-specific and efficient genetic operators.Adaptive control parameters are also employed in our work to improve the genetic algorithms' efficiency.The simulation results show that our proposed algorithm outperforms its counterpart considerably by up to 36% and 35% in terms of the average response time and the average task laxity,respectively.