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.

Scheduling parallel dedicated machines with the speeding-up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two-machine problem is NP-hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst-case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple-choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

Thermoelectric MHD effects on equiaxed crystal morphology

The effects of a constant uniform magnetic field on a growing equiaxed crystal are investigated using a 3-dimensional enthalpy based numerical model. Two cases are considered: The first case looks at unconstrained growth, where the current density is generated through the thermo-electric effect and the current circulates between the tips and roots of the dendrite, the second represents an imposed potential difference across the domain. A jump in the electrical conductivity between the liquid and solid causes the current density to be non uniform. In both cases the resulting Lorentz force drives fluid flow in the liquid phase, this in turn causes advection of the thermal and solute field altering the free energy close to the interface and changing the morphology of the dendrite. In the first case the flow field is complex comprising of many circulations, the morphological changes are modelled using a 2D model with a quasi 3D approximation. The second case is comparable to classic problems involving a constant velocity boundary.