Search

Dirty paper coding (DPC) scheme is the capacity achieving transmission technique in multiuser MIMO downlink channels. As a suboptimal solution to DPC, successive zero-forcing DPC (SZF-DPC) has been proposed recently. The zero-interference constraint in designing the precoding matrices limits the number of supportable users. In this correspondence, we propose three low-complexity suboptimal user scheduling algorithms to exploit the multiuser diversity gain in SZF-DPC as the number of users grows. The first algorithm greedily maximizes the true sum rate. The second algorithm is based on eigenvalues. The third algorithm relies on the diagonal elements of the effective channel matrix since eigenvalues and diagonal entries of a Hermitian matrix have a strong relationship. Simulation results show that the proposed scheduling algorithms can obtain a significant fraction of sum rate of the optimal solution. Furthermore, the performance analysis is provided to prove that the proposed user selection algorithms can achieve the same asymptotic sum rate as that of DPC. [ABSTRACT FROM AUTHOR]

This letter presents two results for multiuser wireless systems employing dirty-paper coding strategies along with greedy scheduling over the broadcast multiple-input multiple-output channel. Specifically, an efficient and suboptimal downlink scheduler is proposed to approximate the maximum sum rate using equal power allocation, and it is shown to approach the maximum sum rate of optimal power allocation for a large number of users under optimal scheduling. The second result demonstrates that the average maximum sum rate can be tightly upper bounded when spatial multiplexing is maximized. [ABSTRACT FROM AUTHOR]

Hundreds of papers on job scheduling for distributed systems are published every year and it becomes increasingly difficult to classify them. Our analysis revealed that half of these papers are barely cited. This paper presents a general taxonomy for scheduling problems and solutions in distributed systems. This taxonomy was used to classify and make publicly available the classification of $109$ scheduling problems and their solutions. These $109$ problems were further clustered into ten groups based on the features of the taxonomy. The proposed taxonomy will facilitate researchers to build on prior art, increase new research visibility, and minimize redundant effort. [ABSTRACT FROM PUBLISHER]

This paper studies simultaneous scheduling of production and material transfer that arises in the semiconductor photolithography area. In particular, the right reticle and right job both need to be present to process the job. Jobs are transferred by a material handling system that employees a fleet of vehicles. Reticles serving as an auxiliary resource are also transferred from one place to another by a different set of vehicles. This intricate scheduling challenge, encompassing jobs, reticles, machines, and two distinct sets of vehicles, is explored here for the first time. The paper introduces a multi-stage methodology that involves relaxation, a constructive heuristic, constraint programming, and a warm-start approach to address this complex problem. [ABSTRACT FROM AUTHOR]

A scheduling problem for parallel batch processing machines (BPMs) with jobs having unequal ready times in semiconductor wafer fabrication facilities (wafer fabs) is studied in this paper. A blended objective function combining the total weighted tardiness (TWT) and the total electricity cost (TEC) under a time-of-use (TOU) tariff is considered. A genetic programming (GP) procedure is designed to automatically discover priority indices for a heuristic scheduling framework. Results of computational experiments are reported that demonstrate that the learned priority indices lead to high-quality schedules in a short amount of computing time. [ABSTRACT FROM AUTHOR]

Urban public transport is a very complex system, and with the development of urbanization, there are many new urban traffic characteristics. Making bus routes and scheduling strategies more efficient, scientific and accurate has a positive impact on the actual operation of public transport. To solve the urban public transport line design problem, this paper describes the implicit law of the characteristics of public transport travel from a deep perspective and analyzes the forms, influencing factors and existing problems of bus dispatching. By establishing a multiobjective public transport dispatching optimization model, starting from bus companies, passengers and government departments, public transportation operating costs comprehensively consider the interests of various parties and finally realize the optimization objective of minimizing fixed costs, fuel costs, carbon emission costs and time window penalty costs. The objective function is set reasonably, and the generation and optimization method of the initial line set in the public transport line design problem is improved; suitable constraint conditions and evaluation indicators are considered. This paper attempts to control the overall length of the bus line on the premise of fully meeting the travel needs of passengers. By solving the multiobjective problem on the same network and comparing different multiobjective optimization algorithms, the effectiveness of the method is evaluated. Additionally, an improved multiobjective adaptive particle swarm optimization (MOAPSO) is proposed, which has the characteristics of faster convergence, higher efficiency and low computational complexity. The simulation experimental results show that the proposed algorithm in this paper can obtain a better Pareto optimal solution set and can effectively solve the multiobjective model. The departure interval conforms to the passenger flow distribution, which can effectively reduce costs and improve the travel service quality of passengers on a large-scale network. [ABSTRACT FROM AUTHOR]

To exploit richer spectrum resources for even better service quality, millimeter wave (mmWave) communication has been considered for high-speed railway (HSR) communication systems. In this paper, we focus on scheduling as many flows as possible while satisfying their QoS requirements. Due to interference, eavesdropping, or other problems, some flows may not be directly transmitted from the track-side BS. In this paper, we propose an UAV-assisted scheduling scheme which utilizes a UAV to serve as relay for such flows. The proposed scheme also utilize two mmWave bands, one for the BS links and the other for the UAV links. The proposed algorithm aims to maximize the number of flows with their QoS requirements satisfied. Simulations demonstrate that the proposed scheme achieves a superior performance on the number of completed flows and the system throughput over two baseline schemes. [ABSTRACT FROM AUTHOR]

Intelligent public transport systems are a key direction for the study of intelligent transportation systems (ITSs), and they perform the following functions: location and tracking, aided navigation, dispatch and command, and dynamic information release; these systems also help travelers determine optimal routes. This paper mainly studies intelligent bus operation optimization by integrating cases and data from business chains, including the optimization of public transport vehicle scheduling according to the characteristics of vehicle scheduling, considers the interests of passengers and public transport companies, and adopts a true-value encoding method with the departure time as the variable goal optimization. In addition, this paper builds a model for the intelligent scheduling problem in public transport based on an enhanced quantum genetic algorithm (EQGA) to find the optimal timetable. This model sets the minimum waiting time cost of passengers and the maximum interests of public transport companies as the goals, restricts the departure interval and two adjacent intervals, and constrains the load factor of passengers. Moreover, based on the analysis of public transport travel characteristics and passenger flow data, this paper evaluates the efficiency of public transport operation, reasonably analyzes the utilization of public transport resources and the travel time of public transport passengers, and thoroughly studies the public transport operation system. This paper selects actual bus line data for empirical analysis, and the empirical results show that the proposed algorithm and model can meet the requirements of many aspects and provides good intelligence, applicability, and optimization. [ABSTRACT FROM AUTHOR]

