Search

As the number of deliveries continues to increase, last-mile transport causes rising congestion rates and pollution in urban environments. Integrating last-mile deliveries with existing public transport infrastructure, e.g., metros or trams, can make them more sustainable. This integration can implement in a shared infrastructure mode, where passenger and cargo vehicles share the same rail network, or a shared vehicle mode, where vehicles simultaneously transport cargo and passengers. Evaluating the resulting systems entails modelling several interlinking planning problems. This work presents a component-based simulation to evaluate design decisions for shared passenger and freight transport on fixed infrastructure. We introduce a linear mixed-integer program for optimising the train schedule and the allocation of cargo with a lexicographical objective function that prioritises passenger transport while minimising cargo delivery delay. We analyse the interplay of operational modes, scheduling solutions, and settings in a computational simulation study. The results show that a well-planned train schedule can significantly contribute to service quality. Furthermore, a system with shared vehicles is more robust towards changes in demand whereas a system with only shared an infrastructure is a valid option if we consider a high or unlimited dwell time for cargo vehicles.

Next generation Radio Access Networks (RANs) consider virtualized architectures in which base station functions are distributed in different logical nodes, connected through fronthaul (FH) links. To reduce the FH deployment costs and the required FH capacity, operators may install a single FH link shared among multiple cells and exploit key enabling techniques, such as modulation compression, to reduce FH data. In shared FH capacity scenarios, it is essential to provide efficient methods to control and optimize the FH resources' utilization with limited impact on the air interface performance. In this paper, a multi-cell multi-user scenario with a shared FH link across multiple cells is considered. We focus on optimizing the resource allocation and modulation compression of each user, in a centralized and dynamic manner, aiming to maximize the air interface performance subject to a shared FH capacity constraint. The problem is formulated as a convex optimization problem, which allows deriving the optimal resource allocation and modulation compression per user. Then, we evaluate the proposed FH-aware scheduling methods against baseline holistic strategies over an end-to-end dynamic 5G NR system-level simulator based on ns-3. Under a tight available FH capacity, results show gains that vary from 16% to 567% in different percentile statistics of the user-perceived throughput.

In satellite-terrestrial integrated networks, it is a common practice to schedule real-time tasks from low Earth orbit (LEO) satellites to ground stations (GSs) for data processing. However, the joint task scheduling and resource allocation under unknown environment dynamics (e.g., transmission latency) remains to be a challenging problem. First, the tradeoff between task latencies and energy consumption should be carefully considered when making decisions to minimize task latencies under time-averaged energy consumption constraints. Second, to learn the environment uncertainties and minimize the system performance loss (i.e., regret) in terms of task latencies, both online feedback and offline history should be leveraged efficiently, and the accompanying exploration-exploitation tradeoff should be dealt with in a proper way. In this paper, we formulate the joint task scheduling and resource allocation problem as a constrained combinatorial multi-armed bandit (CMAB) problem. To solve the problem, by integrating online learning, online control, and offline historical information, we propose a Task scheduling and Resource allocation scheme with Data-driven Bandit Learning called TRDBL. Our theoretical and numerical results show that TRDBL achieves a sublinear time-averaged regret while satisfying the time-averaged energy consumption constraints.

The cloud-assisted mobile edge computing system is a critical architecture to process computation-intensive and delay-sensitive mobile applications in close proximity to mobile users with high resource efficiency. Due to the heterogenous dynamics of task arrivals at edge nodes and the distributed nature of the system, the workloads of edge nodes are prone to be unbalanced, which can cause high task response time and resource cost. This paper solves the dynamic task scheduling problem in cloud-assisted mobile edge computing (including both peer task scheduling among edge nodes and cross-layer task scheduling from edge nodes to the cloud), aiming at minimizing average task response time within resource budget limit. To overcome the challenges of task arrival dynamics, edge node heterogeneity, and computation-communication delay tradeoff, we propose a Water-filling Based Dynamic Task Scheduling (WiDaS) algorithm. WiDaS dynamically tunes the usage of cloud resources based on the Lyapunov optimization method and efficiently schedules mobile tasks among edge nodes (and the cloud) by exploiting the idea of water filling. Extensive simulations are conducted to evaluate WiDaS under a trace-driven traffic pattern and two mathematic traffic patterns. The results demonstrate that WiDaS shows two-fold benefits of efficiency and effectiveness.

This article studies two sensors scheduling with a shared memory channel for remote state estimation in cyber-physical systems (CPSs). We consider that each sensor monitors a plant and sends its local estimate to the remote estimator over a shared memory communication channel, of which the packet reception results between two successive time instants are correlated. This article focuses on how the two sensors are scheduled to minimize the total estimation errors at the remote side. The problem is formulated as the Markov decision process (MDP) and the optimal policy is derived. Moreover, the threshold structure of the optimal policy is given to reduce computation overhead. After proving the Whittle indexability of the overall system under a given condition, the Whittle index policy is adopted to further reduce the computation overhead. Numerical simulations are given to illustrate the theoretical results.

Unmanned Aerial Vehicles (UAVs) have been utilized to serve on-ground users with various services, e.g., computing, communication and caching, due to their mobility and flexibility. The main focus of many recent studies on UAVs is to deploy a set of homogeneous UAVs with identical capabilities controlled by one UAV owner/company to provide services. However, little attention has been paid to the issue of how to enable different UAV owners to provide services with differentiated service capabilities in a shared area. To address this issue, we propose a multi-agent imitation learning enabled UAV deployment approach to maximize both profits of UAV owners and utilities of on-ground users. Specially, a Markov game is formulated among UAV owners and we prove that a Nash equilibrium exists based on the full knowledge of the system. For online scheduling with incomplete information, we design agent policies by imitating the behaviors of corresponding experts. A novel neural network model, integrating convolutional neural networks, generative adversarial networks and a gradient-based policy, can be trained and executed in a fully decentralized manner with a guaranteed -Nash equilibrium. Performance results show that our algorithm has significant superiority on average profits, utilities and execution time compared with other representative algorithms.

