Review on Service Curves of Typical Scheduling Algorithms

In recent years,various internet architectures,such as Integrated Services(IntServ),Differentiated Services(DiffServ),Time Sensitive Networking(TSN)and Deterministic Networking(DetNet),have been proposed to meet the quality-of-service(QoS)requirements of different network services.Concurrently,network calculus has found widespread application in network modeling and QoS analysis.Network calculus abstracts the details of how nodes or networks process data packets using the concept of service curves.This paper summarizes the service curves for typical scheduling algorithms,including Strict Priority(SP),Round Robin(RR),Cycling Queuing and Forwarding(CQF),Time Aware Shaper(TAS),Credit Based Shaper(CBS),and Asynchronous Traffic Shaper(ATS).It introduces the theory of network calculus and then provides an overview of various scheduling algorithms and their associated service curves.The delay bound analysis for different scheduling algorithms in specific scenarios is also conducted for more insights.

A Conservative Multiversion Locking-Graph Scheduler Algorithm

In order to improve the concurrency of multiversion database systems,a conservative MV locking-graph scheduler algorithm is proposed,which takes the power of MVS as a target.The algorithm combines the advantages of locking and graph,and does optimizing processes on read-only and write-only operations to reduce the blocks of transactions.The correctness and com- plexity of the algorithm are also provided.

Rolling horizon scheduling algorithm for dynamic vehicle scheduling system

Dynamic exclusive pickup and delivery problem with time windows (DE-PDPTW), aspecial dynamic vehicle scheduling problem, is proposed. Its mathematical description is given andits static properties are analyzed, and then the problem is simplified asthe asymmetrical travelingsalesman problem with time windows. The rolling horizon scheduling algorithm (RHSA) to solve thisdynamic problem is proposed. By the rolling of time horizon, the RHSA can adapt to the problem'sdynamic change and reduce the computation time by dealing with only part of the customers in eachrolling time horizon. Then, its three factors, the current customer window, the scheduling of thecurrent customer window and the rolling strategy, are analyzed. The test results demonstrate theeffectiveness of the RHSA to solve the dynamic vehicle scheduling problem.

Dynamic and Integrated Load-Balancing Scheduling Algorithm for Cloud Data Centers

One of the challenging scheduling problems in Cloud data centers is to take the allocation and migration of reconfigurable virtual machines as well as the integrated features of hosting physical machines into consideration. We introduce a Dynamic and Integrated Resource Scheduling algorithm (DAIRS) for Cloud data centers. Unlike traditional load-balance scheduling algorithms which often consider only one factor such as the CPU load in physical servers, DAIRS treats CPU, memory and network bandwidth integrated for both physical machines and virtual machines. We develop integrated measurement for the total imbalance level of a Cloud datacenter as well as the average imbalance level of each server. Simulation results show that DAIRS has good performance with regard to total imbalance level, average imbalance level of each server, as well as overall running time.

High Throughput Scheduling Algorithms for Input Queued Packet Switches

The high-performance computing paradigm needs high-speed switching fabrics to meet the heavy traffic generated by their applications.These switching fabrics are efficiently driven by the deployed scheduling algorithms.In this paper,we proposed two scheduling algorithms for input queued switches whose operations are based on ranking procedures.At first,we proposed a Simple 2-Bit(S2B)scheme which uses binary ranking procedure and queue size for scheduling the packets.Here,the Virtual Output Queue(VOQ)set with maximum number of empty queues receives higher rank than other VOQ’s.Through simulation,we showed S2B has better throughput performance than Highest Ranking First(HRF)arbitration under uniform,and non-uniform traffic patterns.To further improve the throughput-delay performance,an Enhanced 2-Bit(E2B)approach is proposed.This approach adopts an integer representation for rank,which is the number of empty queues in a VOQ set.The simulation result shows E2B outperforms S2B and HRF scheduling algorithms with maximum throughput-delay performance.Furthermore,the algorithms are simulated under hotspot traffic and E2B proves to be more efficient.

An optimal scheduling algorithm based on task duplication

When the communication time is relatively shorter than the computation time for every task, the task duplication based scheduling (TDS) algorithm proposed by Darbha and Agrawal generates an optimal schedule. Park and Choe also proposed an extended TDS algorithm whose optimality condition is less restricted than that of TDS algorithm, but the condition is very complex and is difficult to satisfy when the number of tasks is large. An efficient algorithm is proposed whose optimality condition is less restricted and simpler than both of the algorithms, and the schedule length is also shorter than both of the algorithms. The time complexity of the proposed algorithm is O(v2), where v represents the number of tasks.

