Minimizing total weighted completion time in a proportionate flow shop

We study the special case of the m machine flow shop problem in which the processing time of each operation of job j is equal to pj; this variant of the flow shop problem is known as the proportionate flow shop problem. We show that for any number of machines and for any regular performance criterion we can restrict our search for an optimal schedule to permutation schedules. Moreover, we show that the problem of minimizing total weighted completion time is solvable in O(n2) time. © 1998 John Wiley & Sons, Ltd.

A computational model of coupled heat and moisture transfer with phase change in granular sugar during varying environmental conditions

As part of a comprehensive effort to predict the development of caking in granular materials, a mathematical model is introduced to model simultaneous heat and moisture transfer with phase change in porous media when undergoing temperature oscillations/cycling. The resulting model partial differential equations were solved using finite-volume procedures in the context of the PHYSICA framework and then applied to the analysis of sugar in storage. The influence of temperature on absorption/desorption and diffusion coefficients is coupled into the transport equations. The temperature profile, the depth of penetration of the temperature oscillation into the bulk solid, and the solids moisture content distribution were first calculated, and these proved to be in good agreement with experimental data. Then, the influence of temperature oscillation on absolute humidity, moisture concentration, and moisture migration for different parameters and boundary conditions was examined. As expected, the results show that moisture near boundary regions responds faster than farther away from them with surface temperature changes. The moisture absorption and desorption in materials occurs mainly near boundary regions (where interactions with the environment are more pronounced). Small amounts of solids moisture content, driven by both temperature and vapour concentration gradients, migrate between boundary and center with oscillating temperature.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

An algorithm for total variation inpainting based on nonlinear multi-grid methods

Image inpainting refers to restoring a damaged image with missing information. The total variation (TV) inpainting model is one such method that simultaneously fills in the regions with available information from their surroundings and eliminates noises. The method works well with small narrow inpainting domains. However there remains an urgent need to develop fast iterative solvers, as the underlying problem sizes are large. In addition one needs to tackle the imbalance of results between inpainting and denoising. When the inpainting regions are thick and large, the procedure of inpainting works quite slowly and usually requires a significant number of iterations and leads inevitably to oversmoothing in the outside of the inpainting domain. To overcome these difficulties, we propose a solution for TV inpainting method based on the nonlinear multi-grid algorithm.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

Spectroscopic studies of oligomers containing 2,5-trans furanoid sugar amino acids

Sugar amino acids and their oligomers, known as carbopeptoids, are commonly studied as foldamers. However, study of their conformational preference is often challenging when the adopted conformations are extended and/or disordered. This study is the first to explore the disordered nature of such carbopeptoids by utilizing a family of 2,5-trans carbopeptoids. An array of spectroscopic techniques has been used to investigate the conformational preference of these carbopeptoids. However, using this data alone it has not been possible to assign conformational preference as an ordered extended conformation or as a disordered family of closely related conformations. Computational methods need to be employed to achieve reliable interpretation of the spectroscopic data. Chirality, 2008. © 2008 Wiley-Liss, Inc.