The job-shop scheduling problem (JSSP) is a challenging scheduling and optimization problem in the industry and engineering, which relates to the work efficiency and operational costs of factories. The completion time of all jobs is the most commonly considered optimization objective in the existing work. However, factories focus on both time and cost objectives, including completion time, total tardiness, advance time, production cost, and machine loss. Therefore, this article first time proposes a many-objective JSSP that considers all these five objectives to make the model more practical to reflect the various demands of factories. To optimize these five objectives simultaneously, a novel multiple populations for multiple objectives (MPMO) framework-based genetic algorithm (GA) approach, called MPMOGA, is proposed. First, MPMOGA employs five populations to optimize the five objectives, respectively. Second, to avoid each population only focusing on its corresponding single objective, an archive sharing technique (AST) is proposed to store the elite solutions collected from the five populations so that the populations can obtain optimization information about the other objectives from the archive. This way, MPMOGA can approximate different parts of the entire Pareto front (PF). Third, an archive update strategy (AUS) is proposed to further improve the quality of the solutions in the archive. The test instances in the widely used test sets are adopted to evaluate the performance of MPMOGA. The experimental results show that MPMOGA outperforms the compared state-of-the-art algorithms on most of the test instances.

This paper investigates an Unmanned Aerial Vehicle (UAV)-enabled network consisting of smart mobile devices and multiple UAVs as aerial base stations in a Multiple-Input Multiple-Output (MIMO) architecture. Mobile devices are partitioned into several clusters and offload their tasks to UAV servers via the Non-Orthogonal Multiple Access (NOMA) protocol. We aim to jointly maximize the number of served IMDs, the user scheduling, the number of UAVs, and their $3$ D placement. To this end, we formulate an optimization problem subject to some Quality of Service (QoS) constraints. Due to its non-convexity, we break the problem into two subproblems. We propose a machine-learning-based algorithm for the first subproblem, i.e., optimizing the UAVs' number and $3$ D placements, and the user association. Unlike existing literature, our algorithm achieves low computational complexity and fast convergence. The second subproblem, the user scheduling, is non-convex too. We utilize the $\ell_p$ -norm concept and optimize the user scheduling by applying the Successive Convex Approximation (SCA) algorithm. The aforementioned process is performed iteratively until convergence, and a near-optimal solution is achieved. Moreover, the computational complexity of the proposed scheme is analyzed. Regarding fast convergence and low computational complexity of the proposed algorithm, we confirm its superior performance through simulation results.

Edge computing can provide high bandwidth and low-latency service for big data tasks by leveraging the edge side’s computing, storage, and network resources. With the development of microservice and docker technology, service providers can flexibly and dynamically cache microservice at the edge side to respond efficiently with limited resources. Automatically caching needed services on the nearest edge nodes and dynamically scheduling users’ requests can realize that computing power and software services flow with the users to provide continuous services. However, achieving the goal needs to overcome many challenges, such as the significant fluctuation of user devices’ requests at the edge side and the lack of collaboration among edge nodes. In this paper, dynamic computing power scheduling and collaborative task scheduling among edge nodes are comprehensively developed. The problem is considered a multi-objective optimization problem, including sequentially minimizing the deadline missing rate of requests and the average task completion time. We propose an adaptive mechanism for dynamically collaborative computing power and task scheduling (ADCS) in the edge environment to solve this problem. It adopts the greedy decision method to schedule computing tasks to meet their deadline requirements. At the same time, it uses the best-fit method to adjust the computing resources according to the changes of users’ requests. The simulation results show that ADCS can decrease the deadline missing rate and reduce the average completion time. Compared with DSR and CoDSR, the deadline missing rate is reduced by 59.91% and 19.95%, respectively. The average completion time is decreased by 37.87%, 6.71%.

Energy storage systems (ESSs)-based demand response (DR) is an appealing way to save electricity bills for consumers under demand charge and time-of-use (TOU) price. In order to counteract the high investment cost of ESS, a novel operator-enabled ESS sharing scheme, namely, the ``operator-as-a-consumer (OaaC),'' is proposed and investigated in this article. In this scheme, the users and the operator form a Stackelberg game. The users send ESS orders to the operator and apply their own ESS dispatching strategies for their own purposes. Meanwhile, the operator maximizes its profit through optimal ESS sizing and scheduling, as well as pricing for the users' ESS orders. The feasibility and economic performance of OaaC are further analyzed by solving a bilevel joint optimization problem of ESS pricing, sizing, and scheduling. To make the analysis tractable, the bilevel model is first transformed into its single-level mathematical program with equilibrium constraints (MPEC) formulation and is then linearized into a mixed-integer linear programming (MILP) problem using multiple linearization methods. Case studies with actual data are utilized to demonstrate the profitability for the operator and simultaneously the ability of bill saving for the users under the proposed OaaC scheme.

Container technology plays an important role in the virtualization landscape today. A container uses its own file system consisting of a stack of layers, which are stored on the execution server's disk. Containers running on the same server share the layers they have in common, and this sharing results in valuable savings in server storage space. Many containers can run on a single server, but when their resource demands grow enough, they are distributed across a cluster of nodes/servers by orchestration systems, such as Kubernetes. In this work, we found that for the same amount of containers to run, the storage required is higher for clusters consisting of a larger number of nodes. The severity of this storage overhead depends on the scheduling policy used to select the nodes that run the containers. By comparing different storage-saving scheduling policies that differ from each other in the depth of storage knowledge they leverage to make decisions, our analysis reveals that only deep, layer-level knowledge can effectively counter the growth in storage demand as the cluster size increases. Policies with coarser-grained knowledge achieve limited benefit because they achieve performance that is nearly equal to that of a random, zero-knowledge policy.

