On the use of different types of knowledge in metaheuristics based on constructing solutions

Many metaheuristics are either based on neighborhood search or the construction of solutions. Examples for the latter ones include ant colony optimization and greedy randomized adaptive search procedures. These techniques generally construct solutions probabilistically by sampling a probability distribution over the search space. Solution constructions are generally independent from each other. Recent algorithmic variants include two important features that are inspired by deterministic branch and bound derivatives such as beam search: the use of bounds for evaluating partial solutions, and the parallel and non-independent construction of solutions. In this paper we give a theoretical reason of why these algorithms generally work very well in practice. Second, we confirm our theoretical findings by means of practical examples. After the application to artificial problems, we present experimental results concerning the well-known open shop scheduling problem.     

Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

In this paper we study the single machine precedence constrained scheduling problem of minimizing the sum of weighted completion time. Specifically, we settle an open problem first raised by Chudak and Hochbaum and whose answer was subsequently conjectured by Correa and Schulz. As shown by Correa and Schulz, the proof of this conjecture implies that the addressed scheduling problem is a special case of the vertex cover problem. This means that previous results for the scheduling problem can be explained, and in some cases improved, by means of vertex cover theory. For example, the conjecture implies the existence of a polynomial time algorithm for the special case of two-dimensional partial orders. This considerably extends Lawler’s result from 1978 for series-parallel orders.     

The consequences of sampling variability on the estimation of wavenumber and propagation direction from spaceborne SAR image spectra

Even if it were true that SAR (synthetic aperture radar) ocean surface imagery provides a perfect noiseless representation of ocean surface wave height, each spectrum computed from such imagery would be but a single realization of the ensemble-mean ocean spectrum. There would be sampling variability associated with the parameters of dominant wave number and propagation direction extracted from such a spectrum. The present study addresses two questions: (i) what statistical distribution is applicable to the spectra of SAR ocean images? and (ii) what are the consequences of such statistics on the precision with which wave number and propagation direction can be extracted? An examination is made of spectra computed from ocean imagery acquired during the SIR-B (Shuttle Imaging Radar-B) mission     

Grouping Techniques for Scheduling Problems: Simpler and Faster

In this paper we describe a general grouping technique to devise faster and simpler approximation schemes for several scheduling problems. We illustrate the technique on two different scheduling problems: scheduling on unrelated parallel machines with costs and the job shop scheduling problem. The time complexity of the resulting approximation schemes is always linear in the number n of jobs, and the multiplicative constant hidden in the O(n) running time is reasonably small and independent of the error ε. Supported by Swiss National Science Foundation project 200020-109854, “Approximation Algorithms for Machine scheduling Through Theory and Experiments II”. A preliminary version of this paper appeared in the Proceedings of ESA’01.     

Notes on Max Flow Time Minimization with Controllable Processing Times

In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the identical parallel machines max flow time minimization problem with controllable processing times. We address the preemptive and non-preemptive version of the problem. For the preemptive case, a linear programming formulation is presented which solves the problem optimally in polynomial time. For the non-preemptive problem it is shown that the First In First Out (FIFO) heuristic has a tight worst-case performance of 3–2/m, when jobs processing times and costs are set as in some optimal preemptive schedule. Supported by Swiss National Science Foundation project 20-63733.00/1, Resource Allocation and Scheduling in Flexible Manufacturing Systems, and by the Metaheuristics Network, grant HPRN-CT-1999-00106.     

A systematic comparison of QuikSCAT and SAR ocean surface wind speeds

We performed a systematic comparison of wind speed measurements from the SeaWinds QuikSCAT scatterometer and wind speeds computed from RADARSAT-1 synthetic aperture radar (SAR) normalized radar cross section measurements. These comparisons were made over in the Gulf of Alaska and extended over a two-year period, 2000 and 2001. The SAR wind speed estimates require a wind direction to initialize the retrieval. Here, we first used wind directions from the Navy Operational Global Atmospheric Prediction System (NOGAPS) model. For these retrievals, the standard deviation between the resulting SAR and QuikSCAT wind speed measurements was 1.78 m/s. When we used the QuikSCAT-measured wind directions to initialize the inversion, comparisons improve to a standard deviation of 1.36 m/s. We used these SAR-scatterometer comparisons to generate a new C-band horizontal polarization model function. With this new model function, the wind speed inversion improves to a standard deviation of 1.24 m/s with no mean bias. These results strongly suggest that SAR and QuikSCAT measurements can be combined to make better high-resolution wind measurements than either instrument could alone in coastal areas.     

Real-time observations of Southern Ocean wave fields from theShuttle Imaging Radar

During the April and October 1994 flights of the space shuttle Endeavour, C-band synthetic-aperture radar (SAR) signal was acquired and processed in real-time into ocean wave images and two-dimensional image spectra by an on-board processor. The image spectra were transmitted to the ground as they were acquired. During 20 days of observations, spanning the two missions, over 100000 spectra were collected. These data provide the first truly synoptic directional measurements of the Southern Ocean wave field. With additional processing, estimates of ocean wavelength and propagation direction were extracted from the spectra. During the October mission, daily comparisons of these estimates with wave model predictions were made available at a World Wide Web site. The authors describe the computations performed by the processor and the real-time data flow and ground processing. In addition, they summarize and interpret some gross characteristics of the processor-observed real-time wave field from the April and October missions     

Comparison of SIR-B SAR wave image spectra with wave modelpredictions: implications on the SAR modulation transfer function

During the Spaceborne Imaging Radar (SIR-B) mission in October 1984, the onboard synthetic aperture radar (SAR) acquired data in the vicinity of Hurricane Josephine. Ocean wave spectra computed from the SAR imagery are compared with Ocean Data Gathering Project (ODGP) model forecasts. Because the apparent propagation direction of the dominant wave system rotated over 90° along the pass, the data set affords a unique opportunity to observe the same wave system as imaged by different SAR mechanisms. It is shown that, for the SIR-B geometry, the wave numbers and propagation directions extracted from the wave spectra are not strongly dependent on the exact nature of the SAR imaging mechanism. However,the estimation of ocean significant wave height (SWH) requires accurate knowledge of such mechanisms. The spatial variation of SWH as estimated from SAR-derived wave spectra and ODGP model spectra compare most favorably when the phase of the hydrodynamic portion of the SAR modulation transfer function is approximately 90° past the long wave crest     

Optical Determination of Short-Wave Modulation by Long Ocean Gravity Waves

Time series short-wave spectra were produced from photographs acquired during the Joint North Sea Waves Project (JONSWAP). The feasibility of using this surface imagery to quantify the nature of short-wave modulation by long waves is demonstrated. Photographically obtained time series spectra are correlated to the long wave slope. The modulation transfer function of short-wave spectral energy versus long wave slope is measured to have a 9(slope)-1 magnitude with a 90° phase at a wind speed of 5 m/s in the short-wave spectral regime between 3 and 30 cm in wavelength. Comparison of these results with measurements by coherent radars and laser slope gauges indicates good agreement in the measured modulation magnitude but significant disagreement in measured phase. Modulation magnitude and phase predicted from the action balance model are shown to be significantly smaller than empiricaly measured results.