Real-time systems with strict timing constraints have been widely applied in many fields. The Directed acyclic graph (DAG) task model has been widely studied and applied to model real-time systems with partial parallelism and precedence constraints in each task. Our paper focuses on the worst-case response time (WCRT) analysis of DAG tasks under partitioned scheduling on multiprocessors. We investigate a parallel structure named $Str$ S t r , which helps obtain more accurate analysis results, and propose a new offline scheduling analysis algorithm named reducing repetitive calculation (RRC). Experiments with synthetic workload are conducted to compare the results calculated by RRC and the state-of-the-art, as well as the observed average response time on a real embedded system. Results show that RRC has better performance in terms of analysis accuracy. [ABSTRACT FROM AUTHOR]

An equation in the Appendix of a previous paper (IEEE Trans. Veh. Technol ., vol. 58, no. 7, pp. 3247–3262, Sep. 2009) contains an error, which propagates to a few more equations in the Appendix. This error does not affect the main body of the text or results presented in that paper, apart from a change to one equation. In this correspondence, we correct the error and provide a revised Appendix. [ABSTRACT FROM PUBLISHER]

Interference management is a fundamental issue in device-to-device (D2D) communications whenever the transmitter-and-receiver pairs are located in close proximity and frequencies are fully reused, so active links may severely interfere with each other. This paper devises an optimization strategy named FPLinQ to coordinate the link scheduling decisions among the interfering links, along with power control and beamforming. The key enabler is a novel optimization method called matrix fractional programming (FP) that generalizes previous scalar and vector forms of FP in allowing multiple data streams per link. From a theoretical perspective, this paper provides a deeper understanding of FP by showing a connection to the minorization-maximization (MM) algorithm. From an application perspective, this paper shows that as compared to the existing methods for coordinating scheduling in the D2D network, such as FlashLinQ, ITLinQ, and ITLinQ+, the proposed FPLinQ approach is more general in allowing multiple antennas at both the transmitters and the receivers, and further in allowing arbitrary and multiple possible associations between the devices via matching. Numerical results show that FPLinQ significantly outperforms the previous state-of-the-art in a typical D2D communication environment. [ABSTRACT FROM AUTHOR]

Recent studies on cloud-radio access networks assume either signal-level or scheduling-level coordination. This paper considers a hybrid coordinated scheme as a means to benefit from both policies. Consider the downlink of a multi-cloud radio access network, where each cloud is connected to several base-stations (BSs) via high capacity links and, therefore, allows for joint signal processing within the cloud transmission. Across the multiple clouds, however, only scheduling-level coordination is permitted, as low levels of backhaul communication are feasible. The frame structure of every BS is composed of various time/frequency blocks, called power-zones (PZs), which are maintained at a fixed power level. This paper addresses the problem of maximizing a network-wide utility by associating users to clouds and scheduling them to the PZs, under the practical constraints that each user is scheduled to a single cloud at most, but possibly to many BSs within the cloud, and can be served by one or more distinct PZs within the BSs’ frame. This paper solves the problem using graph theory techniques by constructing the conflict graph. The considered scheduling problem is, then, shown to be equivalent to a maximum-weight independent set problem in the constructed graph, which can be solved using efficient techniques. This paper then proposes solving the problem using both optimal and heuristic algorithms that can be implemented in a distributed fashion across the network. The proposed distributed algorithms rely on the well-chosen structure of the constructed conflict graph utilized to solve the maximum-weight independent set problem. Simulation results suggest that the proposed optimal and heuristic hybrid scheduling strategies provide appreciable gain as compared with the scheduling-level coordinated networks, with a negligible degradation to signal-level coordination. [ABSTRACT FROM PUBLISHER]

Motivated by applications in data center networks, in this paper, we study the problem of scheduling in an input queued switch. While throughput maximizing algorithms in a switch are well-understood, delay analysis was developed only recently. It was recently shown that the well-known MaxWeight algorithm achieves optimal scaling of mean queue lengths in steady state in the heavy-traffic regime, and is within a factor less than 2 of a universal lower bound. However, MaxWeight is not used in practice because of its high time complexity. In this paper, we study several low complexity algorithms and show that their heavy-traffic performance is identical to that of MaxWeight. We first present a negative result that picking a random schedule does not have optimal heavy-traffic scaling of queue lengths even under uniform traffic. We then show that if one picks the best among two matchings or modifies a random matching even a little, using the so-called flip operation, it leads to MaxWeight like heavy-traffic performance under uniform traffic. We then focus on the case of non-uniform traffic and show that a large class of low time complexity algorithms have the same heavy-traffic performance as MaxWeight, as long as it is ensured that a MaxWeight matching is picked often enough. We also briefly discuss the performance of these algorithms in the large scale heavy-traffic regime when the size of the switch increases simultaneously with the load. Finally, we perform empirical study on a new algorithm to compare its performance with some existing algorithms. [ABSTRACT FROM AUTHOR]

Gasoline blending scheduling uses resource allocation and operation sequencing to meet a refinery's production requirements. The presence of nonlinearity, integer constraints, and a large number of decision variables adds complexity to this problem, posing challenges for traditional and evolutionary algorithms. This paper introduces a novel multiobjective optimization approach driven by a diffusion model (named DMO), which is designed specifically for gasoline blending scheduling. To address integer constraints and generate feasible schedules, the diffusion model creates multiple intermediate distributions between Gaussian noise and the feasible domain. Through iterative processes, the solutions transition from Gaussian noise to feasible schedules while optimizing the objectives using the gradient descent method. DMO achieves simultaneous objective optimization and constraint adherence. Comparative tests are conducted to evaluate DMO's performance across various scales. The experimental results demonstrate that DMO surpasses state-of-the-art multiobjective evolutionary algorithms in terms of efficiency when solving gasoline blending scheduling problems. [ABSTRACT FROM AUTHOR]

