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.

Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m⩾2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation.

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P6≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.

Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

Abstract not available

Two-stage open shop scheduling with a bottleneck machine

Abstract not available

Parallel partitioning of unstructured meshes

A method is outlined for optimising graph partitions which arise in mapping un- structured mesh calculations to parallel computers. The method employs a combination of iterative techniques to both evenly balance the workload and minimise the number and volume of interprocessor communications. They are designed to work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. The algorithms can also be used for dynamic load-balancing and a clustering technique can additionally be employed to speed up the whole process. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds.

Mesh partitioning and load balancing for distributed memory parallel systems

A method is outlined for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a relative gain iterative technique to both evenly balance the workload and minimise the number and volume of interprocessor communications. A parallel graph reduction technique is also briefly described and can be used to give a global perspective to the optimisation. The algorithms work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds. The algorithms can also be used for dynamic load-balancing, reusing existing partitions and in this case the procedures are much faster than static techniques, provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data.

Batching decisions for assembly production systems

The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching.

What a performance! Developing nurse teachers lecturing persona and identity: a performing arts perspective

Delivering lectures to large groups of students can provoke high levels of anxiety, particularly for new lecturers (Exley and Dennick, 2009). Further, to provide an informative and engaging lecture requires a teacher who is confident, has a sound knowledge and well developed teaching skills (Bentley-Davies, 2010). Thus, new lecturers often need experience and supervision to develop the tacit knowledge and insight into their own style and persona when teaching in order to feel confident when delivering a lecture (Quinn and Hughes, 2007). Considering this model, therefore, may potentially contribute to a lecturers’ development and performance in the classroom. This paper will present the results of the second phase of a two-stage mixed method study that investigated the similarities between lecturing and acting. Twelve in-depth interviews where undertaken with lecturers within one School of Nursing in The United Kingdom. Findings, established a model of ‘persona adoption’ that represents a series of stages that lecturers may go through to both develop and take on a persona when lecturing. This persona is often different from the way they lecturers present themselves in other parts of their working life. The first stage of this model of persona adoption is when the lecturer is subjected to a range of ‘influencing factors’ that provide not only the basic information about a lecture, but also the perceptual stimuli about giving a lecture on a specific subject, to a particular number of students, at a certain academic level. These influencing factors then inter-play with the ‘facets of the individual’, which represent the lecturer’s self-concept, subject knowledge base and philosophy of teaching. This may result in a cognitive dissonance between these ‘facets’ and the ‘influencing factors’, so affecting the lecturers’ perceptions, thoughts and feelings about having to give that particular lecture. This results in the lecturer undertaking specific ‘back stage preparation’ during which they decide on the content and modes of delivery to prepare in light of that discourse. It may result in delivering the information via single or multiple methods, which during the lecture will require various levels of interaction and participation from the students. Just prior to the lecture, the lecturer builds or ‘puts on their persona’ and gets into role, making their initial impact with the group. They use the ‘elements of acting’ as proposed by Tauber and Mester’s (1994) e.g. animated voice and body, space, props humour and suspense and surprise to portray and maintain their persona. This leads the to lecturer demonstrating either positive or negative ‘persona characteristics’ in terms of appearing confident, knowledgeable, fluent in the technical skills of delivering the lecture, being interesting and engendering interaction with the students, or not. These characteristics, may or may not, potentially heighten student interest, attention and attitudes to learning as suggested by Tauber and Mester (1994). This depends on whether the lecturer has successfully used the persona and if the lecturer has been able to engage students in the lecture, in competition with other factors that may be taking the students’ attention. Although the model suggests a linear process, to a great extent, the elements might be more interdependent and interrelated. This might suggest that depending on the lecturer’s perception of their effectiveness during the lecture, that they may decide to continue or adapt their persona and methods to appear more confident. Furthermore, depending on how successful the lecturer perceived the session to be, both their reflections ‘in’ and ‘on’ practice could influence how they teach in the future (Zwozdiak, 2011). Therefore, these reflections become part of the facets of the individual, via the ‘reflective feedback loop’, in the model, which then in turn influences progression through the model in subsequent lectures. This study concluded that these lecturers went through a process whereby they compare the demands of the lecture with their own knowledge base and skill, this resulted in them undertaking specific preparation in terms of content and delivery style, then they adopted their persona immediately prior to entering the lecture, maintain it throughout the lecture via the use of the elements of acting to achieve an informative interactive lecture. The results of which then feedback into their self-concept as a lecturer and consequently may affect the persona they project in future lectures. If lecturers, therefore, can take a step back to consider how they deliver lectures and the way they can deliberately, yet apparently naturally, use their voices, bodies, space and humour in meaningfully, they engage their students in lecture, it will not just result in them being perceived as a good lecturer, but also be a genuine act of education.