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.

Time dependent electric, magnetic and hydrodynamic interaction in aluminium electrolysis cells

The waves in commercial cells for electrolytic aluminium production originate at the interface between the liquid aluminium and electrolyte, but their effect can spread into the surrounding busbar network as electric current perturbation, and the total magnetic field acquires a time dependent component. The presented model for the wave development accounts for the nonuniform electric current distribution at the cathode and the whole network of the surrounding busbars. The magnetic field is computed for the continuous current in the fluid zones, all busbars and the ferromagnetic construction elements. When the electric current and the associated magnetic field are computed according to the actual electrical circuit and updated for all times, the instability growth rate is significantly affected. The presented numerical model for the wave and electromagnetic interaction demonstrates how different physical coupling factors are affecting the wave development in the electrolysis cells. These small amplitude self-sustained interface oscillations are damped in the presence of intense turbulent viscosity created by the horizontal circulation velocity field. Additionally, the horizontal circulation vortices create a pressure gradient contributing to the deformation of the interface. Instructive examples for the 500 kA demonstration cell are presented.

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.

Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach

We consider a variety of preemptive scheduling problems with controllable processing times on a single machine and on identical/uniform parallel machines, where the objective is to minimize the total compression cost. In this paper, we propose fast divide-and-conquer algorithms for these scheduling problems. Our approach is based on the observation that each scheduling problem we discuss can be formulated as a polymatroid optimization problem. We develop a novel divide-and-conquer technique for the polymatroid optimization problem and then apply it to each scheduling problem. We show that each scheduling problem can be solved in $ \O({\rm T}_{\rm feas}(n) \times\log n)$ time by using our divide-and-conquer technique, where n is the number of jobs and Tfeas(n) denotes the time complexity of the corresponding feasible scheduling problem with n jobs. This approach yields faster algorithms for most of the scheduling problems discussed in this paper.

Schedules with due-date assignment and position-dependent processing times

Single machine scheduling problems are considered, in which the processing of jobs depend on positions of the jobs in a schedule and the due-dates are assigned either according to the CON rule (a due-date common to all jobs is chosen) or according to the SLK rule (the due-dates are computed by increasing the actual processing times of each job by a slack, common to all jobs). Polynomial-time dynamic programming algorithms are proposed for the problems with the objective functions that include the cost of assigning the due-dates, the total cost of disgarded jobs (which are not scheduled) and, possibly, the total earliness of the scheduled jobs.

The UK WTC 9/11 evacuation study: an overview of the methodologies employed and some analysis relating to fatigue, stair travel speeds and occupant response times

This paper briefly describes the methodologies employed in the collection and storage of first-hand accounts of evacuation experiences derived from face-to-face interviews with evacuees from the World Trade Center (WTC) Twin Towers complex on 11 September 2001 and the development of the High-rise Evacuation Evaluation Database (HEED). The main focus of the paper is to present an overview of preliminary analysis of data derived from the evacuation of the North Tower.

Investigating the use of elevators for high-rise building evacuation through computer simulation

This paper presents a description of a new agent based elevator sub-model developed as part of the buildingEXODUS software intended for both evacuation and circulation applications. A description of each component of the newly developed model is presented, including the elevator kinematics and associated pedestrian behaviour. The elevator model is then used to investigate a series of full building evacuation scenarios based on a hypothetical 50 floor building with four staircases and a population of 7,840 agents. The analysis explores the relative merits of using up to 32 elevators (arranged in four banks) and various egress strategies to evacuate the entire building population. Findings from the investigation suggest that the most efficient evacuation strategy utilises a combination of elevators and stairs to empty the building and clear the upper half of the building in minimum time. Combined stair elevator evacuation times have been shown to be as much as 50% faster than stair only evacuation times.

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.

Preemptive scheduling on uniform parallel machines with controllable job processing times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

Metaphors and metamorphoses: narratives of identity during times of crisis

The narrative of transformative crisis appears in both autobiographical and fictional accounts of individual lives; it typically involves a difficult or traumatic episode and a period of self-questioning out of which a person emerges more able and more emotionally mature than before (Booker, 2005; Erikson, 1968; Tedeschi and Calhoun, 1995). The present study used interviews to elicit 22 narratives about crises experienced between the ages of 25 and 40, and about any developmental transformation and change that surrounded these crises. Analysis revealed a common four-phase process to the crisis episodes, common metaphors and recurrent descriptions of identity metamorphosis, ie. of ‘becoming a new person’. Comparison of these findings with theory on fictional plots shows a clear parallel between the four-phase process of crisis found in the current study and the ‘rebirth’ plot described by Booker (2005). The theoretical significance of these findings and interpretations is discussed.

Reinforcement corrosion initiation and activation times in concrete structures exposed to severe marine environments

The corrosion of steel reinforcement bars in reinforced concrete structures exposed to severe marine environments usually is attributed to the aggressive nature of chloride ions. In some cases in practice corrosion has been observed to commence already within a few years of exposure even with considerable concrete cover to the reinforcement and apparently high quality concretes. However, there are a number of other cases in practice for which corrosion initiation took much longer, even in cases with quite modest concrete cover and modest concrete quality. Many of these structures show satisfactory long-term structural performance, despite having high levels of localized chloride concentrations at the reinforcement. This disparity was noted already more than 50 years ago, but appears still not fully explained. This paper presents a systematic overview of cases reported in the engineering and corrosion literature and considers possible reasons for these differences. Consistent with observations by others, the data show that concretes made from blast furnace cements have better corrosion durability properties. The data also strongly suggest that concretes made with limestone or non-reactive dolomite aggregates or sufficiently high levels of other forms of calcium carbonates have favourable reinforcement corrosion properties. Both corrosion initiation and the onset of significant damage are delayed. Some possible reasons for this are explored briefly.

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.