The optimal scheduling of interfering links in a dense wireless network with full frequency reuse is a challenging task. The traditional method involves first estimating all the interfering channel strengths and then optimizing the scheduling based on the model. This model-based method is, however, resource intensive and computationally hard because channel estimation is expensive in dense networks; furthermore, finding even a locally optimal solution of the resulting optimization problem may be computationally complex. This paper shows that by using a deep learning approach, it is possible to bypass the channel estimation and to schedule links efficiently based solely on the geographic locations of the transmitters and the receivers due to the fact that in many propagation environments, the wireless channel strength is largely a function of the distance-dependent path-loss. This is accomplished by unsupervised training over randomly deployed networks and by using a novel neural network architecture that computes the geographic spatial convolutions of the interfering or interfered neighboring nodes along with subsequent multiple feedback stages to learn the optimum solution. The resulting neural network gives a near-optimal performance for sum-rate maximization and is capable of generalizing to larger deployment areas and to deployments of different link densities. Moreover, to provide fairness, this paper proposes a novel scheduling approach that utilizes the sum-rate optimal scheduling algorithm over judiciously chosen subsets of links for maximizing a proportional fairness objective over the network. The proposed approach shows highly competitive and generalizable network utility maximization results. [ABSTRACT FROM AUTHOR]

In embedded real-time virtualized systems (ERTVS), the ARINC 653 standard specifies a cyclic scheduling policy to guarantee the real-time performance of tasks in multiple Virtual Machines (VMs) residing on shared hardware. Based on this policy, the Regularity-based Resource Partitioning (RRP) model defines an efficient interface specification to hierarchically partition and assign resource slices among VMs. Although this model has received plenty of attention recently, three major pieces remain missing for applying this model in ERTVS. (1) Embedded systems are more sensitive to resource utilization efficiency since this may drastically affect their deployment cost for including additional cores. Therefore, this paper proposes an optimal and an approximate RRP resource scheduler for multi-core platforms. (2) A resource reconfiguration is required when an embedded system has to switch between operating modes, resulting in the current cyclic schedule being replaced by another pre-configured and verified cyclic schedule. This paper formalizes a new One-Hop Reconfiguration (OHR) problem tailored for mode-switch-capable embedded systems and introduces a corresponding optimal solution. (3) No RRP-based toolset is currently available for embedded systems. This paper thus presents an optimized RRP toolset tailored for embedded systems. Numerous experiments are conducted to evaluate the efficacy of this toolset. [ABSTRACT FROM AUTHOR]

Massive MIMO and millimeter-wave communication (mmWave) have recently emerged as two key technologies for building 5G wireless networks and beyond. To reconcile the conflict between the large antenna arrays and the limited amount of radio-frequency (RF) chains in mmWave systems, the so-called hybrid beamforming becomes a promising solution and has received a great deal of attention in recent years. However, existing research on hybrid beamforming focused mostly on the physical layer or signal processing aspects. So far, there is a lack of theoretical understanding of how hybrid beamforming could affect mmWave network optimization. In this paper, we consider the impacts of hybrid beamforming on utility-optimality and queuing delay in mmWave cellular network optimization. Our contributions in this paper are three-fold: i) we develop a joint hybrid beamforming and congestion control algorithmic framework for mmWave network utility maximization; ii) we reveal a pseudoconvexity structure in the hybrid beamforming scheduling problem, which leads to simplified analog beamforming protocol design; and iii) we theoretically characterize the scalings of utility-optimality and delay with respect to channel state information (CSI) accuracy in digital beamforming. [ABSTRACT FROM AUTHOR]

This paper proposes on-driving experience sharing algorithms at junctions in infrastructure-assisted vehicles-to-everything networks. For the purpose, a millimeter-wave (mmWave) technology is used because it provides multi-Gbps data rates which is helpful for handling users’ short stay times at junctions and spatial reuse due to high beam directionality which is helpful for interference-avoidance among densely deployed vehicles at junctions. To realize on-driving experience sharing, the proposed algorithms focus on joint resource allocation and scheduling for 3GPP-compliant multiple unicast vehicle-to-vehicle (V2V) communications where the vehicles are group leaders (GLs) in 3GPP Mode 4(d). The resource allocation stands for the roadside unit (RSU) allocation to scheduled V2V GL links where RSU is essentially required for overcoming blockage by establishing two-hop relaying. Because vehicles stay for short times at junctions, this paper designs two algorithms without or with delay considerations. Without delay considerations, the joint optimization of RSU allocation and scheduling was originally formulated as mixed 0-1 non-convex optimization. However our proposed algorithm reformulates the problem into mixed 0-1 convex optimization, which is computationally easier to solve. With delay considerations, our proposed algorithm dynamically controls video contents frame rates for time-average on-driving video sharing quality maximization subject to delay constraints, inspired by Lyapunov optimization. Extensive simulation results demonstrate that our algorithms can significantly outperform in a variety of scenarios. Furthermore, we conduct the cost analysis for the proposed algorithms in terms of capital expenditure (CAPEX) and operating expenditure (OPEX). [ABSTRACT FROM AUTHOR]

Age of Information (AoI) has become an important metric to evaluate the freshness of information, and studies of minimizing AoI in wireless networks have drawn extensive attention. In mobile edge networks, changes in critical levels for distinct information is important for users’ decision making, especially when merely partial observations are available. However, existing research has not yet addressed this issue, which is the subject of this paper. To address this issue, we first establish a system model, in which the information freshness is quantified by changes in its critical levels. We formulate Age-of-Critical-Information (AoCI) minimization 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 choose update preferences for mobile clients under partial observations, where policies obtained by the above heuristic algorithm are utilized for expert policies. Finally, we demonstrate the superiority of our designed algorithm from both theoretical and experimental perspectives. [ABSTRACT FROM AUTHOR]