Workflow scheduling in cloud environments has become a significant topic in both commercial and industrial applications. However, it is still an extraordinarily challenge to generate effective and economical scheduling schemes under the deadline constraint especially for the large scale workflow applications. To address the issue, this paper investigates the cloud workflow scheduling problem with the aim of minimizing the whole cost of workflow execution whereas maintaining its execution time under a predetermined deadline. A novel knowledge-based adaptive discrete water wave optimization (KADWWO) algorithm is developed based on the problem-specific knowledge of cloud workflow scheduling. In the proposed KADWWO, a discrete propagation operator is designed based on the idle time knowledge of hourly-based cost model to adaptively explore the huge search space. The adaptive refraction operator is employed to avoid stagnation and expand the available resource pool. Meanwhile, the dynamic grouping based breaking operator is designed to exploit the excellent block structure knowledge of task allocation scheme and corresponding resource to intensify the local region and accelerate convergence. Extensive simulation experiments on the well-known scientific workflow demonstrate that the KADWWO approach outperforms several recent state-of-the-art algorithms.

In this paper, the problem of temporal isolation among containerized software components running in shared cloud infrastructures is tackled, proposing an approach based on hierarchical real-time CPU scheduling. This allows for reserving a precise share of the available computing power for each container deployed in a multi-core server, so to provide it with a stable performance, independently from the load of other co-located containers. The proposed technique enables the use of reliable modeling techniques for end-to-end service chains that are effective in controlling the application-level performance. An implementation of the technique within the well-known OpenStack cloud orchestration software is presented, focusing on a use-case framed in the context of network function virtualization. The modified OpenStack is capable of leveraging the special real-time scheduling features made available in the underlying Linux operating system through a patch to the in-kernel process scheduler. The effectiveness of the technique is validated by gathering performance data from two applications running in a real test-bed with the mentioned modifications to OpenStack and the Linux kernel. A performance model is developed that tightly models the application behavior under a variety of conditions. Extensive experimentation shows that the proposed mechanism is successful in guaranteeing isolation of individual containerized activities on the platform.

BCube is a well-known recursively defined network structure. It provides multiple low-diameter paths and good fault-tolerance for data center networks (DCNs). Its distributed routing algorithm, BCube Source Routing (BSR), can be deployed rapidly and conveniently to build multiple parallel path sets. But in the worst case, BSR may suffer from flow collisions and waste $50\%$ of the capacity of each BCube link. In this paper, to fully use those redundant links and to improve BCube load balancing, we supplement the BCube topology with a central master computer and we design two centralized dynamic parallel flow scheduling algorithms: CDPFS and CDPFSMP, for single-path and multi-path respectively. We focus on finding the least congested path for each flow by analyzing the information about the state of the global network. Furthermore, we allocate those paths to each flow in parallel. The simulation result shows that our proposed algorithms take advantage of BCube structure and deliver high-performance solutions for load balancing problems.

As the backbone of Industry 4.0, industrial cyber-physical systems (ICPSs) that are geographically dispersed, federated, cooperative, and security-critical systems become the center of interest from both industry and academia. In ICPS, there are huge amounts of devices, such as sensors and actuators, which are embedded and networked together to improve the performance of real-time monitoring and control. Reliability and temperature are two important concerns of these embedded and networked devices in ICPS due to their stringent requirement of reliable execution and long lifespan. In this article, we study the problem of maximizing soft-error reliability of CPU- and GPU-integrated embedded platforms deployed in ICPS under the temperature constraint. To speed up the estimation of soft-error rate (SER) and temperature, we train an artificial neural network (ANN) that is able to quickly and accurately derive the system's SER and temperature. To solve the temperature-constrained reliability optimization problem, we propose a feedback control-based task scheduling scheme that adaptively determines the number of tasks admitted in the system and the number of replicas for the admitted tasks. We perform a series of simulation experiments to verify the efficacy of our scheme. The experimental results demonstrate that: 1) the estimated SER and temperature derived by our ANN-based method are very close to the ground-truth data and 2) our proposed feedback control-based task scheduling method can improve system reliability by up to 184.2% with a lower peak temperature when compared with one baseline and two state-of-the-art methods.

Mobile edge computing (MEC), extending computing services from cloud to edge, is recognized as one of key pillars to facilitate real-time services and tackle backhaul bottleneck. However, it is not economically efficient to attach intensive security appliances to every MEC node to defend application-level DDoS attacks and ensure the availability of services. Thus, we explore the elasticity of security defense among MEC nodes by proposing a COoperative DEfense (CODE) framework for MEC, referred to as CODE4MEC. CODE4MEC aims to adapt to traffic changes by coordinating container-carried defensive resources among cooperative MEC nodes in an automatic way. Towards this aim, we propose four control plane functions to enable a life-cycle management for CODE4MEC, namely, CODE triggering, scheduling, coordination and releasing. However, an effective CODE4MEC requires non-trivial algorithmic schemes, in particular for CODE scheduling and coordination functions. We thus design an online combinatorial auction mechanism for real-time CODE scheduling, and prove a tighter performance bound relative to prior arts. As for CODE coordination, a flow-based traffic and context information coordination scheme is proposed to enable classical defense schemes to work properly and efficiently. Finally, using a combination of real testbed and simulation evaluations, we validate the effectiveness of CODE4MEC.

Due to the excessive concentration of computing resources in the traditional centralized cloud service system, there will be three prominent problems of management confusion, construction cost and network delay. Therefore, we propose to virtualize regional edge computing resources in intelligent buildings as edge service pooling, then presents a hierarchical cloud platform with dual-service pooling structure and a dynamic strategy for the proposed model. The analytic hierarchy process (AHP) based quality of service (QoS) evaluation mechanism and the dynamic normal distribution selection method are adopted for service deployment. And the dynamic inertia particle swarm optimization (DI-PSO) algorithm is employed to realize task scheduling. Furthermore, the cloud platform and existing terminal server group are used to conduct platform structure comparison experiments, and the popular task scheduling algorithms are selected for simulation experiments. Experimental results of platform measurement show that the average service response time of different services can be improved by about 17.3% to 37.4%. The average occupancy ratio of computing resources can be reduced by about 5%. The simulation results show that the earliest completion time of single task list can be decreased by 11.3% to 20.9%, and the makespan of 100 task lists can be improved by 0.3 times.

