Two-machine open shop scheduling with an availability constraint

We study a two-machine open shop scheduling problem, in which one machine is not available for processing during a given time interval. The objective is to minimize the makespan. We show that the problem is NP-hard and present an approximation algorithm with a worst-case ratio of 4/3.

Non-preemptive two-machine open shop scheduling with non-availability constraints

We study a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. No preemption is allowed in the processing of any operation. The objective is to minimize the makespan. We consider approximability issues of the problem with more than one non-availability intervals and present an approximation algorithm with a worst-case ratio of 4/3 for the problem with a single non-availability interval.

Investigating the impact of exit availability on egress time using computer based evacuation simulation

This paper examines the influence of exit availability on evacuation time for a narrow body aircraft under certification trial conditions using computer simulation. A narrow body aircraft which has previously passed the certification trial is used as the test configuration. While maintaining the certification requirement of 50% of the available exits, six different exit configurations are examined. These include the standard certification configuration (one exit from each exit pair) and five other exit configurations based on commonly occurring exit combinations found in accidents. These configurations are based on data derived from the AASK database and the evacuation simulations are performed using the airEXODUS evacuation simulation software. The results show that the certification practice of using half the available exits predominately down one side of the aircraft is neither statistically relevant nor challenging. For the aircraft cabin layout examined, the exit configuration used in certification trial produces the shortest egress times. Furthermore, three of the six exit combinations investigated result in predicted egress times in excess of 90 seconds, suggesting that the aircraft would not satisfy the certification requirement under these conditions.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

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.

Operator non-availability periods

In the scheduling literature, the notion of machine non availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator non availability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling and other polynomial-time algorithms.

Investigating the impact of aircraft exit availability on egress time using computer simulation

This paper examines the influence of exit availability on evacuation time for narrow body aircraft under certification trial conditions using computer simulation. A narrow body aircraft which has previously passed the certification trial is used as the test configuration. While maintaining the certification requirement of 50% of the available exits, six different configurations are examined. These include the standard certification and five other exit configurations based on commonly occurring exit combinations found in accidents. These configurations are based on data derived from the AASK database and the evacuation simulations are performed using the airEXODUS evacuation software. The results show that the certification practise of using half of the available exits predominately down one side of the aircraft is neither statistically relevant nor challenging. For the aircraft cabin layout examined, the exit configuration used in certification trial produces the shortest egress times. Furthermore, three of the six exit combinations investigated result in predicted egress times in excess of 90 seconds, suggesting that the aircraft would not satisfy the certification requirement under these conditions.

Use of satellite data for modelling food availability and survival of marine fish larvae

A modelling scheme is described which uses satellite retrieved sea-surface temperature and chlorophyll-a to derive monthly zooplankton biomass estimates in the eastern North Atlantic; this forms part of a bio-physical model of inter-annual variations in the growth and survival of larvae and post-larvae of mackerel (Scomber scombrus). The temperature and chlorophyll data are incorporated first to model copepod (Calanus) egg production rates. Egg production is then converted to available food using distribution data from the Continuous Plankton Recorder (CPR) Survey, observed population biomass per unit daily egg production and the proportion of the larval mackerel diet comprising Calanus. Results are validated in comparison with field observations of zooplankton biomass. The principal benefit of the modelling scheme is the ability to use the combination of broad scale coverage and fine scale temporal and spatial variability of satellite data as driving forces in the model; weaknesses are the simplicity of the egg production model and the broad-scale generalizations assumed in the raising factors to convert egg production to biomass.

Wind mixing, food availability and mortality of anchovy larvae Engraulis encrasicolus in the northern Adriatic Sea

A study was carried out in June/July 1996 in the River Po outflow in the northern Adriatic to investigate spawning of anchovy Engraulis encrasicolus and survival of larvae in relation to food availability and wind mixing. Hydrographic- and bongo net sampling was carried out on 2 grid surveys; one after a period of low winds and settled weather, and the other after an intervening period of strong winds, which resulted in a decrease in water column stratification. The spawning areas of anchovy and the larval distributions were associated with the river outflow plume (most clearly on the second survey grid, after the period of higher winds). Potential food particles for anchovy larvae, primarily copepod nauplii and copepodite stages, were also concentrated in the area influenced by the river outflow. Although there was a nearly 50% reduction in the mean water column abundance of potential food particles between the 2 survey grids, mostly due to a decline in abundance outside the immediate river plume area, there was no significant change in mortality of anchovy larvae between the 2 grids; the exponential decline in numbers of eggs and larvae to 10 mm in length being equivalent to overall mortality rates of 43.2%/d on the first survey and 44.7%/d on the second. The resilience of larval survival under potentially less favourable feeding conditions, following the period of wind mixing, was ascribed, in part, to the maintenance of local water column stratification by the superficial low salinity input from the River Po. This stratification in the immediate outflow area was associated with the presence of concentrated layers of potential food particles (typically >50 particles/L and 1.5 to 2.8 times the mean water column abundance) in the upper 10 m of the water column, coincident with peak numbers of anchovy larvae. However, since there was no evidence for lower larval survival in areas, less influenced by the immediate river outflow plume, a simple direct relationship between enhanced water column stability, improved feeding conditions and larval survival was not supported.