Minimizing total weighted tardiness on a batch-processing machine with non-agreeable release times and due dates

This study considers the scheduling problem observed in the burn-in operation of semiconductor final testing, where jobs are associated with release times, due dates, processing times, sizes, and non-agreeable release times and due dates. The burn-in oven is modeled as a batch-processing machine which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity and the processing time of a batch is equal to the longest time among all the jobs in the batch. Due to the importance of on-time delivery in semiconductor manufacturing, the objective measure of this problem is to minimize total weighted tardiness. We have formulated the scheduling problem into an integer linear programming model and empirically show its computational intractability. Due to the computational intractability, we propose a few simple greedy heuristic algorithms and meta-heuristic algorithm, simulated annealing (SA). A series of computational experiments are conducted to evaluate the performance of the proposed heuristic algorithms in comparison with exact solution on various small-size problem instances and in comparison with estimated optimal solution on various real-life large size problem instances. The computational results show that the SA algorithm, with initial solution obtained using our own proposed greedy heuristic algorithm, consistently finds a robust solution in a reasonable amount of computation time.

Pickup and delivery problem using metaheuristics techniques

Dial-a-ride problem (DARP) is an optimization problem which deals with the minimization of the cost of the provided service where the customers are provided a door-to-door service based on their requests. This optimization model presented in earlier studies, is considered in this study. Due to the non-linear nature of the objective function the traditional optimization methods are plagued with the problem of converging to a local minima. To overcome this pitfall we use metaheuristics namely Simulated Annealing (SA), Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and Artificial Immune System (AIS). From the results obtained, we conclude that Artificial Immune System method effectively tackles this optimization problem by providing us with optimal solutions. Crown Copyright (C) 2011 Published by Elsevier Ltd. All rights reserved.

Experiments on three-dimensional wire-frame object recognition

Some experimental results on the recognition of three-dimensional wire-frame objects are presented. In order to overcome the limitations of a recent model, which employs radial basis functions-based neural networks, we have proposed a hybrid learning system for object recognition, featuring: an optimization strategy (simulated annealing) in order to avoid local minima of an energy functional; and an appropriate choice of centers of the units. Further, in an attempt to achieve improved generalization ability, and to reduce the time for training, we invoke the principle of self-organization which utilises an unsupervised learning algorithm.

A stochastic dynamical system for image segmentation

Image segmentation is formulated as a stochastic process whose invariant distribution is concentrated at points of the desired region. By choosing multiple seed points, different regions can be segmented. The algorithm is based on the theory of time-homogeneous Markov chains and has been largely motivated by the technique of simulated annealing. The method proposed here has been found to perform well on real-world clean as well as noisy images while being computationally far less expensive than stochastic optimisation techniques

Developing alternatives for optimal representation of seafloor habitats and associated communities in Stellwagen Bank National Marine Sanctuary

The implementation of various types of marine protected areas is one of several management tools available for conserving representative examples of the biological diversity within marine ecosystems in general and National Marine Sanctuaries in particular. However, deciding where and how many sites to establish within a given area is frequently hampered by incomplete knowledge of the distribution of organisms and an understanding of the potential tradeoffs that would allow planners to address frequently competing interests in an objective manner. Fortunately, this is beginning to change. Recent studies on the continental shelf of the northeastern United States suggest that substrate and water mass characteristics are highly correlated with the composition of benthic communities and may therefore, serve as proxies for the distribution of biological biodiversity. A detailed geo-referenced interpretative map of major sediment types within Stellwagen Bank National Marine Sanctuary (SBNMS) has recently been developed, and computer-aided decision support tools have reached new levels of sophistication. We demonstrate the use of simulated annealing, a type of mathematical optimization, to identify suites of potential conservation sites within SBNMS that equally represent 1) all major sediment types and 2) derived habitat types based on both sediment and depth in the smallest amount of space. The Sanctuary was divided into 3610 0.5 min2 sampling units. Simulations incorporated constraints on the physical dispersion of sampling units to varying degrees such that solutions included between one and four site clusters. Target representation goals were set at 5, 10, 15, 20, and 25 percent of each sediment type, and 10 and 20 percent of each habitat type. Simulations consisted of 100 runs, from which we identified the best solution (i.e., smallest total area) and four nearoptimal alternates. We also plotted total instances in which each sampling unit occurred in solution sets of the 100 runs as a means of gauging the variety of spatial configurations available under each scenario. Results suggested that the total combined area needed to represent each of the sediment types in equal proportions was equal to the percent representation level sought. Slightly larger areas were required to represent all habitat types at the same representation levels. Total boundary length increased in direct proportion to the number of sites at all levels of representation for simulations involving sediment and habitat classes, but increased more rapidly with number of sites at higher representation levels. There were a large number of alternate spatial configurations at all representation levels, although generally fewer among one and two versus three- and four-site solutions. These differences were less pronounced among simulations targeting habitat representation, suggesting that a similar degree of flexibility is inherent in the spatial arrangement of potential protected area systems containing one versus several sites for similar levels of habitat representation. We attribute these results to the distribution of sediment and depth zones within the Sanctuary, and to the fact that even levels of representation were sought in each scenario. (PDF contains 33 pages.)