Generally the accelerators type identifies the edge computing performance hugely and it includes Integrated Circuit (IC), Graphical Processing Unit (GPU) and Field Programmable Gate Array (FPGA). Among these accelerator FPGAs are widely used in several edge computing areas since it has the ability to reconfigure and has high energy efficient. The consequence also comes out with the paradigm of scheduling efficiency on CPU’s (software tasks) and FPGA (hardware tasks). However the conventional schemes not entirely exploited the variations among hardware and software tasks which results in low scheduling efficiency. Therefore a task scheduling system is proposed on basis of fully active reconfigurable system. The scheduling efficiency for the proposed scheme can be increased by switching the task overheads and by predicting the execution time for hardware with minimum task switching times.

Mobile Edge Computing (MEC), which is the main technology behind 5th Generation (5G) networks, is a nascent paradigm that meets the demands of IoT (Internet of Things) and localized computing. From an end-user point of view, it can be regarded as a refinement of cloud computing and Fog computing. The transfer of computational tasks to the closet MEC servers leads to energy efficiency and low latency. It is important to apply the most suitable policies for scheduling, especially when configuring different modules of an IoT application in MEC. In this paper, three algorithms, namely the heuristic Bald Eagle Search Optimisation [BESO] algorithm, Particle Swarm Optimization algorithm [PSO], and Genetic Algorithm [GA], are presented to carry out heuristic offloading of computational tasks with a view to improving the latency and performance of MEC. However, the most effective algorithm must be adopted to conduct these tasks. As a result, this paper attempts to find an algorithm that is most appropriate for MEC. To demonstrate this. the three algorithms were tested in the Long-Term Evolution [LTE] based Orthogonal frequency-division multiplexing [OFDM] network during a period when the edge nodes had no adequate resources. The performance and efficiency of the three algorithms, BESO, PSO and GA, were determined and compared. After generating the results, the comparative results were evaluated. In terms of offloading the computational tasks, the BESO algorithm was discovered to perform better, with greater energy efficiency and lower latency, than the other two algorithms.

Downlink mobile edge computing (MEC) networks are required to serve increasing large number of Internet of Things (IoT) devices with limited battery capacity. In order to serve massive user equipments with low power consumption requirements, in this paper, we propose an energy-efficient multi-carrier non-orthogonal multiple access (MC-NOMA) design which allows more than two IoT devices to multiplex and access the same subcarrier band. With the aim to minimize the total transmit energy while meeting the demands of each IoT device such as the low latency, in our design, we firstly derive the optimal successive interference cancellation (SIC) policy and minimum power allocated to every IoT device. Then we propose an optimal greedy algorithm to allocate the frequency blocks, and formulate the optimization of the computational resource allocation as a min-max problem. Subsequently, we characterize the MC-NOMA network with the potential game model, and present a scheduling scheme to manage massive IoT devices. Simulation results demonstrate that our proposed scheme can consume 3-10 dB less energy in a MEC network deployed with 256 IoT devices compared with the conventional orthogonal multiple access (OMA) scheme and non-orthogonal multiple access (NOMA) scheme.

This article considers the problem of cyclic flow shop (CFS) scheduling problems in robotic cells deploying several single and dual gripper robots. In this problem, different part types are successively processed on multiple machines with different pickup criteria including free pickup, pickup within time windows, and no-waiting times. The parts are transported between the machines by the robots. We propose a novel integer programming approach that determines the optimal sequence of parts simultaneously for the sequencing of the robots’ movements and the cyclic schedule, which also results in maximizing the throughput rate. The proposed mathematical model is validated on a number of randomly generated test instances. These problem instances are constructed by varying the number of machines, part types, robots, and gripper options. This allows a detailed analysis of the model including how it scales with increasing numbers of machines, part types, robots, and grippers. An experimental evaluation shows that our proposed model is very effective for a range of small medium-sized problems. In particular, we find that differing number of robots and gripper options directly affects the cycle time and in turn, the throughput rate. Overall, our integer programming model finds good feasible solutions for up to 20 machines and 10 part types, which is comparable to real-world industrial problems.

Millimeter wave (mmWave) wireless networks are envisioned to bring a very high degree of spatial reuse, i.e., multiple links can operate simultaneously without interference. The vision, however, is becoming doubtful, as recent studies found that non-negligible interference exists due to imperfect beam patterns. In this paper, we extensively measure the spatial reuse issue in a dense 60 GHz mmWave network consisting of multiple access points (AP) and users. Our measurement quantifies the impact of interference on network performance and finds that the existing prediction based on interference-resolving approaches are insufficient. Motivated by the findings, we propose MDSR, which enhances the spatial reuse in 60 GHz mmWave networks. Instead of relying on interference prediction, MDSR takes a new measurement principle of building a conflict graph that implicitly takes into account the impact of both beam imperfection and reflections. Using the conflict graph, MDSR improves the spatial reuse from three dimensions: AP association, user scheduling, and beam selection, which can determine the optimal AP-user-beam combination and minimize interference in each scheduling cycle. We prototype and evaluate MDSR on the testbed using commodity mmWave radios. The evaluation results demonstrate that MDSR improves network throughput by multi-folds compared with the state-of-the-art one.

