Two-stage no-wait scheduling models with setup and removal times separated

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other is the assembly model. For both models we consider the problem of minimizing the makespan, provided that the setup and removal times are separated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in general, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assembly problem under some reasonable assumptions. Using these and existing results, we provide a complete complexity classification of the relevant two-stage no-wait scheduling models.

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.

Group technology approach to the open shop scheduling problem with batch setup times

This paper studies the problem of scheduling jobs in a two-machine open shop to minimize the makespan. Jobs are grouped into batches and are processed without preemption. A 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. For this NP-hard problem, we propose a linear-time heuristic algorithm that creates a group technology schedule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a -approximation algorithm. Moreover, we show that no group technology algorithm can guarantee a worst-case performance ratio less than 5/4.

On-line algorithms for single machine scheduling with family setup times

The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

(From) The Mill for Grinding Old People Young

Chapter one of novel in progress

The application of colloidal gas aphrons in the recovery of fine cellulose fibres from paper mill wastewater

Colloidal gas aphrons (CGAs) are micron-sized gas bubbles of 25–30 µm in diameter produced by a high-speed stirrer in a vessel containing dilute surfactant solution. These bubbles, because of their small size, exhibit some colloidal properties. In this work, CGAs were used to separate fine fibres from a lean slurry of cellulosic pulp in a flotation column. The pulp fibres were recovered as foamate from the top. Sodium dodecyl sulphate at a concentration of 2.0 kg/m3 was used as a surfactant to generate the CGAs in a spinning disc apparatus. The results indicated that up to 70% flotation efficiency could be obtained within a short column height of 0.3–0.35 m. This technique can be applied to recover fine cellulosic pulp from paper-machine backwater.

Experimental setup and first measurement of DNA damage induced along and around an antiproton beam

Radiotherapy employs ionizing radiation to induce lethal DNA lesions in cancer cells while minimizing damage to healthy tissues. Due to their pattern of energy deposition, better therapeutic outcomes can, in theory, be achieved with ions compared to photons. Antiprotons have been proposed to offer a further enhancement due to their annihilation at the end of the path. The work presented here aimed to establish and validate an experimental procedure for the quantification of plasmid and genomic DNA damage resulting from antiproton exposure. Immunocytochemistry was used to assess DNA damage in directly and indirectly exposed human fibroblasts irradiated in both plateau and Bragg peak regions of a 126 MeV antiproton beam at CERN. Cells were stained post irradiation with an anti-gamma-H2AX antibody. Quantification of the gamma-H2AX foci-dose relationship is consistent with a linear increase in the Bragg peak region. A qualitative analysis of the foci detected in the Bragg peak and plateau region indicates significant differences highlighting the different severity of DNA lesions produced along the particle path. Irradiation of desalted plasmid DNA with 5 Gy antiprotons at the Bragg peak resulted in a significant portion of linear plasmid in the resultant solution.

Synthesis of nucleoside analogues in a ball mill: fast, chemoselective and high yielding acylation without undesirable solvents

The chemoselective acylation of primary aliphatic amines has been achieved in under ten minutes (and for aromatic amines under 120 min) using vibration ball-milling, avoiding undesirable solvents which are typically employed for such reactions (e.g. DMF). Under optimised conditions, the synthesis of amides in the presence of both primary and secondary alcohol functions was achieved in high to excellent yields (65-94%). Overall, the methods described have significant practical advantages over conventional approaches based upon bulk solvents including greater yields, higher chemoselectivity and easier product separation.

Rapid synthesis of nucleotide pyrophosphate linkages in a ball mill

Using a ball mill, rapid, atom-economic coupling between adenosine-5'-phosphoromorpholidate and phosphorylated ribose derivatives as their sodium or barium salts was achieved. Facile purification by reversed-phase HPLC enabled product isolation within hours.