Multiple quasi-phase-matching for enhanced generation of selected high harmonics in aperiodic modulated fibers

A technique for enhanced generation of selected high harmonics in a gas medium, in a high ionization limit, is proposed in this paper. An aperiodically corrugated hollow-core fiber is employed to modulate the intensity of the fundamental laser pulse along the direction of propagation, resulting in multiple quasi-phase-matched high harmonic emissions at the cutoff region. Simulated annealing (SA) algorithm is applied for optimizing the aperiodic hollow-core fiber. Our simulation shows that the yield of selected harmonics is increased equally by up to 2 orders of magnitude compared with no modulation and this permits flexible control of the quasi-phase-matched emission of selected harmonics by appropriate corrugation. (c) 2007 Optical Society of America.

Far-field spot compression without energy loss in main lob in wireless laser communication

Far-field spot compression without energy loss in main lob is of great significance to wireless laser communication. In this letter, we propose two schemes to obtain far-field spot compression without energy loss in main lob. One scheme is based on the simulated annealing (SA) algorithm. Using SA algorithm, we design the phase profile of the diffractive phase element (DPE). Using the designed DPE, far-field spot compression without energy loss in main lob is achieved. The other scheme is based on YG algorithm. By means of YG algorithm, we appropriately designed the DPE in the emitting plane. Using the DPE, far-field spot compression without energy loss in main lob is obtained. (c) 2007 Elsevier GmbH. All rights reserved.

A metal-mirror-based reflecting polarizing beam splitter

We theoretically investigated the design of a metal-mirror-based reflecting polarizing beam splitter (RPBS). The metal mirror is a silver slab, which is embedded in the substrate of a rectangular silica transmission grating. By using a modal analysis and rigorous coupled-wave analysis, an RPBS grating is designed for operation at 1550 nm. When it is illuminated in Littrow mounting, the transverse electric (TE) and transverse magnetic (TM) waves will be mainly reflected in the minus-first and zeroth orders, respectively. Moreover, a wideband RPBS grating is obtained by adopting the simulated annealing algorithm. The RPBS gratings exhibit high diffraction efficiencies (similar to 95%) and high extinction ratios over a certain angle and wavelength range, especially for the minus-first-order reflection. This kind of RPBS should be useful in practical optical applications.

Demonstration of multi-casting in a 1 × 9 LCOS wavelength selective switch

A multi-functional 1 × 9 wavelength selective switch based on liquid crystal on silicon (LCOS) spatial light modulator technology and anamorphic optics was tested at a channel spacing of 100 and 200 GHz, including dynamic data measurements on both single beam deflection and multi-casting to two ports. The multi-casting holograms were optimized using a modified Gerchberg-Saxton routine to design the core hologram, followed by a simulated annealing routine to reduce crosstalk at non-switched ports. The effect of clamping the magnitude of phase changes between neighboring pixels during optimization was investigated, with experimental results for multi-casting to two ports resulting in a signal insertion loss of-7.6 dB normalized to single port deflection, a uniformity of ±0.6%, and a worst case crosstalk of-19.4 dB, which can all be improved further by using a better anti-reflection coating on the LCOS SLM coverplate and other measures. © 2013 IEEE.

Nanoelectronic Circuit Architectures Based on Single-Electron Turnstiles

Single-electron devices (SEDs) have ultra-low power dissipation and high integration density, which make them promising candidates as basic circuit elements of the next generation VLSI circuits. In this paper, we propose two novel circuit single-electron architectures: the single-electron simulated annealing algorithm (SAA) circuit and the single-electron cellular neural network (CNN). We used the MOSFET-based single-electron turnstile [1] as the basic circuit element. The SAA circuit consists of the voltage-controlled single-electron random number generator [2] and the single-electron multiple-valued memories (SEMVs) [3]. The random-number generation and variable variations in SAA are easily achieved by transferring electrons using the single-electron turnstile. The CNN circuit used the floating-gate single-electron turnstile as the neural synapses, and the number of electrons is used to represent the cells states. These novel circuits are promising in future nanoscale integrated circuits.