This paper proves an impossibility result for stochastic network utility maximization for multi-user wireless systems, including multiple access and broadcast systems. Every time slot an access point observes the current channel states for each user and opportunistically selects a vector of transmission rates. Channel state vectors are assumed to be independent and identically distributed with an unknown probability distribution. The goal is to learn to make decisions over time that maximize a concave utility function of the running time average transmission rate of each user. Recently it was shown that a stochastic Frank-Wolfe algorithm converges to utility-optimality with an error of $O(\log (T)/T)$ , where $T$ is the time the algorithm has been running. An existing $\Omega (1/T)$ converse is known. The current paper improves the converse to $\Omega (\log (T)/T)$ , which matches the known achievability result. It does this by constructing a particular (simple) system for which no algorithm can achieve a better performance. The proof uses a novel reduction of the opportunistic scheduling problem to a problem of estimating a Bernoulli probability $p$ from independent and identically distributed samples. Along the way we refine a regret bound for Bernoulli estimation to show that, for any sequence of estimators, the set of values $p \in [{0,1}]$ under which the estimators perform poorly has measure at least 1/6. [ABSTRACT FROM AUTHOR]

Reconfigurable intelligent surface (RIS) is capable of intelligently manipulating the phases of the incident electromagnetic wave to improve the wireless propagation environment between the base-station (BS) and the users. This paper addresses the joint user scheduling, RIS configuration, and BS beamforming problem in an RIS-assisted downlink network with limited pilot overhead. We show that graph neural networks (GNN) with permutation invariant and equivariant properties can be used to appropriately schedule users and to design RIS configurations to achieve high overall throughput while accounting for fairness among the users. As compared to the conventional methodology of first estimating the channels then optimizing the user schedule, RIS configuration and the beamformers, this paper shows that an optimized user schedule can be obtained directly from a very short set of pilots using a GNN, then the RIS configuration can be optimized using a second GNN, and finally the BS beamformers can be designed based on the overall effective channel. Numerical results show that the proposed approach can utilize the received pilots more efficiently than the conventional channel estimation based approach, and can generalize to systems with an arbitrary number of users. [ABSTRACT FROM AUTHOR]

Role assignment is a critical element in the role-based collaboration process. There are many different requirements to be considered when undertaking this task. This correspondence paper formalizes the group multirole assignment (GMRA) problem; proves the necessary and sufficient condition for the problem to have a feasible solution, provides an improved IBM ILOG CPLEX optimization package solution, and verifies the proposed solution with experiments. The contributions of this paper include: 1) the formalization of an important engineering problem, i.e., the GMRA problem; 2) a theoretical proof of the necessary and sufficient condition for GMRA to have a feasible solution; and 3) an improved ILOG solution to such a problem. [ABSTRACT FROM AUTHOR]

This paper presents an energy scheduling and output smoothing scheme for storage aided utility scale photovoltaic systems. A weighted energy scheduling approach is adopted for the peak load periods, and this ensures enhanced performance with well-fitted supply-demand curve and flat net load variation. A novel smoothing method is proposed by blending double grid search support vector machine power prediction with first-in-first-out robust smoothing. The actual hourly and minute interval data sets for Australia are used for case studies, demonstrating the effectiveness and efficiency of the proposed scheme. [ABSTRACT FROM PUBLISHER]

This paper constructs an integrated virtual reconfiguration model that can simultaneously group workstations, schedule virtual cells, and select energy consumption levels. If managers prefer the physical proximity of machines in a certain virtual cell, the material handling cost in it can be reduced. However, the distances among machines in other virtual cells are probably large, which may cause greater material handling cost. If a virtual cell for a certain product type has priority to be created, the backorder cost of that type can be decreased or even avoided. Nevertheless, the creation of virtual cells for other product types may be delayed, perhaps leading to the higher backorder cost of other product types. In addition, managers can choose a high energy consumption level of a machine to expedite its production to reduce backorder cost at the expense of more energy consumption cost. To minimize the total operational cost, we develop a novel Discrete Imperialist Competitive Algorithm with a Priority rule-based heuristic (DICAP). It includes a colony movement strategy, a competition strategy, a collapse mechanism, a development strategy, and a sufficient convergence policy. Numerical experiments and t-test are conducted to validate that the proposed DICAP outperforms genetic algorithm and simulated annealing. Note to Practitioners—Virtual cellular manufacturing systems can create an expectation of improving machine utilization and productivity, reducing reconfiguration cost, and adaptation to product specification changes in reality. However, managers often feel difficult to make appropriate decisions for three interrelated issues, i.e., workstation grouping, virtual cell creation and release, and energy consumption options. Workstation grouping depends on the availability of machines and workers, and the availability may be related to the creation and release time of some virtual cells. Whether a virtual cell is created in time has an influence on the selection of energy consumption levels, because managers need to consider both backorder cost and energy consumption cost. In addition, there often exists a bottleneck workstation in each virtual cell. Therefore, it is essential and worthwhile to select appropriate energy consumption levels of machines to smooth the production efficiency of grouped workstations. To effectively address the issues, this paper presents an integrated virtual reconfiguration model. A novel Discrete Imperialist Competitive Algorithm with a Priority rule-based heuristic is developed to minimize the total operational cost. Numerical experiments and t-test results indicate that the proposed algorithm outperforms two commonly used ones, i.e., genetic algorithm and simulated annealing in solution quality. It is suitable for virtual reconfiguration problem with industrial size in practice. [ABSTRACT FROM AUTHOR]

Real-time dynamic workload consists of tasks that can arbitrarily join and leave the system at run-time. To avoid incurring deadline misses, tasks that request to join the system must pass an admission test, which has to cope with potential scheduling transients originated by the residual effect of the tasks that previously left the system. This phenomenon may require some tasks to suffer an admission delay before being accepted for execution. This paper focuses on uniprocessor earliest-deadline first (EDF) scheduling with constrained deadlines and explicitly considers methods for handling scheduling transients in the presence of dynamic real-time workload. A generalized analysis framework is first presented to overcome several limitations of the existing approaches (including the support for overlapping transients), and is then used to derive methods for computing bounds on the admission delays incurred by tasks. Building on such results, an on-line protocol is proposed to handle the admission control of a dynamic workload, which also comes with a variant that can execute in polynomial time to favor its practical application. Furthermore, the paper shows how the presented analysis can be used off-line for analyzing mode-changes among static task sets. Experimental results are finally presented to evaluate the proposed algorithms. [ABSTRACT FROM AUTHOR]