Broadcasting is an essential operation for the source node to disseminate the message to all other nodes in the network. Unfortunately, the problem of Minimum Latency Broadcast Scheduling (MLBS) in duty-cycled wireless networks is not well studied. In existing works, the construction of broadcast tree and the scheduling of transmissions are conducted separately, which may result in a bad-structured broadcast tree and then a large latency is obtained even using the optimal scheduling method. Thus, the MLBS problem in duty-cycled wireless networks without above limitation is investigated in this paper. Firstly, a two step scheduling algorithm is proposed to construct the broadcast tree and compute a collision-free schedule simultaneously. This is the first work that can integrate these two kinds of operations together. Secondly, a novel transmission mode, i.e., concurrent broadcasting, is first introduced for wireless networks and several techniques are designed to further improve the broadcast latency. Thirdly, through designing some special data structures, the continuous and all-to-all broadcasting algorithms are also proposed, in which all the nodes do not need to wait for any period of time to begin a new transmission. Finally, the theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms.

Network Utility Maximization (NUM) studies the problems of allocating traffic rates to network users in order to maximize the users' total utility subject to network resource constraints. In this paper, we propose a new NUM framework, Learning-NUM, where the users' utility functions are unknown apriori and the utility function values of the traffic rates can be observed only after the corresponding traffic is delivered to the destination, which means that the utility feedback experiences \textit{queueing delay}. The goal is to design a policy that gradually learns the utility functions and makes rate allocation and network scheduling/routing decisions so as to maximize the total utility obtained over a finite time horizon $T$. In addition to unknown utility functions and stochastic constraints, a central challenge of our problem lies in the queueing delay of the observations, which may be unbounded and depends on the decisions of the policy. We first show that the expected total utility obtained by the best dynamic policy is upper bounded by the solution to a static optimization problem. Without the presence of feedback delay, we design an algorithm based on the ideas of gradient estimation and Max-Weight scheduling. To handle the feedback delay, we embed the algorithm in a parallel-instance paradigm to form a policy that achieves $\tilde{O}(T^{3/4})$-regret, i.e., the difference between the expected utility obtained by the best dynamic policy and our policy is in $\tilde{O}(T^{3/4})$. Finally, to demonstrate the practical applicability of the Learning-NUM framework, we apply it to three application scenarios including database query, job scheduling and video streaming. We further conduct simulations on the job scheduling application to evaluate the empirical performance of our policy.

This work investigates the observer-based asynchronous control of discrete-time nonlinear systems with network-induced communication constraints. To avoid the data collisions and side effects in a constrained communication channel, a novel dynamic event-based weighted try-once-discard (DEWTOD) protocol is proposed. In contrast to the existing protocols, the DEWTOD scheduling regulates whether the sampling instant to release and which node to transmit the sampling instant simultaneously. In light of a hidden Markov model, the time-varying detection probability matrix is characterized by a polytopic set. By resorting to the polytopic-structured Lyapunov functional, sufficient conditions are derived such that the closed-loop dynamic is mean-square exponentially stable, and the observer-based controller is designed. In the end, two numerical examples are provided to explicate the validity of the attained methodology.

We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the "classic" adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to the algorithm's reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version and use it as a subroutine to solve the latter., The extended abstract appeared in FOCS 2019. The definitive version was published in JACM '22. V8 is the latest version with all technical changes. Subsequent versions fixes minor LATEX presentation issues

This article proposes a novel and efficient dual-space co-evolutionary memetic algorithm (DCMA) to tackle a practical hybrid differentiation flowshop scheduling problem with limited buffer constraints. In this scheduling problem, jobs are divided into different types and each job consists of multiple parts. The manufacturing of a job involves three stages: 1) parts fabrication on first-stage parallel machines; 2) parts assembly on second-stage single machine; and 3) job differentiation on one of third-stage dedicated machines. Due to the assembly operation and limited buffers between adjacent stages, deadlock and blocking will occur. We formulate the problem and present a deadlock handling policy to guarantee all schedules feasible. Then, we propose the DCMA metaheuristic to approximate the optimal solutions in acceptable time. Global exploration of DCMA is performed by a hybrid of three parts: 1) a continuous optimizer to be executed in continuous search space; 2) a discrete optimizer to be executed in combinatorial solution space; and 3) a meta-Lamarckian learning-based selection mechanism for adaptively determining that which optimizer is more suitable for current global exploration campaign. To balance exploration and exploitation, three problem-special local search strategies are presented, which collaborates with each other and are adaptively started to avoid high computational costs. The effect of parameter setting on DCMA is checked by the Taguchi method of design of experiment. The computational experiments demonstrate the effectiveness of DCMA special designs, and show that DCMA performs better than the existing algorithms for the considered problem.

Different data transmission times, processing times which are difficult to predict and node-dependent access times make MapReduce task scheduling rather complex. In this paper, we consider the problem of scheduling MapReduce tasks to heterogeneous geo-distributed data centers to minimize the total tardiness. A new architecture is constructed to analyze data in the considered scenario. We model distinct data transmission levels, inter- and intra- data centers and heterogeneity of nodes mathematically. An algorithm framework is proposed to schedule MapReduce tasks to heterogeneous nodes in geographically distributed data centers. The proposed algorithm is suitable for both Hadoop MRv1 and MRv2. In terms of the number of idle containers detected in each heartbeat, the same number of tasks are selected from a sorted job sequence. For the map and reduce phases, two measurements are developed with data locality and completion time, respectively, based on which the classical Hungarian algorithm is adopted to optimally assign selected tasks to corresponding idle containers. Components and parameters of the proposal are statistically calibrated over a large set of random instances. A comparison of the proposed algorithm to existing methods for similar problems is carried out. Experimental results demonstrate the proposal is effective for the considered problem.