地形可视性分析中观察点设置问题研究

观察点设置问题是地形可视性分析中的一类重要问题，对该问题的研究可以在空间信息辅助决策、通信、旅游、野生动物保护等领域发挥重大作用。本文在对地形可视性分析中观察点设置问题现有研究成果总结和分析基础上对该问题展开深入研究。 首先，针对现有解决方法只从智能算法或地形数据表示方法单一角度进行分析和研究的局限性，提出了一种问题相关的智能算法和数据表示方法相结合的解决问题新框架。该框架考虑了解决观察点设置问题时智能算法的优点和数据表示方式的特点相互配合问题，目的是充分发挥二者各自的优势以提高观察点设置问题解决的准确度与效率。 其次，在深入分析观察点设置问题本身特点的基础上，结合隶属云理论的基本理论和方法，对经典模拟退火算法从退温函数设计、温度产生过程、状态生成过程三方面进行了问题相关的改进，提出了一种适于观察点设置问题的改进模拟退火算法(Improved Simulated Annealing algorithm, ISA)。该算法一方面保持了经典模拟退火算法的稳定倾向特性，保证了算法满足伴随退火温度的不断下降，对恶化的新状态越来越难于接受这一模拟退火算法的最基本特征；另一方面其退火温度的连续性随机变化特性和隐含的“回火升温”过程，则有利于算法有效拒绝恶化解，加速算法收敛，能够更好地满足观察点设置问题对于算法收敛速度的要求。 再次，在分析地形数据的精度、误差等因素对观察点设置问题的解决准确性和解决效率影响程度的基础上，提出了一种基于离散余弦变换的地形数据内插方法(Discrete Cosine Transformation Interpolation method, DCTI)。新方法将传统空域上的地形内插转换到变换域上进行，同时充分利用了离散余弦变换的熵保持特性和能量压缩特性，简化了变换域上的内插过程，提高了地形数据内插的效率和精度。DCTI方法与其他现有典型地形数据内插方法相比，对地形可视性信息获取的准确性和效率影响最小，为平衡观察点设置问题解决过程中时间效率和准确度之间的关系，最终有效地解决观察点设置问题提供了数据基础。 最后，从智能算法和地形数据相结合的角度出发，提出了一种基于ISA和DCTI相结合的观察点设置问题多分辨率处理方法(Multi-Resolution Processing method, MRP)。新方法将模拟退火算法的逐次退火特点和地形数据的多分辨率表示充分结合，达到了发挥算法数据相结合的综合优势的目的。与现有单纯基于模拟退火算法的解决方法相比，在问题解决准确度保持不变的前提下，基于MRP方法的观察点设置问题解决的平均耗时减少85%~95%，为实际工程应用问题的解决提供了一条重要途径。

Three dimensional solution structure of neurotoxin CM-11 from the Ophiophagus hannah

The Ophiophagus hannah (King Cobra) neurotoxin CM-11 is a small protein with 72 amino acid residues, Based on complete assignments of H-1-NMR resonances and determination of secondary structures of CM-11, 349 distance and 27 dihedral angle constraints including 19 phi's and 8 chi's were collected from NOESY and DQF-COSY , and the chemical stereospecific assignment of beta(1)H was partially achieved, Twelve structures with lower energy was obtained via metric matrix distance geometry and refinement with simulated annealing, These structures have a low RMSD of 0.14 nm for backbone atoms and 0.20 nm for heavy atoms, with no distance constraint violation more than 0.05 nm, and no dihedral angle violation more than 3 degrees.

青藏高原及邻区面波频散反演--岩石圈-软流层体系结构研究