Based on the Petri net (PN) models of the flexible manufacturing systems (FMSs), this paper focuses on solving the scheduling problem of minimizing the total energy consumption of FMSs. In the view of different energy consumption rates of resources under different working statuses, two energy consumption functions are considered. The dynamic programming (DP) models of the scheduling problems based on PNs are established, where a reachable marking of a PN model, start processing time vector, route vector, and the transition sequence leading to the reachable marking from the initial one, is regarded as a state, and the Bellman equation is based on transition firing. For small-size scheduling problems, their optimal solutions can be obtained by the presented DP algorithm. However, it is difficult to solve larger-scale ones since the number of explored states increases exponentially with the problem size, which makes DP computationally infeasible. To obtain an optimal or suboptimal schedule in an acceptable time, modified DP (MDP) algorithm is proposed, in which fewer states are explored. In MDP, two ways are introduced through which only the most promising states are explored. One is keeping only one transition sequence for each marking through an evaluation function. Another is selecting the most promising states in each stage for further exploration through a heuristic function. To guarantee that the generated states are safe, a deadlock controller is applied in the recursion procedure of MDP. Experimental results on manufacturing systems and comparisons with existing works are provided to show the effectiveness of MDP. Note to Practitioners—This paper is motivated by the need of optimizing the energy consumption of manufacturing systems, considering the increasing energy cost and environmental concerns. Existing studies on energy optimization rarely focus on flexible manufacturing systems (FMSs) which exhibit a high degree of resource sharing and route flexibility and can be highly adaptable to various production plans and goals. Scheduling becomes more challenging when facing deadlock-prone FMSs. This paper provides a method to solve this complex scheduling problem efficiently. In this paper, dynamic programming (DP) is formulated for it, and the optimal energy consumption schedules are found. Considering the computational burden of implementing DP in the scheduling of large-size FMSs, a novel scheduling method named modified DP (MDP) is proposed. Experimental tests on an FMS and a stamping system suggest that MDP can successfully find feasible solutions. Besides, it can be applied to other FMS scheduling problems and industrial cases, once their processing time of operations and energy consumption of resources per unit time are known. [ABSTRACT FROM AUTHOR]

Home healthcare (HHC) is a service that dispatches caregivers to people in need of healthcare who live in the home. The task assignment and route generation for caregivers can be formulated as an extension of the well-known vehicle routing problem with time windows (VRPTW). Currently, the most successful exact algorithms for VRPTW are based on a framework combining column generation (CG) and branching. Although such methods could be successful for HHC routing and scheduling problem (HHCRSP) as well, fast approximate algorithms are appealing, especially for large problems. In an early version of this paper, we employed a heuristic distributed gossip algorithm to solve HHCRSP. In this paper, we integrate the gossip algorithm with a local solver based on CG, which makes it an effective algorithm for larger problem instances. As it will be shown with extensive numerical experiments, for large problem instances, gossip-CG performs better than the pure CG. Note to Practitioners—The task of routing and scheduling caregivers for HHC providers can be formulated as a mathematical problem that is theoretically challenging to solve to optimality for large-scale problems involving many clients and caregivers. Although extensive research and tools for tackling this problem already exist, in practice, even in developed countries, it is still common to rely on schedules generated manually by staff. What we present in this paper is the summary of our theoretical work on tackling such problems. The benefit of the framework that we propose, the CG-based gossip method, is that it can be preempted at any time if the staff requires to obtain a good schedule as soon as possible. If ample time is available, one can let our algorithm to run for a longer period of time to generate even shorter routes. [ABSTRACT FROM AUTHOR]

The paper surveys the state of the art of task scheduling in Desktop Grid computing systems. We describe the general architecture of a Desktop Grid system and the computing model adopted by the BOINC middleware. We summarize research papers to bring together and examine the optimization criteria and methods proposed by researchers so far for improving Desktop Grid task scheduling (assigning tasks to computing nodes by a server). In addition, we review related papers, which address non-regular architectures, like hierarchical and peer-to-peer Desktop Grids, as well as Desktop Grids designed for solving interdependent tasks. [ABSTRACT FROM AUTHOR]

This paper is concerned with scheduling of a set of ${n}$ single-operation tasks/orders on a set of $m$ unrelated parallel machines where subcontracting is allowed. When a machine/subcontractor is chosen to do a set of orders/tasks, it incurs a one-time fixed cost. When a job/order is performed by a machine/subcontractor, there is a cost that depends on the machine/subcontractor. The objective is to choose a subset of ${k}$ machines and/or subcontractors from the set of all ${m}$ available machines and/or subcontractors to perform all jobs to minimize the sum of total workload costs and total fixed costs. We discuss the complexity of the problem, and prove NP-hardness of the problem. Simplified mathematical development is provided that allows efficient implementation of two-exchange algorithms. An efficient tabu search heuristic with a diversification generation component is developed. An extensive computational experiment of the heuristic for large-scale problems with comparison to the results from CPLEX software is presented. We also solved 40 benchmark ${k}$ -median problems available on the Internet that have been used by many researchers. Note to Practitioners—To be competitive in the global market, companies must be prudent in the use of their resources. This paper considers a parallel scheduling environment where choosing in-house machines and/or subcontractors as resources to perform the orders/jobs is the main objective. Processing time (or cost) of a job to be performed by different machines or subcontractors can be different. Furthermore, if a machine or a subcontractor is chosen to perform a set of orders, there is a one-time fixed cost (in the case of subcontractor it can be considered transportation cost) that depends on the machine or subcontractor. The scheduling criteria are to choose a subset of $k$ machines and/or subcontractors to do all orders/jobs while minimizing the sum of the total workload and total fixed costs. The complexity of the problem is discussed and shown to be NP-hard. An efficient tabu search that solves large-scale problems in fraction of a second of CPU time is presented and an extensive computational experiment is provided. [ABSTRACT FROM AUTHOR]