Problem Definition: Problem Definition: We develop a framework to plan capacity for ambulatory surgery centers (ASCs) typically consisting of three stages. The problem is to determine the capacity in each stage that efficiently covers possible daily patient demand and to coordinate the three stages of patient visits. The objective is to minimize the total cost incurred in satisfying the daily patient demand, where the total cost is defined as the sum of overtime cost and amortized construction cost for the three stages. Academic/Practical Relevance: Timely capacity adjustment is important for ASC practitioners, but related research is limited. We explicitly consider three sequential stages that are typical in ASCs: the pre-operative at holding room (HR), intra-operative at operating room (OR), and post-operative at post-anesthesia care unit (PACU). Such ASCs can be modeled as a hybrid flow shop (HFS) in the scheduling literature. The interdependence of activities and uncertainties in patient-mix as well as their durations pose a significant challenge to manage the capacity of each activity and achieving a smooth patient flow. Methodology: In contrast to the traditional top-down approach to capacity planning, our approach contributes by proposing a bottom-up strategy based on optimization methods combined with analytics that are informed by operational-level archival patient data. Specifically, we use analytics tools to classify patients into groups, which reduces the complexity of the capacity planning problem and improves the model's practicality. Later, we develop several mathematical formulations and heuristics based on scheduling theory to derive the most cost-efficient capacity solution. Results: Given the trade-off between overtime cost and amortized capacity construction cost, this study relaxes the fixed capacity assumption of traditional HFS problems. Because of the computational complexity of the exact HFS model, we develop a heuristic that is straightforward and easy to implement to find cost-efficient capacities for the three stages. Our computational study examines how uncertain business parameters, e.g., patient-mix, service durations, overnight-stay probabilities, affect the capacity planning decision. Managerial implications: This study highlights the benefit of considering multiple stages together in capacity planning, rather than focusing solely on the operating rooms exclusively. We expect our approach to guide the more than 5,000 ASCs in the U.S., performing 23 million surgeries annually, to make appropriate investments that will improve ASC operations via capacity adjustment and patient scheduling.

Mobile edge computing enables resource-limited edge clouds (ECs) in federation to help each other with resource-hungry yet delay-sensitive service requests. Contrary to common practice, we acknowledge that mobile services are heterogeneous and the limited storage resources of ECs allow only a subset of services to be placed at the same time. This paper presents a jointly optimized design of cooperative placement and scheduling framework, named JCPS, that pursues social cost minimization over time while ensuring diverse user demands. Our main contribution is a novel perspective on cost reduction by exploiting the spatial-temporal diversities in workload and resource cost among federated ECs. To build a practical edge cloud federation system, we have to consider two major challenges: user deadline preference and ECs strategic behaviors. We first formulate and solve the problem of spatially strategic optimization without deadline awareness, which is proved NP -hard. By leveraging user deadline tolerance, we develop a Lyapunov-based deadline-driven joint cooperative mechanism under the scenario where the workload and resource information of ECs are known for one-shot global cost minimization. The service priority imposed by deadline urgency drives time-critical placement and scheduling, which, combined with cooperative control, enables workloads migrated across different times and ECs.

Games are energy-intensive applications on mobile devices. Optimizing the energy efficiency of games is hence critical for battery-limited mobile devices. Although the advent of energy-aware scheduling (EAS) integrated in recent devices has provided opportunities for improved energy management, the framework is not specifically tuned for game applications. In this paper, we aim to improve the energy efficiency of game applications running on EAS-enabled mobile devices. To this end, we first analyze the functional characteristics of games, and investigate the source of the energy inefficiency. We then propose a scheme, called System-level Energy-optimization for Game Applications (SEGA), to improve the energy efficiency of games. SEGA governs CPU and GPU power consumption in a tightly coupled manner by employing three key techniques: (1) Gsync-aware GPU DVFS governor, (2) adaptive capacity clamping, and (3) on-demand touch boosting. We implemented SEGA on the latest Android-based smartphones. The evaluation results for 23 popular games showed that SEGA reduced the energy consumption of the Google Pixel 2 XL and Samsung Galaxy S9 Plus smartphones, at the device level, by 6.1-22.3% and 4.0-11.7%, respectively, with a quality of service (QoS) degradation of 1.1% and 0.5%, on average.

Distributed machine learning (DML) is an increasingly important workload. In a DML job, each communication stage can comprise a coflow, and there are dependencies among its coflows. Thus, efficient coflow scheduling becomes critical for DML jobs. However, the majority of existing solutions focus on scheduling single-stage coflows with no dependencies. While there are a few studies schedule dependent coflows of multi-stage jobs, they suffer from either practical or theoretical issues. In this paper, we study how to schedule dependent coflows of multiple DML jobs to minimize the total job completion time (JCT) in a shared cluster. To solve this problem without any prior knowledge of job information, we present an online coflow-aware optimization framework called Parrot. The core idea in Parrot is to infer the job with the shortest remaining processing time (SRPT) each time and dynamically control the inferred job's bandwidth based on how confident it is an SRPT job while being mindful of not starving any other job. We have proved that Parrot algorithm has an approximation ratio of $O(M)$ , where M is the number of jobs. The results from large-scale trace-driven simulations further demonstrate that our Parrot can reduce the total JCT by up to 58.4%, compared to the state-of-the-art solution Aalo.

In Wireless Multimedia Sensor Networks (WMSNs), nodes capable of retrieving video, audio, images, and small scale sensor data, tend to generate immense traffic of various types. The energy-efficient transmission of such a vast amount of heterogeneous multimedia content while simultaneously ensuring the quality of service and optimal energy consumption is indispensable. Therefore, we propose a Power-Efficient Wireless Multimedia of Things (PE-WMoT), a robust and energy-efficient cluster-based mechanism to improve the overall lifetime of WMSNs. In a PE-WMoT, nodes declare themselves Cluster Heads (CHs) based on available resources. Once cluster formation and CH declaration processes are completed, the Sub-Cluster (SC) formation process triggers, in which application base nodes within close vicinity of each other organize themselves under the administration of a Sub-Cluster Head (SCH). The SCH gathers data from member nodes, removes redundancies, and forwards miniaturized data to its respective CH. PE-WMoT adopts a fuzzy-based technique named the analytical hierarchical process, which enables CHs to select an optimal SCH among available SCs. A PE-WMoT also devises a robust scheduling mechanism between CH, SCH, and child nodes to enable collision-free data transmission. Simulation results revealed that a PE-WMoT significantly reduces the number of redundant packet transmissions, improves energy consumption of the network, and effectively increases network throughput.

