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.

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.

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.

Low complexity resource allocation and scheduling algorithms for downlink SDMA systems

The downlink zero-forcing beamforming strategy in the case of random packet arrivals is investigated. Under this setting, the relevant fairness criterion is the stabilization of all buffer queues which guarantees a bounded average delay for all users. It has been shown that allocating resources to maximize a queue-length-weighted sum of the rates is a stabilizing policy. However, the high complexity of user selection and the feasible rates determination for optimal scheme may prevent the real-time scheduling operation. Two low complexity algorithms are provided taking the channel state, queue state and orthogonality into account. In particular, the authors pick the first user with the largest product between channel gain and queuing length, and select the remaining users to construct candidate user set based on the greedy user selection method or channel orthogonal user selection method. Then, the power and rate allocation for the selected users are implemented based on the modified water-filling method. The complexity of the proposed algorithms is analyzed. The average delay and average throughput are studied in homogeneous scenarios and heterogeneous scenarios, respectively. Simulation results show that the proposed algorithms can take full advantage of the multi-user diversity gain and provide average delay （or throughput） and fairness improvement compared with channel-aware-only schemes.

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.

Information gain based sensor search scheduling for low-earth orbit constellation estimation

This paper addresses the problem of sensor search scheduling in the complicated space environment faced by the low-earth orbit constellation.Several search scheduling methods based on the commonly used information gain are compared via simulations first.Then a novel search scheduling method in the scenarios of uncertainty observation is proposed based on the global Shannon information gain and beta density based uncertainty model.Simulation results indicate that the beta density model serves a good option for solving the problem of target acquisition in the complicated space environments.

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.

Application-adaptive resource scheduling in a computational grid

Selecting appropriate resources for running a job efficiently is one of the common objectives in a computational grid. Resource scheduling should consider the specific characteristics of the application, and decide the metrics to be used accordingly. This paper presents a distributed resource scheduling framework mainly consisting of a job scheduler and a local scheduler. In order to meet the requirements of different applications, we adopt HGSA, a Heuristic-based Greedy Scheduling Algorithm, to schedule jobs in the grid, where the heuristic knowledge is the metric weights of the computing resources and the metric workload impact factors. The metric weight is used to control the effect of the metric on the application. For different applications, only metric weights and the metric workload impact factors need to be changed, while the scheduling algorithm remains the same. Experimental results are presented to demonstrate the adaptability of the HGSA.

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.

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.

Multi-objective modeling and optimization for scheduling of cracking furnace systems

Cracking furnace is the core device for ethylene production. In practice, multiple ethylene furnaces are usually run in parallel. The scheduling of the entire cracking furnace system has great significance when multiple feeds are simultaneously processed in multiple cracking furnaces with the changing of operating cost and yield of product. In this paper, given the requirements of both profit and energy saving in actual production process, a multi-objective optimization model contains two objectives, maximizing the average benefits and minimizing the average coking amount was proposed. The model can be abstracted as a multi-objective mixed integer non- linear programming problem. Considering the mixed integer decision variables of this multi-objective problem, an improved hybrid encoding non-dominated sorting genetic algorithm with mixed discrete variables （MDNSGA-II） is used to solve the Pareto optimal front of this model, the algorithm adopted crossover and muta- tion strategy with multi-operators, which overcomes the deficiency that normal genetic algorithm cannot handle the optimization problem with mixed variables. Finally, using an ethylene plant with multiple cracking furnaces as an example to illustrate the effectiveness of the scheduling results by comparing the optimization results of multi-objective and single objective model.

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.

DYNAMIC ADVANCED PLANNING AND SCHEDULING WITH FROZEN INTERVAL FOR NEW ORDERS

A dynamic advanced planning and scheduling （DAPS） problem is addressed where new orders arrive on a continuous basis. A periodic policy with frozen interval is adopted to increase stability on the shop floor. A genetic algorithm is developed to find a schedule at each rescheduling point for both original orders and new orders that both production idle time and penalties on tardiness and earliness of orders are minimized. The proposed methodology is tested on a small example to illustrate the effect of the frozen interval. The results indicate that the suggested approach can improve the schedule stability while retaining efficiency.

Utility-Based Joint Scheduling Approach Supporting Multiple Services for Co MP-SUMIMO in LTE-A System

In this paper, we study utilitybased resource allocation for users supporting multiple services in a LTEA system with coordinated multipoint transmission for singleuser multiinput multioutput （CoMPSUMIMO）. We designed Joint Transmission Power Control （JTPC） for the selected clusters for minimizing power consumption in LTEA systems. The objective of JTPC is to calculate the optimal transmission power for each scheduled user and subcarrier. Moreover, based on the convex optimization theory, we propose the dynamic sector selection method in which the average sector throughput and celledge users （UEs） rates are performed to achieve the optimal solution. Simulation results show that the system performance achieved by using the proposed suboptimal algorithm is close to that achieved by the dual decomposition method.

Coordinate scheduling approach for EDS observation tasks and data transmission jobs

Electromagnetic detection satellite（EDS） is a type of Earth observation satellite（EOS）. Satellites observation and data down-link scheduling plays a significant role in improving the efficiency of satellite observation systems. However, the current works mainly focus on the scheduling of imaging satellites, little work focuses on the scheduling of EDSes for its specific requirements.And current works mainly schedule satellite resources and data down-link resources separately, not considering them in a globally optimal perspective. The EDSes and data down-link resources are scheduled in an integrated process and the scheduling result is searched globally. Considering the specific constraints of EDS, a coordinate scheduling model for EDS observation tasks and data transmission jobs is established and an algorithm based on the genetic algorithm is proposed. Furthermore, the convergence of our algorithm is proved. To deal with some specific constraints, a solution repairing algorithm of polynomial computing time is designed. Finally, some experiments are conducted to validate the correctness and practicability of our scheduling algorithms.

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%.

Rule-based scheduling of multi-stage multi-product batch plants with parallel units

A novel rule-based model for multi-stage multi-product scheduling problem(MMSP)in batch plants with parallel units is proposed.The scheduling problem is decomposed into two sub-problems of order assignment and order sequencing.Firstly,hierarchical scheduling strategy is presented for solving the former sub-problem,where the multi-stage multi-product batch process is divided into multiple sequentially connected single process stages,and then the production of orders are arranged in each single stage by using forward order assignment strategy and backward order assignment strategy respectively according to the feature of scheduling objective.Line-up competition algorithm(LCA)is presented to find out optimal order sequence and order assignment rule,which can minimize total flow time or maximize total weighted process time.Computational results show that the proposed approach can obtain better solutions than those of the literature for all scheduling problems with more than 10 orders.Moreover,with the problem size increasing,the solutions obtained by the proposed approach are improved remarkably.The proposed approach has the potential to solve large size MMSP.