Applications in data-parallel computing typically consist of multiple stages. In each stage, a set of intermediate parallel data flows (Coflow) is produced and transferred between servers to enable starting of next stage. While there has been much research on scheduling isolated coflows, the dependency between coflows in multi-stage jobs has been largely ignored. In this paper, we consider scheduling coflows of multi-stage jobs represented by general DAGs (Directed Acyclic Graphs) in a shared data center network, so as to minimize the total weighted completion time of jobs. This problem is significantly more challenging than the traditional coflow scheduling, as scheduling even a single multi-stage job to minimize its completion time is shown to be NP-hard. In this paper, we propose a polynomial-time algorithm with approximation ratio of $O(\mu \log (m)/\log (\log (m)))$ , where $\mu $ is the maximum number of coflows in a job and $m$ is the number of servers. For the special case that the jobs’ underlying dependency graphs are rooted trees, we modify the algorithm and improve its approximation ratio. To verify the performance of our algorithms, we present simulation results using real traffic traces that show up to 53% improvement over the prior approach. We conclude the paper by providing a result concerning an optimality gap for scheduling coflows with general DAGs. [ABSTRACT FROM AUTHOR]

This paper proposes a novel scheduling strategy to dispatch controllable loads with nonlinear power-efficiency characteristics. Due to these characteristics, the controllable loads, such as desalination devices, suffer from efficiency loss when participating in day-ahead and real-time power regulations. The existing two-stage scheduling algorithms ignore the real-time efficiency loss at the day-ahead stage. In order to consider the real-time efficiency loss, a complex single-stage scheduling model with numerous optimization variables is required. This will greatly increase the computation burden to the optimization algorithm. To deal with this issue, a novel efficiency threshold-based control method is proposed in this paper. The proposed method only has three efficiency thresholds, thus the number of optimization variables is significantly reduced. Based on this method, a novel energy scheduling framework is designed for the controllable loads with power-efficiency characteristics. Numerical simulations indicate that the proposed approach can utilize the power regulation flexibility of controllable loads in both day-ahead and real-time stages to reduce the operation cost. [ABSTRACT FROM AUTHOR]

Employees are increasingly using electric vehicles (EVs) as their choice of company car. Charging infrastructure is limited by undersized connection lines and a lack of charging stations on company premises. Upgrades require significant financial investment, time, and effort. Smart charging represents an approach to make the most of existing infrastructure while satisfying charging needs. The objective of smart charging depends on the business context. Objectives of interest include fair share maximization, electricity cost minimization, peak demand minimization, and load imbalance minimization. During business hours, EV arrivals and departures are predictable while still containing uncertainty. To utilize this knowledge ahead of time, this paper presents a novel approach for combining day-ahead and real-time planning for smart charging. First, we model the problem using mixed-integer programming for day-ahead planning to precompute schedules. Next, we propose a schedule guided heuristic which takes as input precomputed schedules and adapts them in real time as new information arrives. Both methods use a parameterized weighting mechanism to flexibly combine and emphasize individual objectives of smart charging. Experimental results from simulations show significant benefits of combining day-ahead and real-time planning over using a single planning approach in isolation. Improvements include increased fair share and decreased energy costs. [ABSTRACT FROM AUTHOR]

This paper studies a hot rolling batch scheduling problem in compact strip production (CSP), which is decomposed into a two-stage problem. The first stage is the strip combination problem aimed at determining the strip combination of each rolling turn and the number of rolling turns with the objective of minimizing the number of virtual strips, and the second is the strip allocation and sequencing problem aimed at optimizing the allocation and rolling sequence of the strips in each rolling turn. We first model this two-stage problem considering a set of production constraints and then design an optimal approach to solve the strip combination problem. Subsequently, we design an evolutionary algorithm (i.e., artificial bee colony algorithm) with a novel search strategy for employed bees, a dynamic strategy for onlooker bees, a variable neighborhood search strategy for a scout bee, and an enhanced strategy to solve the problem in the second stage. Computational experiments demonstrate the effectiveness of the proposed algorithms. Note to Practitioners—The hot rolling batch scheduling process is crucial in linking the casting and rolling processes of iron and steel productions. In the rolling batch scheduling problem of CSP, there is no buffer between the casting and rolling processes, and virtual strips must be added to satisfy production constraints. Most rolling batch scheduling methods do not consider the addition of virtual strips. In this paper, we mathematically characterize the hot rolling batch scheduling problem in CSP with flexible production constraints. We then show how the optimal approach and artificial bee colony algorithm are designed. Finally, the effectiveness of the proposed algorithms is demonstrated by comparisons with other well-known metaheuristic algorithms. This paper can be extended to other hot rolling batch scheduling problems with buffers and hybrid flowshop scheduling problems. [ABSTRACT FROM AUTHOR]

A growing number of organizations deploy multiple heterogeneous applications in infrastructures of distributed green data centers (DGDCs) to flexibly provide services to users around the world in a low-cost and high-quality way. The skyrocketing growth in types and number of heterogeneous applications dramatically increases the amount of energy consumed by DGDCs. The spatial and temporal variations in prices of power grid and availability of renewable energy make it highly challenging to minimize the energy cost of DGDC providers by intelligently scheduling arriving tasks of heterogeneous applications among GDCs while meeting their expected delay bound constraints. Unlike existing studies, this paper proposes a spatiotemporal task scheduling (STTS) algorithm to minimize energy cost by cost-effectively scheduling all arriving tasks to meet their delay bound constraints. STTS well investigates spatial and temporal variations in DGDCs. In each time slot, the energy cost minimization problem is formulated as a nonlinear constrained optimization one and addressed with the proposed genetic simulated-annealing-based particle swarm optimization. Trace-driven experiments show that STTS achieves larger throughput and lower energy cost than several typical task scheduling approaches while strictly meeting all tasks’ delay bound constraints. Note to Practitioners—This paper investigates the energy cost minimization problem for a DGDC provider while meeting delay bound constraints for all arriving tasks. Previous scheduling methods do not jointly consider spatial and temporal variations in prices of power grid and availability of renewable energy in DGDCs. Therefore, they fail to adopt such variations to minimize the energy cost of a DGDC provider. In this paper, a new method that avoids disadvantages of previous methods is proposed. It is realized by adopting a hybrid metaheuristic algorithm named GSP to solve a nonlinear constrained optimization problem. Experimental results demonstrate that compared with several typical methods, it reduces energy cost and increases throughput. It can be readily integrated into realistic industrial DGDCs. The future work requires engineers to consider the effect of indeterminacy and uncertainty of green energy on scheduling methods. [ABSTRACT FROM AUTHOR]

