An open shop scheduling problem with a non-bottleneck machine

This paper considers the problem of processing n jobs in a two-machine non-preemptive open shop to minimize the makespan, i.e., the maximum completion time. One of the machines is assumed to be non-bottleneck. It is shown that, unlike its flow shop counterpart, the problem is NP-hard in the ordinary sense. On the other hand, the problem is shown to be solvable by a dynamic programming algorithm that requires pseudopolynomial time. The latter algorithm can be converted into a fully polynomial approximation scheme that runs in time. An O(n log n) approximation algorithm is also designed whi finds a schedule with makespan at most 5/4 times the optimal value, and this bound is tight.

Scheduling parallel dedicated machines under a single non-shared resource

The scheduling problem of minimizing the makespan for m parallel dedicated machines under single resource constraints is considered. For different variants of the problem the complexity status is established. Heuristic algorithms employing the so-called group technology approach are presented and their worst-case behavior is examined. Finally, a polynomial time approximation scheme is presented for the problem with fixed number of machines.

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.

Low temperature crystal structures of two rhodanine derivatives, 3-amino rhodanine and 3-methyl rhodanine: geometry of the rhodanine ring

Rhodanines (2-thio-4-oxothiazolidines) are synthetic small molecular weight organic molecules with diverse applications in biochemistry, medicinal chemistry, photochemistry, coordination chemistry and industry. The X-ray crystal structure determination of two rhodanine derivatives, namely (I), 3-aminorhodanine [3-amino-2-thio-4-oxothiazolidine], C3H4N2OS2, and (II) 3-methylrhodanine [3-methyl-2-thio-4-oxothiazolidine], C4H5NOS2, have been conducted at 100 K. I crystallizes in the monoclinic space group P2(1)/n with unit cell parameters a = 9.662(2), b = 9.234(2), c = 13.384(2) angstrom, beta = 105.425(3)degrees, V = 1151.1(3) angstrom(3), Z = 8 (2 independent molecules per asymmetric unit), density (calculated) = 1.710 mg/m(3), absorption coefficient = 0.815 mm(-1). II crystallizes in the orthorhombic space group Iba2 with unit cell a = 20.117(4), b = 23.449(5), c = 7.852(2) angstrom, V = 3703.9(12) angstrom(3), Z = 24 (three independent molecules per asymmetric unit), density (calculated) = 1.584 mg/m(3), absorption coefficient 0.755 mm(-1). For I in the final refinement cycle the data/restraints/parameter ratios were 2639/0/161, goodness-of-fit on F-2 = 0.934, final R indices [I > 2sigma(I)] were R1 = 0.0299, wR2 = 0.0545 and R indices (all data) R1 = 0.0399, wR2 = 0.0568. The largest difference peak and hole were 0.402 and -0.259 e angstrom(-3). For II in the final refinement cycle the data/restraints/parameter ratios were 3372/1/221, goodness-of-fit on F(2) = 0.950, final R indices [I > 2sigma(I)] were R1 = 0.0407, wR2 = 0.1048 and R indices (all data) R1 = 0.0450, wR2 = 0.1088. The absolute structure parameter = 0.19(9) and largest difference peak and hole 0.934 and -0.301 e angstrom(-3). Details of the geometry of the five molecules (two for I and three for II) and the crystal structures are fully discussed. Corresponding features of the molecular geometry are highly consistent and firmly establish the geometry of the rhodanine

Velocity measurement of pneumatically conveyed solids using electrodynamic sensors

Theoretical and experimental studies of cross correlation techniques applied to non-restrictive velocity measurement of pneumatically conveyed solids using ring-shaped electrodynamic flow sensors are presented. In-depth studies of the electrodynamic sensing mechanism, and also of the spatial sensitivity and spatial filtering properties of the sensor are included, together with their relationships to measurement accuracy and the effects of solids' velocity profiles. The experimental evaluation of a 53 mm bore sensing head is described, including trials using a calibrated pneumatic conveyor circulating pulverized fuel and cement. Comparisons of test results with the mathematical models of the sensor are used to identify important aspects of the instrument design. Off-line test results obtained using gravity-fed solids flow show that the system repeatability is within +/-0.5% over the velocity range of 2-4 m s(-1) for volumetric concentrations of solids no greater than 0.2%. Results obtained in the pilot-plant trials demonstrate that the system is capable of achieving repeatability better than +/-2% and linearity within +/-2% over the velocity range 20-40 m s(-1) for volumetric concentrations of solids in the range 0.01-0.44%.