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.

Distributed load adaptive scheduling for throughput and delay guarantees in fading wireless LANs

We consider a problem of providing mean delay and average throughput guarantees in random access fading wireless channels using CSMA/CA algorithm. This problem becomes much more challenging when the scheduling is distributed as is the case in a typical local area wireless network. We model the CSMA network using a novel queueing network based approach. The optimal throughput per device and throughput optimal policy in an M device network is obtained. We provide a simple contention control algorithm that adapts the attempt probability based on the network load and obtain bounds for the packet transmission delay. The information we make use of is the number of devices in the network and the queue length (delayed) at each device. The proposed algorithms stay within the requirements of the IEEE 802.11 standard.

Evolving Random Geometric Graph Models for Mobile Wireless Networks

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

Influence of Spatial Scales on the Performance of Saturated Subsurface Flow and Transport Models

Numerical modeling of saturated subsurface flow and transport has been widely used in the past using different numerical schemes such as finite difference and finite element methods. Such modeling often involves discretization of the problem in spatial and temporal scales. The choice of the spatial and temporal scales for a modeling scenario is often not straightforward. For example, a basin-scale saturated flow and transport analysis demands larger spatial and temporal scales than a meso-scale study, which in turn has larger scales compared to a pore-scale study. The choice of spatial-scale is often dictated by the computational capabilities of the modeler as well as the availability of fine-scale data. In this study, we analyze the impact of different spatial scales and scaling procedures on saturated subsurface flow and transport simulations.

Scheduling a Burn-In Oven with Non-Agreeable Release Times and Due Dates

We consider the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modelled as batch processing machines. Most of the studies assume that ready times and due dates of jobs are agreeable (i.e., ri < rj implies di ≤ dj). In many real world applications, the agreeable property assumption does not hold. Therefore, in this paper, scheduling of a single burn-in oven with non-agreeable release times and due dates along with non-identical job sizes as well as non-identical processing of time problem is formulated as a Non-Linear (0-1) Integer Programming optimisation problem. The objective measure of the problem is minimising the maximum completion time (makespan) of all jobs. Due to computational intractability, we have proposed four variants of a two-phase greedy heuristic algorithm. Computational experiments indicate that two out of four proposed algorithms have excellent average performance and also capable of solving any large-scale real life problems with a relatively low computational effort on a Pentium IV computer.

Inverse models to analyze the spatiotemporal variations of chemical weathering fluxes in a granito-gneissic watershed: Mule Hole, South India