Consider a massive random access scenario in which a small set of $k$ active users out of a large number of $n$ potential users need to be scheduled in $b\ge k$ slots. What is the minimum common feedback to the users needed to ensure that scheduling is collision-free? Instead of a naive scheme of listing the indices of the $k$ active users in the order in which they should transmit, at a cost of $k\log (n)$ bits, this paper shows that for the case of $b=k$ , the rate of the minimum fixed-length common feedback code scales only as $k \log (e)$ bits, plus an additive term that scales in $n$ as $\Theta (\log \log (n))$ for fixed $k$. If a variable-length code can be used, assuming uniform activity among the users, the minimum average common feedback rate still requires $k \log (e)$ bits, but the dependence on $n$ can be reduced to $O(1)$. When $b>k$ , the number of feedback bits needed for collision-free scheduling can be significantly further reduced. Moreover, a similar scaling on the minimum feedback rate is derived for the case of scheduling $m$ users per slot, when $k \le mb$. The problem of constructing a minimum collision-free feedback scheduling code is connected to that of constructing a perfect hashing family, which allows practical feedback scheduling codes to be constructed from perfect hashing algorithms. [ABSTRACT FROM AUTHOR]

This paper studies the problem of scheduling machines in the photolithography area of a semiconductor manufacturing facility. The scheduling problem is characterized as an unrelated parallel machine scheduling problem with machine eligibilities, sequence- and machine-dependent setup times, auxiliary resources and transfer times for the auxiliary resources. Each job requires two auxiliary resources: a reticle and a pod. Reticles are handled in pods and a pod contains multiple reticles. Both reticles and pods are used on multiple machines and a transfer time is required if transferred from one machine to another. A novel constraint programming (CP) approach is proposed and is benchmarked against a mixed-integer programming (MIP) method. The results of the study, consisting of a real-world case study at a global semiconductor manufacturer, demonstrate that the CP approach significantly outperforms the MIP method and produces high-quality solutions for multiple real-world instances, although optimality cannot be guaranteed. [ABSTRACT FROM AUTHOR]

This paper proposes a novel repair rule set (RRS) for scheduling the power system infrastructure repair after the occurrence of extreme events. RRS is made up of multiple repair rules, each of them can be applied in arbitrary post-disaster failure scenarios to rank the repair actions by priority. A learning-to-rank technique called AdaRank is used to train the repair rules by combining the weak learners derived from the dynamic repair scheduling model. Then, RRS is constructed by iteratively clustering the training cases and retraining the repair rule for each cluster. Increasing the number of repair rules within RRS allows it to differentiate various types of failure scenarios, thereby improving its performance. Further combined with multi-label K nearest neighbor (ML-KNN) technique, RRS is able to schedule the repair without the full knowledge of real-time failure information, such as the estimated repair time. The results of case studies on IEEE-118 test systems show that the proposed method has a desirable performance compared to the exact mathematical optimization model. Moreover, it reduces the requirement for failure information while significantly improving the computational efficiency. [ABSTRACT FROM AUTHOR]

The Third Generation Partnership Project has standardized cellular vehicle-to-everything (C-V2X) sidelink Mode 4 to support direct communication between vehicles. In Mode 4, the sensing-based semipersistent scheduling (SPS) scheme enables vehicles to autonomously reserve and select radio resources. In particular, SPS has three processes to realize the resource scheduling, including continuously sensing resources, probabilistically reselecting resources, and periodically reserving resources. However, vehicles randomly select resources from the available resource lists in the resource reselection process, resulting in frequent packet collisions especially when radio resources are insufficient. Unlike the traditional SPS, this paper proposes a multiagent deep reinforcement learning-based SPS (RL-SPS) algorithm to help vehicles select appropriate radio resources with the aim of reducing packet collisions. Furthermore, a multi-head attention mechanism is adopted to improve the training efficiency by helping vehicles selectively pay attention to the observations and actions of neighbouring vehicles. It is worth noting that the RL-SPS algorithm fits the characteristics of Mode 4, which selects resources without requiring any global information. Simulation results show that RL-SPS outperforms other decentralized approaches and demonstrate the scalability and robustness of RL-SPS in a dynamic vehicular network. [ABSTRACT FROM AUTHOR]

Age of Information (AoI) is an application layer performance metric that quantifies the freshness of information. This paper investigates scheduling problems at network edge when there is an AoI requirement for each source node, which we call Maximum AoI Threshold (MAT). Specifically, we want to determine whether or not a vector of MATs corresponding to the source nodes is schedulable, and if so, find a feasible scheduler for it. For a small network, we present an optimal procedure called Cyclic Scheduler Detection (CSD) that can determine the schedulability with absolute certainty. For a large network where CSD is not applicable, we present a novel low-complexity procedure, called Fictitious Polynomial Mapping (FPM), and prove that FPM can find a feasible scheduler for any MAT vector when the load is under $\ln 2$. We use extensive numerical results to validate our theoretical results and show that the performance of FPM is significantly better than a state-of-the-art scheduling algorithm. [ABSTRACT FROM AUTHOR]

Multiple heterogeneous applications concurrently run in distributed cloud data centers (CDCs) for better performance and lower cost. There is a highly challenging problem of how to minimize the total cost of a CDCs provider in a market where the bandwidth and energy cost show geographical diversity. To solve the problem, this paper first proposes a revenue-based workload admission control method to judiciously admit requests by considering factors including priority, revenue and the expected response time. Then, this paper presents a cost-aware workload scheduling method to jointly optimize the number of active servers in each CDC, and the selection of Internet service providers for the CDCs provider. Finally, trace-driven simulation results demonstrate that the proposed methods can greatly reduce the total cost and increase the throughput of the CDCs provider in comparison to existing methods. [ABSTRACT FROM AUTHOR]

