Single-machine scheduling with past-sequence-dependent setup times and learning effects: a parametric analysis

In this article, we consider the single-machine scheduling problem with past-sequence-dependent (p-s-d) setup times and a learning effect. The setup times are proportional to the length of jobs that are already scheduled; i.e. p-s-d setup times. The learning effect reduces the actual processing time of a job because the workers are involved in doing the same job or activity repeatedly. Hence, the processing time of a job depends on its position in the sequence. In this study, we consider the total absolute difference in completion times (TADC) as the objective function. This problem is denoted as 1/LE, (Spsd)/TADC in Kuo and Yang (2007) ('Single Machine Scheduling with Past-sequence-dependent Setup Times and Learning Effects', Information Processing Letters, 102, 22-26). There are two parameters a and b denoting constant learning index and normalising index, respectively. A parametric analysis of b on the 1/LE, (Spsd)/TADC problem for a given value of a is applied in this study. In addition, a computational algorithm is also developed to obtain the number of optimal sequences and the range of b in which each of the sequences is optimal, for a given value of a. We derive two bounds b* for the normalising constant b and a* for the learning index a. We also show that, when a < a* or b > b*, the optimal sequence is obtained by arranging the longest job in the first position and the rest of the jobs in short processing time order.

An algorithm for dynamic optimal bandwidth allocation in communication networks

We study the problem of optimal bandwidth allocation in communication networks. We consider a queueing model with two queues to which traffic from different competing flows arrive. The queue length at the buffers is observed every T instants of time, on the basis of which a decision on the amount of bandwidth to be allocated to each buffer for the next T instants is made. We consider a class of closed-loop feedback policies for the system and use a twotimescale simultaneous perturbation stochastic approximation(SPSA) algorithm to find an optimal policy within the prescribed class. We study the performance of the proposed algorithm on a numerical setting. Our algorithm is found to exhibit good performance.

A Simultaneous Deterministic Perturbation Actor-Critic Algorithm with an Application to Optimal Mortgage Refinancing

We develop a simulation-based, two-timescale actor-critic algorithm for infinite horizon Markov decision processes with finite state and action spaces, with a discounted reward criterion. The algorithm is of the gradient ascent type and performs a search in the space of stationary randomized policies. The algorithm uses certain simultaneous deterministic perturbation stochastic approximation (SDPSA) gradient estimates for enhanced performance. We show an application of our algorithm on a problem of mortgage refinancing. Our algorithm obtains the optimal refinancing strategies in a computationally efficient manner

A Predictive Perfomance Model for Superscalar Processors

Designing and optimizing high performance microprocessors is an increasingly difficult task due to the size and complexity of the processor design space, high cost of detailed simulation and several constraints that a processor design must satisfy. In this paper, we propose the use of empirical non-linear modeling techniques to assist processor architects in making design decisions and resolving complex trade-offs. We propose a procedure for building accurate non-linear models that consists of the following steps: (i) selection of a small set of representative design points spread across processor design space using latin hypercube sampling, (ii) obtaining performance measures at the selected design points using detailed simulation, (iii) building non-linear models for performance using the function approximation capabilities of radial basis function networks, and (iv) validating the models using an independently and randomly generated set of design points. We evaluate our model building procedure by constructing non-linear performance models for programs from the SPEC CPU2000 benchmark suite with a microarchitectural design space that consists of 9 key parameters. Our results show that the models, built using a relatively small number of simulations, achieve high prediction accuracy (only 2.8% error in CPI estimates on average) across a large processor design space. Our models can potentially replace detailed simulation for common tasks such as the analysis of key microarchitectural trends or searches for optimal processor design points.

Optimal association of mobile wireless devices with a WLAN-3G access network

In this paper, we consider the problem of association of wireless stations (STAs) with an access network served by a wireless local area network (WLAN) and a 3G cellular network. There is a set of WLAN Access Points (APs) and a set of 3G Base Stations (BSs) and a number of STAs each of which needs to be associated with one of the APs or one of the BSs. We concentrate on downlink bulk elastic transfers. Each association provides each ST with a certain transfer rate. We evaluate an association on the basis of the sum log utility of the transfer rates and seek the utility maximizing association. We also obtain the optimal time scheduling of service from a 3G BS to the associated STAs. We propose a fast iterative heuristic algorithm to compute an association. Numerical results show that our algorithm converges in a few steps yielding an association that is within 1% (in objective value) of the optimal (obtained through exhaustive search); in most cases the algorithm yields an optimal solution.

Tracking performance of an LMS-Linear Equalizer for fading channels

We consider a time varying wireless fading channel, equalized by an LMS linear equalizer. We study how well this equalizer tracks the optimal Wiener equalizer. We model the channel by an Auto-regressive (AR) process. Then the LMS equalizer and the AR process are jointly approximated by the solution of a system of ODEs (ordinary differential equations). Using these ODEs, the error between the LMS equalizer and the instantaneous Wiener filter is shown to decay exponentially/polynomially to zero unless the channel is marginally stable in which case the convergence may not hold.Using the same ODEs, we also show that the corresponding Mean Square Error (MSE) converges towards minimum MSE(MMSE) at the same rate for a stable channel. We further show that the difference between the MSE and the MMSE does not explode with time even when the channel is unstable. Finally we obtain an optimum step size for the linear equalizer in terms of the AR parameters, whenever the error decay is exponential.

Asymptotically optimal cooperative wireless networks without constellation expansion

In this work, we construct a unified family of cooperative diversity coding schemes for implementing the orthogonal amplify-and-forward and the orthogonal selection-decode-and-forward strategies in cooperative wireless networks. We show that, as the number of users increases, these schemes meet the corresponding optimal high-SNR outage region, and do so with minimal order of signaling complexity. This is an improvement over all outage-optimal schemes which impose exponential increases in signaling complexity for every new network user. Our schemes, which are based on commutative algebras of normal matrices, satisfy the outage-related information theoretic criteria, the duplex-related coding criteria, and maintain reduced signaling, encoding and decoding complexities

Optimal location of centre of gravity for swashplateless helicopter UAV and MAV

To investigate the use of centre of gravity location on reducing cyclic pitch control for helicopter UAV's (unmanned air vehicles) and MAV's (micro air vehicles). Low cyclic pitch is a necessity to implement the swashplateless rotor concept using trailing edge flaps or active twist using current generation low authority piezoceramic actuators. Design/methodology/approach – An aeroelastic analysis of the helicopter rotor with elastic blades is used to perform parametric and sensitivity studies of the effects of longitudinal and lateral center of gravity (cg) movements on the main rotor cyclic pitch. An optimization approach is then used to find cg locations which reduce the cyclic pitch at a given forward speed. Findings – It is found that the longitudinal cyclic pitch and lateral cyclic pitch can be driven to zero at a given forward speed by shifting the cg forward and to the port side, respectively. There also exist pairs of numbers for the longitudinal and lateral cg locations which drive both the cyclic pitch components to zero at a given forward speed. Based on these results, a compromise optimal cg location is obtained such that the cyclic pitch is bounded within ±5° for a BO105 helicopter rotor. Originality/value – The reduction in the cyclic pitch due to helicopter cg location is found to significantly reduce the maximum magnitudes of the control angles in flight, facilitating the swashplateless rotor concept. In addition, the existence of cg locations which drive the cyclic pitches to zero allows for the use of active cg movement as a way to replace the cyclic pitch control for helicopter MAV's.