The Qinghai-Tibet Plateau lies in the place of the continent-continent collision between Indian and Eurasian plates. Because of their interaction the shallow and deep structures are very complicated. The force system forming the tectonic patterns and driving tectonic movements is effected together by the deep part of the lithosphere and the asthenosphere. It is important to study the 3-D velocity structures, the spheres and layers structures, material properties and states of the lithosphere and the asthenosphere for getting knowledge of their formation and evolution, dynamic process, layers coupling and exchange of material and energy. Based on the Rayleigh wave dispersion theory, we study the 3-D velocity structures, the depths of interfaces and thicknesses of different layers, including the crust, the lithosphere and the asthenosphere, the lithosphere-asthenosphere system in the Qinghai-Tibet Plateau and its adjacent areas. The following tasks include: (1)The digital seismic records of 221 seismic events have been collected, whose magnitudes are larger than 5.0 over the Qinghai-Tibet Plateau and its adjacent areas. These records come from 31 digital seismic stations of GSN , CDSN、NCDSN and part of Indian stations. After making instrument response calibration and filtering, group velocities of fundamental mode of Rayleigh waves are measured using the frequency-time analysis (FTAN) to get the observed dispersions. Furthermore, we strike cluster average for those similar ray paths. Finally, 819 dispersion curves (8-150s) are ready for dispersion inversion. (2)From these dispersion curves, pure dispersion data in 2°×2° cells of the areas (18°N-42°N, 70°E-106°E) are calculated by using function expansion method, proposed by Yanovskaya. The average initial model has been constructed by taking account of global AK135 model along with geodetic, geological, geophysical, receiving function and wide-angle reflection data. Then, initial S-wave velocity structures of the crust and upper mantle in the research areas have been obtained by using linear inversion (SVD) method. (3)Taking the results of the linear inversion as the initial model, we simultaneously invert the S wave velocities and thicknesses by using non-linear inversion (improved Simulated Annealing algorithm). Moreover, during the temperature dropping the variable-scale models are used. Comparing with the linear results, the spheres and layers by the non-linear inversion can be recognized better from the velocity value and offset. (4)The Moho discontinuity and top interface of the asthenosphere are recognized from the velocity value and offset of the layers. The thicknesses of the crust, lithosphere and asthenosphere are gained. These thicknesses are helpful to studying the structural differentia between the Qinghai-Tibet Plateau and its adjacent areas and among geologic units of the plateau. The results of the inversion will provide deep geophysical evidences for studying deep dynamical mechanism and exploring metal mineral resource and oil and gas resources. The following conclusions are reached by the distributions of the S wave velocities and thicknesses of the crust, lithosphere and asthenosphere, combining with previous researches. (1)The crust is very thick in the Qinghai-Tibet Plateau, varying from 60 km to 80 km. The lithospheric thickness in the Qinghai-Tibet Plateau is thinner (130-160 km) than its adjacent areas. Its asthenosphere is relatively thicker, varies from 150 km to 230 km, and the thickest area lies in the western Qiangtang. India located in south of Main Boundary thrust has a thinner crust (32-38 km), a thicker lithosphere of about 190 km and a rather thin asthenosphere of only 60 km. Sichuan and Tarim basins have the crust thickness less than 50km. Their lithospheres are thicker than the Qinghai-Tibet Plateau, and their asthenospheres are thinner. (2)The S-wave velocity variation pattern in the lithosphere-asthenosphere system has band-belted distribution along east-westward. These variations correlate with geology structures sketched by sutures and major faults. These sutures include Main Boundary thrust (MBT), Yarlung-Zangbo River suture (YZS), Bangong Lake-Nujiang suture (BNS), Jinshajiang suture (JSJS), Kunlun edge suture (KL). In the velocity maps of the upper and middle crust, these sutures can be sketched. In velocity maps of 250-300 km depth, MBT, BNS and JSJS can be sketched. In maps of the crustal thickness, the lithospheric thickness and the asthenospheric thickness, these sutures can be still sketched. In particular, MBT can be obviously resolved in these velocity maps and thickness maps. (3)Since the collision between India and Eurasian plate, the “loss” of surface material arising from crustal shortening is caused not only by crustal thickening but also by lateral extrusion material. The source of lateral extrusion lies in the Qiangtang block. These materials extrude along the JSJS and BNS with both rotation and dispersion in Daguaiwan. Finally, it extends toward southeast direction. (4)There is the crust-mantle transition zone of no distinct velocity jump in the lithosphere beneath the Qiangtang Terrane. It has thinner lithosphere and developed thicker asthenosphere. It implies that the crust-mantle transition zone of partial melting is connected with the developed asthenosphere. The underplating of asthenosphere may thin the lithosphere. This buoyancy might be the main mechanism and deep dynamics of the uplift of the Qinghai-Tibet hinterland. At the same time, the transport of hot material with low velocity intrudes into the upper mantle and the lower crust along cracks and faults forming the crust-mantle transition zone.