This paper addresses the joint coordinated scheduling and power control problem in cloud-enabled networks. Consider the downlink of a cloud-radio access network (CRAN), where the cloud is only responsible for the scheduling policy, power control, and synchronization of the transmit frames across the single-antenna base-stations (BS). The transmit frame consists of several time/frequency blocks, called power-zones (PZs). The paper considers the problem of scheduling users to PZs and determining their power levels (PLs), by maximizing the weighted sum-rate under the practical constraints that each user cannot be served by more than one base-station, but can be served by one or more power-zones within each base-station frame. The paper solves the problem using a graph theoretical approach by introducing the joint scheduling and power control graph formed by several clusters, where each is formed by a set of vertices, representing the possible association of users, BSs, and PLs for one specific PZ. The problem is, then, formulated as a maximum-weight clique problem, in which the weight of each vertex is the sum of the benefits of the individual associations belonging to that vertex. Simulation results suggest that the proposed cross-layer scheme provides appreciable performance improvement as compared to schemes from recent literature. [ABSTRACT FROM PUBLISHER]

This paper deals with the novel and complex problem of scheduling the internal operations in post-distribution cross docking systems (PDCDSs), i.e., a kind of cross docking terminal where the operations of good allocation are performed. More precisely, internal operations of the PDCDS consist in deconsolidating inbound cases, sorting products according to customer requests, and consolidating outbound cases. The problem is determining the optimal schedule of the internal operations with the objective of minimizing the makespan. The contribution of this paper is twofold. First, the PDCDS scheduling problem is characterized and the corresponding NP-hardness is proved. Second, in order to address the complexity of the problem, two mixed integer linear programming (MILP) models and a heuristic algorithm are presented. In particular, the mathematical programming formulations are solved by using symmetry breaking constraints and objective function perturbations. Moreover, the lower bounds of the start times of operations are evaluated in order to strengthen the formulations. A set of test results compare the formulation performances and a case study shows the effectiveness of the proposed heuristic algorithm to schedule the operations of an half work day of an Italian company of cloth retail stores. [ABSTRACT FROM AUTHOR]

This paper is concerned with the moving horizon (MH) estimation issue for a type of networked nonlinear systems (NNSs) with the so-called random access (RA) protocol scheduling effects. To handle the signal transmissions between sensor nodes and the MH estimator, a constrained communication channel is employed whose channel constraints implies that at each time instant, only one sensor node is permitted to access the communication channel and then send its measurement data. The RA protocol, whose scheduling behavior is characterized by a discrete-time Markov chain (DTMC), is utilized to orchestrate the access sequence of sensor nodes. By extending the robust MH estimation method, a novel nonlinear MH estimation scheme and the corresponding approximate MH estimation scheme are developed to cope with the state estimation task. Subsequently, some sufficient conditions are established to guarantee that the estimation error is exponentially ultimately bounded in mean square. Based on that the main results are further specialized to linear systems with the RA protocol scheduling. Finally, two numerical examples and the corresponding figures are provided to verify the effectiveness/correctness of the developed MH estimation scheme and approximate MH estimation scheme. [ABSTRACT FROM AUTHOR]

While 5G is being deployed all around the world, the industry and academia start the investigation of 6G. Network function virtualization (NFV) is seen as the key enabler towards the flexible resource management and sharing of 6G networks. The main idea of NFV is to decouple the physical devices from the specific functions that run on them. In NFV, virtual network service (NS) is modeled as a service function chain (SFC). The challenges in SFC description, composition, embedding, and scheduling are key issues in NFV. In this paper, we focus on the joint SFC embedding and scheduling for NFV in 6G networks. With the assistance of sensing the physical node resource abilities, we propose a novel SFC embedding and scheduling algorithm, which is named as RA-SFC-6G. A new service is first composed as an SFC which is an ordered sequence of virtual network functions (VNFs). Afterwards, our RA-SFC-6G algorithm will select the physical nodes with stronger resource abilities and abundant resources to accommodate the SFC. In addition, the NS is guaranteed to be implemented without violating the NS maximum allowed scheduling time. If violated, our RA-SFC-6G can re-embed and re-schedule the violated VNFs to suitable positions. In order to validate our RA-SFC-6G performance, we do the experiment work. Experiment results show that our RA-SFC-6G achieves at least 10% higher SFC acceptance ratio than the previous counterparts and the typical heuristics. [ABSTRACT FROM AUTHOR]

The Smart City contexts and the adoption of Industry 4.0 are being upgraded with the latest technologies throughout all systems. New data are continuously collected in huge amounts; therefore, an efficient data aggregation scheduling scheme is highly demanded. This paper addresses the minimum time aggregation scheduling problem in duty-cycled sensor networks. Existing solutions schedule the sensory data through predefined routing structures, which limit the utilization of diverse active time slots of sensors. We propose a period-driven pipeline scheduling approach, namely PDA, that simultaneously grows the aggregation tree and assigns a transmission schedule for each node being added to the tree. Particularly, this process is performed in a top-down manner. In each iteration, corresponding to a time slot, PDA uses a multi-level ranking strategy to schedule several $\langle sender, receiver \rangle$ 〈 s e n d e r , r e c e i v e r 〉 pairs, so that in a working period ahead, the possibility to pipeline as many transmissions as possible is high. Intensive simulation results show that the proposed scheme notably works better than the best known recent algorithms by having up to 35 percent shorter aggregation time, as well as having a significantly improved network throughput and time utilization. [ABSTRACT FROM AUTHOR]

The rapid growth of mobile data traffic in a high-speed scenario imposes great challenges on wireless system design and optimization, where the inherent Doppler shift, frequent cell switching, and large penetration loss will significantly degrade the quality of transceiver signals. Wireless resource scheduling dynamically allocates wireless resources according to the user channel conditions and quality of service requirement, which is an enabling approach to maximize the resource utilization. In this paper, we develop a new wireless resource scheduling method in high mobility scenario to uplift the system performance. We first propose a feature extraction algorithm to extract the spatial traffic characteristics. On this basis, several time-series prediction algorithms are leveraged to predict the traffic volume. Then, we introduce cell switching indicator (CSI) into channel quality prediction to improve the signal-to-noise ratio (SNR) prediction performance. Based on the predicted results of service traffic and user channel quality variations, a resource scheduling strategy is proposed, which compromises the total system throughput and user satisfaction. Simulation results validate the effectiveness of the proposed scheduling algorithm. [ABSTRACT FROM AUTHOR]