Applications of DNP-NMR for the measurement of heteronuclear T1 relaxation times

Measurement of heteronuclear spin-lattice relaxation times is hampered by both low natural abundance and low detection sensitivity. Combined with typically long relaxation times, this results in extended acquisition times which often renders the experiment impractical. Recently a variant of dynamic nuclear polarisation has been demonstrated in which enhanced nuclear spin polarisation, generated in the cryo-solid state, is transferred to the liquid state for detection. Combining this approach with small flip angle pulse trains, similar to the FLASH-T(1) imaging sequence, allows the rapid determination of spin-lattice relaxation times. In this paper we explore this method and its application to the measurement of T(1) for both carbon-13 and nitrogen-15 at natural abundance. The effects of RF inhomogeneity and the influence of proton decoupling in the context of this experiment are also investigated.

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.

A 3/2 algorithm for two-machine open shop with route-dependent processing times

This paper considers the problem of minimizing the schedule length of a two-machine shop in which not only can a job be assigned any of the two possible routes, but also the processing times depend on the chosen route. This problem is known to be NP-hard. We describe a simple approximation algorithm that guarantees a worst-case performance ratio of 2. We also present some modifications to this algorithm that improve its performance and guarantee a worst-case performance ratio of 3=2.

Measuring distributions of jump rates in disordered metal–hydrogen systems by nuclear magnetic relaxation

Monte Carlo calculations of the nuclear magnetic relaxation rate in a disordered metal–hydrogen system having a distribution of jump rates are reported. The calculations deal specifically with the spin-locked rotating-frame relaxation time T1ρ. The results demonstrate that the temperature variation of the rate is only weakly dependent on the distribution and it is therefore unlikely that the jump rate distribution can be extracted from relaxation measurements in which temperature is the main variable. It is shown that the alternative of measuring the relaxation rate over a wide range of spin-locking field strengths at a constant temperature can lead to an evaluation of the distribution.

Rotating-frame nuclear magnetic relaxation of spins diffusing on a disordered lattice: a Monte Carlo model

The rotating-frame nuclear magnetic relaxation rate of spins diffusing on a disordered lattice has been calculated by Monte Carlo methods. The disorder includes not only variation in the distances between neighbouring spin sites but also variation in the hopping rate associated with each site. The presence of the disorder, particularly the hopping rate disorder, causes changes in the time-dependent spin correlation functions which translate into asymmetry in the characteristic peak in the temperature dependence of the dipolar relaxation rate. The results may be used to deduce the average hopping rate from the relaxation but the effect is not sufficiently marked to enable the distribution of the hopping rates to be evaluated. The distribution, which is a measure of the degree of disorder, is the more interesting feature and it has been possible to show from the calculation that measurements of the relaxation rate as a function of the strength of the radiofrequency spin-locking magnetic field can lead to an evaluation of its width. Some experimental data on an amorphous metal - hydrogen alloy are reported which demonstrate the feasibility of this novel approach to rotating-frame relaxation in disordered materials.

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.

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.

A heuristic for the two-machine open-shop scheduling problem with transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimize the makespan, provided that preemption is not allowed and the interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O (n log n) time and provides a worst-case performance ratio of 3/2.

Proportionate flow shop with controllable processing times

This paper considers a special class of flow-shop problems, known as the proportionate flow shop. In such a shop, each job flows through the machines in the same order and has equal processing times on the machines. The processing times of different jobs may be different. It is assumed that all operations of a job may be compressed by the same amount which will incur an additional cost. The objective is to minimize the makespan of the schedule together with a compression cost function which is non-decreasing with respect to the amount of compression. For a bicriterion problem of minimizing the makespan and a linear cost function, an O(n log n) algorithm is developed to construct the Pareto optimal set. For a single criterion problem, an O(n2) algorithm is developed to minimize the sum of the makespan and compression cost. Copyright © 1999 John Wiley & Sons, Ltd.

The collection and analysis of pre-evacuation times derived from evacuation trials and their application to evacuation modelling

This paper presents data relating to occupant pre-evacuation times from university and hospital outpatient facilities. Although the two occupancies are entirely different, they do employ relatively similar procedures: members of staff sweep areas to encourage individuals to evacuate.However the manner in which the dependent population reacts to these procedures is quite different. In the hospital case, the patients only evacuated once a member of the nursing staff had instructed them to do so, while in the university evacuation, the students were less dependent upon the actions of the staff, with over 50% of them evacuating with no prior prompting. In addition, the student pre-evacuation time was found to be dependent on their level of engagement in various activities.

The collection of pre-evacuation times from evacuation trials involving a Hospital Outpatient area and a University Library facility

This paper presents data relating to occupant pre-evacuation times from a university and a hospital outpatient facility. Although the two structures are entirely different they do employ relatively similar procedures: members of staff sweeping areas of the structure to encourage individuals to evacuate. However, the manner in which the dependent population reacts to these procedures is quite different. In the hospital case the patients only evacuated once a member of the nursing staff had instructed them to do so while in the university evacuation the students were less dependent upon the actions of the staff with over 50% of them evacuating with no prior prompting. Although this data may be useful in a variety of areas, it was collected primarily for use within evacuation models.

Pre-emptive scheduling problems with controllable processing times

We consider a range of single machine and identical parallel machine pre-emptive scheduling models with controllable processing times. For each model we study a single criterion problem to minimize the compression cost of the processing times subject to the constraint that all due dates should be met. We demonstrate that each single criterion problem can be formulated in terms of minimizing a linear function over a polymatroid, and this justifies the greedy approach to its solution. A unified technique allows us to develop fast algorithms for solving both single criterion problems and bicriteria counterparts.

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.