Water-rock reactions are driven by the influx of water, which are out of equilibrium with the mineral assemblage in the rock. Here a mass balance approach is adopted to quantify these reactions. Based on field experiments carried out in a granito-gneissic small experimental watershed (SEW), Mule Hole SEW (similar to 4.5 km(2)), quartz, oligoclase, sericite, epidote and chlorite are identified as the basic primary minerals while kaolinite, goethite and smectite are identified as the secondary minerals. Observed groundwater chemistry is used to determine the weathering rates, in terms of `Mass Transfer Coefficients' (MTCs), of both primary and secondary minerals. Weathering rates for primary and secondary minerals are quantified in two steps. In the first step, top red soil is analyzed considering precipitation chemistry as initial phase and water chemistry of seepage flow as final phase. In the second step, minerals present in the saprolite layer are analyzed considering groundwater chemistry as the output phase. Weathering rates thus obtained are converted into weathering fluxes (Q(weathering)) using the recharge quantity. Spatial variability in the mineralogy observed among the thirteen wells of Mule Hole SEW is observed to be reflected in the MTC results and thus in the weathering fluxes. Weathering rates of the minerals in this silicate system varied from few 10 mu mol/L (in case of biotite) to 1000 s of micromoles per liter (calcite). Similarly, fluxes of biotite are observed to be least (7 +/- 5 mol/ha/yr) while those of calcite are highest (1265 791 mol/ha/yr). Further, the fluxes determined annually for all the minerals are observed to be within the bandwidth of the standard deviation of these fluxes. Variations in these annual fluxes are indicating the variations in the precipitation. Hence, the standard deviation indicated the temporal variations in the fluxes, which might be due to the variations in the annual rainfall. Thus, the methodology adopted defines an inverse way of determining weathering fluxes, which mainly contribute to the groundwater concentration. (C) 2011 Elsevier B.V. All rights reserved.

An Accurate Model for EESM and its Application to Analysis of CQI Feedback Schemes and Scheduling in LTE

The Effective Exponential SNR Mapping (EESM) is an indispensable tool for analyzing and simulating next generation orthogonal frequency division multiplexing (OFDM) based wireless systems. It converts the different gains of multiple subchannels, over which a codeword is transmitted, into a single effective flat-fading gain with the same codeword error rate. It facilitates link adaptation by helping each user to compute an accurate channel quality indicator (CQI), which is fed back to the base station to enable downlink rate adaptation and scheduling. However, the highly non-linear nature of EESM makes a performance analysis of adaptation and scheduling difficult; even the probability distribution of EESM is not known in closed-form. This paper shows that EESM can be accurately modeled as a lognormal random variable when the subchannel gains are Rayleigh distributed. The model is also valid when the subchannel gains are correlated in frequency or space. With some simplifying assumptions, the paper then develops a novel analysis of the performance of LTE's two CQI feedback schemes that use EESM to generate CQI. The comprehensive model and analysis quantify the joint effect of several critical components such as scheduler, multiple antenna mode, CQI feedback scheme, and EESM-based feedback averaging on the overall system throughput.

Low-Complexity Detection in Large-Dimension MIMO-ISI Channels Using Graphical Models

In this paper, we deal with low-complexity near-optimal detection/equalization in large-dimension multiple-input multiple-output inter-symbol interference (MIMO-ISI) channels using message passing on graphical models. A key contribution in the paper is the demonstration that near-optimal performance in MIMO-ISI channels with large dimensions can be achieved at low complexities through simple yet effective simplifications/approximations, although the graphical models that represent MIMO-ISI channels are fully/densely connected (loopy graphs). These include 1) use of Markov random field (MRF)-based graphical model with pairwise interaction, in conjunction with message damping, and 2) use of factor graph (FG)-based graphical model with Gaussian approximation of interference (GAI). The per-symbol complexities are O(K(2)n(t)(2)) and O(Kn(t)) for the MRF and the FG with GAI approaches, respectively, where K and n(t) denote the number of channel uses per frame, and number of transmit antennas, respectively. These low-complexities are quite attractive for large dimensions, i.e., for large Kn(t). From a performance perspective, these algorithms are even more interesting in large-dimensions since they achieve increasingly closer to optimum detection performance for increasing Kn(t). Also, we show that these message passing algorithms can be used in an iterative manner with local neighborhood search algorithms to improve the reliability/performance of M-QAM symbol detection.

Joint Performance Analysis of Channel Quality Indicator Feedback Schemes and Frequency-Domain Scheduling for LTE

Frequency-domain scheduling and rate adaptation enable next-generation orthogonal frequency-division multiple access (OFDMA) cellular systems such as Long-Term Evolution (LTE) to achieve significantly higher spectral efficiencies. LTE uses a pragmatic combination of several techniques to reduce the channel-state feedback that is required by a frequency-domain scheduler. In the subband-level feedback and user-selected subband feedback schemes specified in LTE, the user reduces feedback by reporting only the channel quality that is averaged over groups of resource blocks called subbands. This approach leads to an occasional incorrect determination of rate by the scheduler for some resource blocks. In this paper, we develop closed-form expressions for the throughput achieved by the feedback schemes of LTE. The analysis quantifies the joint effects of three critical components on the overall system throughput-scheduler, multiple-antenna mode, and the feedback scheme-and brings out its dependence on system parameters such as the number of resource blocks per subband and the rate adaptation thresholds. The effect of the coarse subband-level frequency granularity of feedback is captured. The analysis provides an independent theoretical reference and a quick system parameter optimization tool to an LTE system designer and theoretically helps in understanding the behavior of OFDMA feedback reduction techniques when operated under practical system constraints.

Carnatic music analysis: Shadja, swara identification and rAga verification in AlApana using stochastic models

We analyze the AlApana of a Carnatic music piece without the prior knowledge of the singer or the rAga. AlApana is ameans to communicate to the audience, the flavor or the bhAva of the rAga through the permitted notes and its phrases. The input to our analysis is a recording of the vocal AlApana along with the accompanying instrument. The AdhAra shadja(base note) of the singer for that AlApana is estimated through a stochastic model of note frequencies. Based on the shadja, we identify the notes (swaras) used in the AlApana using a semi-continuous GMM. Using the probabilities of each note interval, we recognize swaras of the AlApana. For sampurNa rAgas, we can identify the possible rAga, based on the swaras. We have been able to achieve correct shadja identification, which is crucial to all further steps, in 88.8% of 55 AlApanas. Among them (48 AlApanas of 7 rAgas), we get 91.5% correct swara identification and 62.13% correct R (rAga) accuracy.