In modern discrete flexible manufacturing systems, dynamic disturbances frequently occur in real time and each job may contain several special operations in partial-no-wait constraint due to technological requirements. In this regard, a hierarchical multiagent deep reinforcement learning (DRL)-based real-time scheduling method named hierarchical multi-agent proximal policy optimization (HMAPPO) is developed to address the dynamic partial-no-wait multiobjective flexible job shop scheduling problem (DMOFJSP-PNW) with new job insertions and machine breakdowns. The proposed HMAPPO contains three proximal policy optimization (PPO)-based agents operating in different spatiotemporal scales, namely, objective agent, job agent, and machine agent. The objective agent acts as a higher controller periodically determining the temporary objectives to be optimized. The job agent and machine agent are lower actuators, respectively, choosing a job selection rule and machine assignment rule to achieve the temporary objective at each rescheduling point. Five job selection rules and six machine assignment rules are designed to select an uncompleted job and assign the next operation of which together with its successors in no-wait constraint on the corresponding processing machines. A hierarchical PPO-based training algorithm is developed. Extensive numerical experiments have confirmed the effectiveness and superiority of the proposed HMAPPO compared with other well-known dynamic scheduling methods.

In this paper, we first propose a multi-objective task-scheduling optimization problem that minimizes both the makespans and total costs in a fog-cloud environment. Then, we suggest an optimization model based on a Discrete Non-dominated Sorting Genetic Algorithm II (DNSGA-II) to deal with the discrete multi-objective task-scheduling problem and to automatically allocate tasks that should be executed either on fog or cloud nodes. The NSGA-II algorithm is adapted to discretize crossover and mutation evolutionary operators, rather than using continuous operators that require high computational resources and not able to allocate proper computing nodes. In our model, the communications between the fog and cloud tiers are formulated as a multi-objective function to optimize the execution of tasks. The proposed model allocates computing resources that would effectively run on either the fog or cloud nodes. Moreover, it efficiently organizes the distribution of workloads through various computing resources at the fog. Several experiments are conducted to determine the performance of the proposed model compared with a continuous NSGA-II (CNSGA-II) algorithm and four peer mechanisms. The outcomes demonstrate that the model is capable of achieving dynamic task scheduling with minimizing the total execution times (i.e. makespans) and costs in fog-cloud environments

In the single-machine non-clairvoyant scheduling problem, the goal is to minimize the total completion time of jobs whose processing times are unknown a priori. We revisit this well-studied problem and consider the question of how to effectively use (possibly erroneous) predictions of the processing times. We study this question from ground zero by first asking what constitutes a good prediction; we then propose a new measure to gauge prediction quality and design scheduling algorithms with strong guarantees under this measure. Our approach to derive a prediction error measure based on natural desiderata could find applications for other online problems.

The use of industrial wireless networks has been growing continuously and it hasbecome an alternative to wired networks. One of the main elements of an industrial wireless network is the network manager, this component is responsible for tasks related to the network construction and maintenance. This work presents the development of a network manager compatible with the WirelessHART protocol, but also customizable, where it is possible to make modifications in order to carry out studies with this protocol. Case studies are presented where the developed tool was used for studies related to communications scheduling, adaptive channel mapping and fast data collection, thus proving the efficiency of the proposed manager.

Delivering cloud-like computing facilities at the network edge provides computing services with ultra-low-latency access, yielding highly responsive computing services to application requests. The concept of fog computing has emerged as a computing paradigm that adds layers of computing nodes between the edge and the cloud, also known as cloudlets, or fog nodes. Therefore, this paper proposes a component-based service scheduler in a cloud-fog computing infrastructure comprising several layers of fog nodes between the edge and the cloud. The proposed scheduler aims to satisfy the application's latency requirements by deciding which services components should be moved upwards in the fog-cloud hierarchy to alleviate computing workloads at the network edge. One communication-aware policy is introduced for resource allocation to enforce resource access prioritization among applications. We evaluate the proposal using the well-known iFogSim simulator. Our component-based scheduling algorithm can reduce average delays for application services with stricter latency requirements while still reducing the total network usage when applications exchange data between the components. Results have shown that our policy was able to, on average, reduce the overload impact on the network usage by approximately 11% compared to the best allocation policy in the literature while maintaining acceptable delays for latency-sensitive applications.

Reasonable route planning and resource allocation strategy in the airborne radar systems (ARS), can sufficiently utilize the limited resources and promote the multitarget tracking (MTT) performance. However, using separately the route planning and resource optimization method cannot take full advantage of the airborne platform. Considering this issue, we propose a joint online route planning and resource optimization strategy in the ARS to improve the system capability for MTT. First, a kinematic model of the ARS, including the mathematical expression between the radar states and the system control parameters, is introduced, which integrates the route planning to the radar scheduling scheme. Next, the posterior Cramer–Rao lower bound about route planning and resource optimization variables for the tracking targets is derived. Then, a scaled-based utility function is established to quantify the MTT performance. Hereafter, a nonconvex problem is formulated by minimizing the utility function with route and resource constraints, and then a efficient three-stage partition-based solution is proposed. Finally, simulation experiments demonstrate the effectiveness of the proposed algorithm. Furthermore, over the traditional benchmark algorithm, the tracking performance of the proposed approach improves 30.44%.

