Scheduling three-operation jobs in a two-machine flow shop to minimize makespan

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented.

Tree species-area and species-diameter relationships at three lowland rain forest sites in Sumatra

Data from three forest sites in Sumatra (Batang Ule, Pasirmayang and Tebopandak) have been analysed and compared for the effects of sample area cut-off, and tree diameter cut-off. An 'extended inverted exponential model' is shown to be well suited to fitting tree-species-area curves. The model yields species carrying capacities of 680 for Batang Ule, 380 species for Pasirmayang, and 35 for Tebopandak (tree diameter >10cm). It would seem that in terms of species carrying capacity, Tebopandak and Pasirmayang are rather similar, and both less diverse than the hilly Batang Ule site. In terms of conservation policy, this would mean that rather more emphasis should be put on conserving hilly sites on a granite substratum. For Pasirmayang with tree diameter >3cm, the asymptotic species number estimate is 567, considerably higher than the estimate of 387 species for trees with diameter >10cm. It is clear that the diameter cut-off has a major impact on the estimate of the species carrying capacity. A conservative estimate of the total number of tree species in the Pasirmayang region is 632 species! In sampling exercises, the diameter cut-off should not be chosen lightly, and it may be worth adopting field sampling procedures which involve some subsampling of the primary sample area, where the diameter cut-off is set much lower than in the primary plots.