RECONFIGURABLE PRODUCTION LINE MODELING AND SCHEDULING USING PETRI NETS AND GENETIC ALGORITHM

In response to the production capacity and functionality variations, a genetic algorithm （GA） embedded with deterministic timed Petri nets（DTPN） for reconfigurable production line（RPL） is proposed to solve its scheduling problem. The basic DTPN modules are presented to model the corresponding variable structures in RPL, and then the scheduling model of the whole RPL is constructed. And in the scheduling algorithm, firing sequences of the Petri nets model are used as chromosomes, thus the selection, crossover, and mutation operator do not deal with the elements in the problem space, but the elements of Petri nets model. Accordingly, all the algorithms for GA operations embedded with Petri nets model are proposed. Moreover, the new weighted single-objective optimization based on reconfiguration cost and E/T is used. The results of a DC motor RPL scheduling suggest that the presented DTPN-GA scheduling algorithm has a significant impact on RPL scheduling, and provide obvious improvements over the conventional scheduling method in practice that meets duedate, minimizes reconfiguration cost, and enhances cost effectivity.

A Disk Scheduling Algorithm:SPFF

We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first （SPFF）. This algorithm is based on the shortest path of disk head motion constructed by all the pendent requests. From view of the head moving distance, it has the stronger glohality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system＇s different demands.

A Throughput-Driven Scheduling Algorithm of Differentiated Service for Web Cluster

Requests distribution is an key technology for Web cluster server. This paper presents a throughput-driven scheduling algorithm （TDSA）. The algorithm adopts the throughput of cluster back-ends to evaluate their load and employs the neural network model to predict the future load so that the scheduling system features a self-learning capability and good adaptability to the change of load. Moreover, it separates static requests from dynamic requests to make full use of the CPU resources and takes the locality of requests into account to improve the cache hit ratio. Experimental re suits from the testing tool of WebBench^TM show better per formance for Web cluster server with TDSA than that with traditional scheduling algorithms.

Multiple QoS modeling and algorithm in computational grid

Multiple QoS modeling and algorithm in grid system is considered. Grid QoS requirements can be formulated as a utility function for each task as a weighted sum of its each dimensional QoS utility functions. Multiple QoS constraint resource scheduling optimization in computational grid is distributed to two subproblems： optimization of grid user and grid resource provider. Grid QoS scheduling can be achieved by solving sub problems via an iterative algorithm.

Makespan and reliability driven scheduling algorithm for independent tasks in Grids

In the dynamic, complex and unbounded Grid systems, failures of Grid resources caused by malicious attacks and hardware failures are inevitable and have an adverse effect on the execution of tasks. To mitigate this problem, a makespan and reliability driven （MRD） sufferage scheduling algorithm is designed and implemented. Different from the traditional Grid scheduling algorithms, the algorithm addresses the makespan as well as reliability of tasks. The simulation experimental results show that the MRD sufferage scheduling algorithm can increase reliability of tasks and can trade off reliability against makespan of tasks by adjusting the weighting parameter in its cost function. So it can be applied to the complex Grid computing environment well.

An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop problem with the variable batches scheduling model is formulated.Second,we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method.Moreover,in order to increase the diversity of the population,two methods are developed.One is the threshold to control the neighborhood updating,and the other is the dynamic clustering algorithm to update the population.Finally,a group of experiments are carried out.The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively,and has effective performance in solving the flexible job shop scheduling problem with variable batches.

Genetic Algorithm for Scheduling Reentrant Jobs on Parallel Machines with a Remote Server

This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm(GA) to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound(BB) algorithm and the heuristic algorithm, coordinated scheduling(CS), which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%.

Scheduling Algorithm for Multimedia Services in IEEE 802.16e OFDM System

Based on five scheduling types and their QoS requirements defined in IEEE 802.16e specification, this paper proposes a new scheduring algorithm for non-real-time or real-time multimedia services. Taking the performances of efficiency, fairness and complexity into consideration, the proposed algorithm enhances the efficiency of air interface resource at the expense of the short-time unfairness, but ensures the long-time fairness. Moreover, the proposed algorithm introduces an efficient QoS assurance mechanism, which implements the functions of congestion control, queuing management and traffic management. The simulation results based on a simplified traffic model show that the proposed algorithm guarantees better performances of efficiency and fairness than conventional algorithms, without increasing the algorithm complexity. Especially on the occasion of heavy-traffic requirement, the performance of efficiency and fairness can be improved by 50% at most.

Schedule algorithm for mitigating inter-cell interference based on orthogonal complement space