Task scheduling problem in a cloud computing environment is one of the most important issues in this field. Because task schedulers should be aware of underlying platform heterogeneity, task interdependencies, and virtual machine (VM) variable configurations. An efficient task scheduling algorithm can potentially increase the efficiency of cloud computing, by choosing the appropriate virtual machine to do a specific task-scheduling problem, for dependent tasks on heterogeneous resources which is a well-known NP-Hard problem. To reduce minimum total execution time, makespan, in cloud computing many heuristics were presented in literature but lots of them suffer from low efficiency. In this article, a new task priority strategy and applying task duplication methods are proposed, for solving the task scheduling problem of the dependent tasks in heterogeneous cloud computing systems. The novelty of the current paper is to present a new list scheduling algorithm with a new task priority strategy and applying pertinent task duplication techniques. This paper uses optimistic cost table downward (OCTd) and optimistic cost table upward (OCTu) procedures to prioritize tasks in an efficient ordered list; then, it utilizes Heterogeneous Earliest Finish Time (HEFT)-duplication method for performing task duplication technique which significantly reduces makespan. To validate the proposal, we experimentally analyzed the proposed scheduling algorithm with different scientific workflows such as Molecular, LU-Like, FFT, and Montage datasets. The performance comparison of the novel heuristic scheduling algorithm against other existing approaches proved the superiority of proposed algorithm in terms of makespan, speedup, SLR, and efficiency which are prominent scheduling evaluation metrics.

Coarse-grained reconfigurable architecture (CGRA) is a promising programmable hardware with high power-efficiency and high performance. However, compiling and optimizing loops with irregular branches on CGRAs is a challenge to fulfill the performance potential. Existing predication techniques, such as partial predication (PP) and full predication (FP), conservatively implement software pipeline with a static initiation interval (II) obtained from the maximum graph, and thus only parts of the graph in each loop iteration will be actually executed, resulting in underexploited performance. To exploit more loop-level parallelism for irregular branches, this paper proposes a novel dynamic-II pipeline (DIP) scheme, which realizes a pipeline with variable II by accommodating multiple iterations of short path in one static configuration. Since the DIP scheme is effective to only certain types of branches, this paper designs a hybrid compilation framework integrating other complementary methods, which selects appropriate method for source programs according to a proposed performance evaluation model. Experimental results show that 1) the hybrid compilation framework can effectively extract branch features, correctly choose and implement corresponding branch processing methods within acceptable compile time, 2) as compared to PP and FP, DIP brings a significant total execution time (TET) reduction by 27.21% and 22.04% on average when execution probability of short branch is 50%.

Recently, Age of Information (AoI) has become an important metric to evaluate the freshness of information, and studies on minimizing AoI in wireless networks have drawn extensive attention. In mobile edge networks, the change of critical levels for distinct information is important for users’ decision making, especially when merely partial observations are available. However, existing researches have not addressed that issue yet. To tackle the above challenges, we first establish the system model, in which the information freshness is quantified by the changes of its critical levels. We formulate the Age-of-Critical-Information (AoCI) minimization issue as an optimization problem, with the purpose of minimizing the average relative AoCI of mobile clients to help them make timely decisions. Then, we propose an information-aware heuristic algorithm that can reach optimal performance with full obsevations in an offline manner. For online scheduling, an imitation learning-based scheduling approach is designed to decide update preferences for mobile clients under partial observations, where policies obtained by the above heuristic algorithm are utilized for expert policies. At last, we demonstrate the superiority of our designed algorithm from both theoretical and experimental perspectives.

Many scientific applications can be well modeled as large-scale workflows. Cloud computing has become a suitable platform for hosting and executing them. Workflow scheduling has gained much attention in recent years. However, since cloud service providers must offer services for multiple users with various QoS demands, scheduling multiple applications with different QoS requirements is highly challenging. This work proposes a Multi-swarm Co-evolutionary-based Hybrid Optimization (MCHO) algorithm for multiple-workflow scheduling to minimize total makespan and cost while workflow deadline constraints. First, we design a multi-swarm co-evolutionary mechanism where three swarms are adopted to sufficiently search for various elite solutions. Second, to improving global search and convergence performance, we embed local and global guiding information into the updating process of a Particle Swarm Optimizer, and develop a swarm cooperation technique. Third, we propose a Genetic Algorithm-based elite enhancement strategy to exploit more non-dominated individuals, and apply the Metropolis Acceptance rule of Simulated Annealing to update the local guiding solution for each swarm so as to prevent it from being stuck into a local optimum at an early stage. Extensive experimental results demonstrate that MCHO outperforms the state-of-art scheduling algorithms with better distributed non-dominated solutions.

Reorganizing bus frequencies to cater for actual travel demands can signicantly save the cost of the public transport system. This paper studies the bus frequency optimization problem considering the user satisfaction. Specically, for the rst time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efciently, we rst present an index-based (1 1/e)-approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method for that achieves a (1)(1 1/e) approximation ratio. Then we propose a progressive partition-based greedy method for to further boost the efciency while achieving a (1)(1 1/e) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efciency, effectiveness, and scalability of our methods in addressing FAST and FASTCO.

Todays large-scale parallel workflows are often processed on heterogeneous distributed computing platforms. From an economic perspective, computing resource providers should minimize the cost while offering high service quality. It has become well-organized that energy consumption accounts for a large part of a computing systems total cost, and timeliness and reliability are two important service indicators. This article studies the problem of scheduling a parallel workflow that minimizes the system energy consumption under the constraints of response time and reliability. We first mathematically formulate this problem as a Non-linear Mixed Integer Programming problem. Since this problem is hard to solve directly, we present some highly-efficient heuristic solutions. Specifically, we first develop an algorithm that minimizes the schedule length while meeting reliability requirement, on top of which we propose a processor-merging algorithm and a slack time reclamation algorithm using a dynamic voltage frequency scaling (DVFS) technique to reduce energy consumption. The processor-merging algorithm tries to turn off some energy-inefficient processors such that energy consumption can be minimized. The DVFS technique is applied to scale down the processor frequency at both processor and task levels to reduce energy consumption. Experimental results on two real-life workflows and extensive synthetic parallel workflows demonstrate their effectiveness.