Adaptive subsequence adjustment with evolutionary asymmetric path-relinking for TDRSS scheduling

Due to the limited transmission resources for data relay in the tracking and data relay satellite system （TDRSS）, there are many job requirements in busy days which will be discarded in the conventional job scheduling model. Therefore, the improvement of scheduling efficiency in the TDRSS can not only help to increase the resource utilities, but also to reduce the scheduling failure ratio. A model of nonhomogeneous parallel machines scheduling problems with time window （NPM-TW） is firstly built up for the TDRSS, considering the distinct features of the variable preparation time and the nonhomogeneous transmission rates for different types of antennas on each tracking and data relay satellite （TDRS）. Then, an adaptive subsequence adjustment （ASA） framework with evolutionary asymmetric path-relinking （EvAPR） is proposed to solve this problem, in which an asymmetric progressive crossover operation is involved to overcome the local optima by the conventional job inserting methods. The numerical results show that, compared with the classical greedy randomized adaptive search procedure （GRASP） algorithm, the scheduling failure ratio of jobs can be reduced over 11% on average by the proposed ASA with EvAPR.

Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.

Implementation and Evaluation of Dynamically Weighted Low Complexity Fair Queuing(DWLC-FQ) Algorithm for Packet Scheduling in WiMAX Networks

Services provided by internet need guaranteed network performance. Efficient packet queuing and scheduling schemes play key role in achieving this. Internet engineering task force(IETF) has proposed Differentiated Services(Diff Serv) architecture for IP network which is based on classifying packets in to different service classes and scheduling them. Scheduling schemes of today's wireless broadband networks work on service differentiation. In this paper, we present a novel packet queue scheduling algorithm called dynamically weighted low complexity fair queuing(DWLC-FQ) which is an improvement over weighted fair queuing(WFQ) and worstcase fair weighted fair queuing+(WF2Q+). The proposed algorithm incorporates dynamic weight adjustment mechanism to cope with dynamics of data traffic such as burst and overload. It also reduces complexity associated with virtual time update and hence makes it suitable for high speed networks. Simulation results of proposed packet scheduling scheme demonstrate improvement in delay and drop rate performance for constant bit rate and video applications with very little or negligible impact on fairness.

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.

Generalized multiple time windows model based parallel machine scheduling for TDRSS

The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites（TDRSs）.In this paper,ageneralized multiple time windows（GMTW）model is proposed to fully exploit the time and spatial DoF.Then,the improvements of service capability and job-completion probability based on the GMTW are theoretically proved.Further,an asymmetric path-relinking（APR）based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW.Simulation results show that by using our proposal 11%improvement of average jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.

Statistics and Analysis on Reliability of HVDC Transmission Systems of SGCC

Reliability level of HVDC power transmission systems becomes an important factor impacting the entire power grid.The author analyzes the reliability of HVDC power transmission systems owned by SGCC since 2003 in respect of forced outage times,forced energy unavailability,scheduled energy unavailability and energy utilization eff iciency.The results show that the reliability level of HVDC power transmission systems owned by SGCC is improving.By analyzing different reliability indices of HVDC power transmission system,the maximum asset benef its of power grid can be achieved through building a scientif ic and reasonable reliability evaluation system.

SEMI-DEFINITE RELAXATION ALGORITHM FOR SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES

The authors present a semi-definite relaxation algorithm for the scheduling problem with controllable times on a single machine. Their approach shows how to relate this problem with the maximum vertex-cover problem with kernel constraints (MKVC).The established relationship enables to transfer the approximate solutions of MKVCinto the approximate solutions for the scheduling problem. Then, they show how to obtain an integer approximate solution for MKVC based on the semi-definite relaxation and randomized rounding technique.

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Stochastic dynamic job shop scheduling pro- blem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time （SIMSET） rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date （JMEDD） rule provides the best performance for make- span, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.