In order to avoid severe performance degradation led by the inter-cell interference (ICI) in orthogonal frequency division multiple access (OFDMA) systems with a frequency reused factor (FRF) of 1,distributed schedule algorithm (DS-OCS) and distributed proportional fairness schedule algorithm (DPFS-OCS) based on orthogonal complement space (OCS) were proposed. The first right and left singular vectors of the channel that the user experienced were selected as the transmitting and receiving beamforming vectors. An interference space was spanned by the left singular vectors of the entire interference users in the same channel. The most suitable user lay in the OCS of the interference space was scheduled to avoid suffering interference from neighboring cells based on the criterion of system capacity maximizing and proportional fairness. The simulation results show that the average system capacity can be improved by 2%-4% compared with the DS-OCS algorithm with the Max C/I algorithm,by 6%-10% compared with the DPFS-OCS algorithm with the PF algorithm.

Dynamic thermal management by greedy scheduling algorithm

Chip multiprocessors(CMPs) allow thread level parallelism,thus increasing performance.However,this comes with the cost of temperature problem.CMPs require more power,creating non uniform power map and hotspots.Aiming at this problem,a thread scheduling algorithm,the greedy scheduling algorithm,was proposed to reduce the thermal emergencies and to improve the throughput.The greedy scheduling algorithm was implemented in the Linux kernel on Intel's Quad-Core system.The experimental results show that the greedy scheduling algorithm can reduce 9.6%-78.5% of the hardware dynamic thermal management(DTM) in various combinations of workloads,and has an average of 5.2% and up to 9.7% throughput higher than the Linux standard scheduler.

Study on simulation and scheduling algorithm of CAN control for independently driving electric vehicle

Safety-critical applications such as the independently driving systems of electric vehicle （EV） require a high degree of reliability. The controller area network （CAN） is used extensively in the control sectors. A new real-time and reliable scheduling algorithm based on time-triggered scheduler with a focus on the CAN-based distributed control systems for independently driving EV is exploited. A distributed control network model for a dual-wheel independendy driving EV is established. The timing and reliabili- ty analysis in the worst case with the algorithm is used to evaluate the predictability and dependability and the simulation based on the algorithm with CANoe software is designed. The results indicate the algorithm is more predicable and dependable.

A NEW SCHEDULING ALGORITHM TO PROVIDE PROPORTIONAL QOS IN OPTICAL BURST SWITCHING NETWORKS

A new scheduling algorithm, which aims to provide proportional and controllable QoS (Quality of Service) in terms of burst loss probability for OBS (Optical Burst Switching) networks, is proposed on the ba- sis of a survey of QoS schemes in current OBS networks. With simulations, performance analysis and com- parisons are carried out in detail. The results show that, in the proposed scheme, burst loss probabilities are proportional to the given factors and the control of QoS performance can be achieved with better performance. This scheme will be beneficial to the OBS network management and the tariff policy making.

Genetic algorithm for short-term scheduling of make-and-pack batch production process

This paper considers a scheduling problem in industrial make-and-pack batch production process. This process equips with sequence-dependent changeover time, multipurpose storage units with limited capacity, storage time, batch splitting, partial equipment connectivity and transfer time. The objective is to make a production plan to satisfy all constraints while meeting demand requirement of packed products from various product families. This problem is NP-hard and the problem size is exponentially large for a realistic-sized problem. Therefore,we propose a genetic algorithm to handle this problem. Solutions to the problems are represented by chromosomes of product family sequences. These sequences are decoded to assign the resource for producing packed products according to forward assignment strategy and resource selection rules. These techniques greatly reduce unnecessary search space and improve search speed. In addition, design of experiment is carefully utilized to determine appropriate parameter settings. Ant colony optimization and Tabu search are also implemented for comparison. At the end of each heuristics, local search is applied for the packed product sequence to improve makespan. In an experimental analysis, all heuristics show the capability to solve large instances within reasonable computational time. In all problem instances, genetic algorithm averagely outperforms ant colony optimization and Tabu search with slightly longer computational time.

Improved Disk Scheduling Algorithms Based on Rotational Position

As increase of disk access speed has far lagged the speed of processors and main memory, disk-scheduling performance, although less significant for personal users with dedicated storage, is crucial for internet-based intensive data processing. For modern disks, increase of disk rotation rate makes overhead of disk access to data transfer heavier. Therefore, it seems more important to improve both parallel processing capability of disk I/O and disk-scheduling performance at the same time. For disk-scheduling algorithms based on both disk arm and rotational positions, their time-resolving powers are more precise in comparison with those for disk-scheduling algorithms based only on disk arm position. Algorithms of this sort are studied in this paper. Several improved algorithms based on rotational position are proposed, and simulation results of their performances demonstrate.