Two-machine flowshop scheduling problems with no-wait jobs

We study a two-machine flow shop scheduling problem with no-wait in process, in which one of the machines is not available during a specified time interval. We consider three scenarios of handing the operation affected by the nonavailability interval. Its processing may (i) start from scratch after the interval, or (ii) be resumed from the point of interruption, or (iii) be partially restarted after the interval. The objective is to minimize the makespan. We present an approximation algorithm that for all these scenarios delivers a worst-case ratio of 3/2. For the second scenario, we offer a 4/3-approximation algorithm.

Flow shop scheduling problems under machine–dependent precedence constraints

The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.

Domain decomposition methods for welding problems

This paper, a 2-D non-linear electric arc-welding problem is considered. It is assumed that the moving arc generates an unknown quantity of energy which makes the problem an inverse problem with an unknown source. Robust algorithms to solve such problems e#ciently, and in certain circumstances in real-time, are of great technological and industrial interest. There are other types of inverse problems which involve inverse determination of heat conductivity or material properties [CDJ63][TE98], inverse problems in material cutting [ILPP98], and retrieval of parameters containing discontinuities [IK90]. As in the metal cutting problem, the temperature of a very hot surface is required and it relies on the use of thermocouples. Here, the solution scheme requires temperature measurements lied in the neighbourhood of the weld line in order to retrieve the unknown heat source. The size of this neighbourhood is not considered in this paper, but rather a domain decomposition concept is presented and an examination of the accuracy of the retrieved source are presented. This paper is organised as follows. The inverse problem is formulated and a method for the source retrieval is presented in the second section. The source retrieval method is based on an extension of the 1-D source retrieval method as proposed in [ILP].

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Two-machine flow shop scheduling problems with no-wait jobs

In this paper we provide a fairly complete complexity classification of various versions of the two-machine permutation flow shop scheduling problem to minimize the makespan in which some of the jobs have to be processed with no-wait in process. For some version, we offer a fully polynomial-time approximation scheme and a 43-approximation algorithm.

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.

Fatal impact? The effects of emotional arousal and weapon presence on police officers' memories for a simulated crime

Purpose. (1) To investigate the effects of emotional arousal and weapon presence on the completeness and accuracy of police officers' memories; and (2) to better simulate the experience of witnessing a shooting and providing testimony. Methods. A firearms training simulator was used to present 70 experienced police officers with either a shooting or a domestic dispute scenario containing no weapons. Arousal was measured using both self-report and physiological indices. Recall for event details was tested after a 10-minute delay using a structured interview. Identification accuracy was assessed with a photographic line-up. Results. Self-report measures confirmed that the shooting induced greater arousal than did the other scenario. Overall, officers' memories for the event were less complete, but more accurate, when they had witnessed the shooting. The recall and line-up data did not support a weapon focus effect. Conclusions. Police officers' recall performance can be affected both qualitatively and quantitatively by witnessing an arousing event such as a shooting.

Numerical simulation of incompressible flow problems using an unstructured staggered mesh method

A number of two dimensional staggered unstructured discretisation schemes for the solution of fluid flow and heat transfer problems have been developed. All schemes store and solve velocity vector components at cell faces with scalar variables solved at cell centres. The velocity is resolved into face-normal and face-parallel components and the various schemes investigated differ in the treatment of the parallel component. Steady-state and time-dependent fluid flow and thermal energy equations are solved with the well known pressure correction scheme, SIMPLE, employed to couple continuity and momentum. The numerical methods developed are tested on well known benchmark cases: the Lid-Driven Cavity, Natural Convection in a Cavity and Melting of Gallium in a rectangular domain. The results obtained are shown to be comparable to benchmark, but with accuracy dependent on scheme selection.

Parallel genetic algorithms for the solution of inverse heat conduction problems

A parallel genetic algorithm (PGA) is proposed for the solution of two-dimensional inverse heat conduction problems involving unknown thermophysical material properties. Experimental results show that the proposed PGA is a feasible and effective optimization tool for inverse heat conduction problems

A hybrid Laplace transform/finite difference boundary element method for diffusion problems

