Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

Integrated biomedical device for blood preparation

The separation of red blood cells from plasma flowing in microchannels is possible by bio-physical effects such as an axial migration effect and Zweifach-Fung bifurcation law. In the present study, subchannels are placed alongside a main channel to collect cells and plasma separately. The addition of a constriction in the main microchannel creates a local high shear force region, forcing the cells to migrate and concentrate towards the centre of the channel. The resulting lab-on-a-chip was manufactured using biocompatible materials. Purity efficiency was measured for mussel and human blood suspensions as different parameters including flow rate and geometries of parent and daughter channels were varied.