The solution process for diffusion problems usually involves the time development separately from the space solution. A finite difference algorithm in time requires a sequential time development in which all previous values must be determined prior to the current value. The Stehfest Laplace transform algorithm, however, allows time solutions without the knowledge of prior values. It is of interest to be able to develop a time-domain decomposition suitable for implementation in a parallel environment. One such possibility is to use the Laplace transform to develop coarse-grained solutions which act as the initial values for a set of fine-grained solutions. The independence of the Laplace transform solutions means that we do indeed have a time-domain decomposition process. Any suitable time solver can be used for the fine-grained solution. To illustrate the technique we shall use an Euler solver in time together with the dual reciprocity boundary element method for the space solution

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.

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.

Second language processing: an analysis of theory, problems and possible solutions

Second Language Processing examines the problems facing learners in the second language classroom from the theoretical perspectives of Processing Instruction (structured input) and Enhanced Input. These two theories are brought to bear on a variety of processing problems, such as the difficulty of connecting second language grammatical forms encoding tense and mood as well as noun-adjective agreement with their meaning. Empirical studies examine a range of languages including Japanese, Italian and Spanish, through which the authors suggest practical solutions to these processing problems.

Ambitious mothers – successful daughters: Mothers’ early expectations for children’s education and children’s earnings and sense of control in adult life

Background. Mothers' expectations for their children's educational attainment are related to children's educational and occupational attainment. Studies have yet to establish, however, the long-term links between maternal expectations and offspring earnings, which are not always related to occupational attainment especially in women, or between maternal expectations and offspring sense of control and self-efficacy, which are pivotal factors in career choice and development. Aims. To explore the role of mothers' expectations for their children's educational attainment in children's earnings attainment and sense of control later in life. Method. Data from sweeps of the 1970 British Cohort Study (BCS70) were used. The study sample was those cohort members with complete information on all the variables of interest. The study sample (N = 3,285) was more educated and less disadvantaged than the whole sample. If cohort members of this type are more likely to have a mother who has high expectations, then our results are biased downwards, which suggests that we underestimate the effect of expectations on our two outcome variables. Results. Mothers' expectations at the age of 10 were positively related to daughters' sense of control at the age of 30 even after controlling for ethnicity, educational attainment, and concurrent partner, parent, and labour market participation status, as well as the following confounding variables (measured at the ages of 0–10): general ability and general ability squared, locus of control, emotional and behavioural problems and emotional and behavioural problems squared, socio-economic disadvantage, parental social class, parental family structure, and mothers' education, child-rearing attitudes, and mental health. Mothers' expectations had no effect on sons' adult outcomes. Conclusions. Given that women are particularly at risk for poor psychological and economic outcomes in adulthood, and that this study likely underestimated the effect of expectations on these two outcomes, this is an important conclusion.

Sex talk? overcoming barriers about sex and contraception after childbirth

Anecdotal evidence tells professionals that childbirth is the best form of contraception. However, sexual health problems are the very common after childbirth with Barrett et al (2000) arguing that only 15% of women who have a postnatal sexual problem reported discussing it with a health professional. As health professionals with a predilection for the ‘clinical’ and the ‘prescriptive’ we organise antenatal classes to discuss bathing the baby and post partum reunions to recount birth stories, but often fail to address sexual health problems and contraception after birth.(Glazener 1997). Many women who have carefully used contraception for years prior to pregnancy are often not helped to re-engage with the issues following birth. This would seem to be a particular problem for the most vulnerable parents such as adolescent mothers and their partners (Social Exclusion Unit 1999, 2004) where some young women go on to have more than one baby in a short time period (Reeves 2003). The focus of this paper is to explore the apparent general failure of health professionals to discuss sex after childbirth and provide information regarding reliable contraception. Glazener (1997) tells us that health professionals are encouraged to educate and prepare patients antenatally, for example to be trained to identify problems and deal with them openly and sympathetically. What is brought into question is why this form of rigorous support is not extended to providing sexual health advice in the immediate and often vulnerable postnatal period and why this provision is not a priority for some groups. The paper will explore if this situation caused by a lack of training or is it a symptom of our culture and a British attitude towards sex and contraception.