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.

Characterizing the most general temporal constraint

This paper introduces a characterization of the so-called most general temporal constraint (GTC), which guarantees the common-sense assertion that "the beginning of the effect cannot precede the beginning of the cause". The formalism is based on general time theory which takes both points and intervals as primitive. It is shown that there are in fact 8 possible causal relationships which satisfy GTC, including cases where, on the one hand, effects start simultaneously with, during, immediately after, or some time after their causes, and on the other hand, events end before, simultaneously with, or after their causes. These causal relationships are versatile enough to subsume those representatives in the literature.

A price worth paying?: Women and work – choice, constraint or satisficing

Purpose – Are women held back or holding back? Do women choose their jobs/careers or are they structurally or normatively constrained? The purpose of this paper is to shed fresh light on these questions and contribute to an on-going debate that has essentially focused on the extent to which part-time work is women’s choice, the role of structural and organisational constraints and the role of men in excluding women. Design/methodology/approach – The paper uses data from interviews with 80 working women – both full-time and part-time – performing diverse work roles in a range of organisations in the south east of England. Findings – It was found that many women do not make strategic job choices, rather they often ‘‘fall into’’ jobs that happen to be available to them. Some would not have aspired to their present jobs without male encouragement; many report incidents of male exclusion; and virtually all either know or suspect that they are paid less than comparable men. Those working reduced hours enjoy that facility, yet they are aware that reduced hours and senior roles are seen as incompatible. In short, they recognise both the positive and negative aspects of their jobs, whether they work full or part-time, whether they work in male-dominated or female-dominated occupations, and whatever their position in the organisational hierarchy. Accordingly, the paper argues that the concept of ‘‘satisficing’’, i.e. a decision which is good enough but not optimal, is a more appropriate way to view women’s working lives than are either choice or constraint theories. Originality/value – There is an ongoing, and often polarised, debate between those who maintain that women choose whether to give preference to work or home/family and others who maintain that women, far from being self-determining actors, are constrained structurally and normatively. Rather than supporting these choice or constraint theories, this paper argues that ‘‘satisficing’’ is a more appropriate and nuanced concept to explain women’s working lives.

FUELGEN: effective evolutionary design of refuellings for pressurized water reactors

The paper describes the design of an efficient and robust genetic algorithm for the nuclear fuel loading problem (i.e., refuellings: the in-core fuel management problem) - a complex combinatorial, multimodal optimisation., Evolutionary computation as performed by FUELGEN replaces heuristic search of the kind performed by the FUELCON expert system (CAI 12/4), to solve the same problem. In contrast to the traditional genetic algorithm which makes strong requirements on the representation used and its parameter setting in order to be efficient, the results of recent research results on new, robust genetic algorithms show that representations unsuitable for the traditional genetic algorithm can still be used to good effect with little parameter adjustment. The representation presented here is a simple symbolic one with no linkage attributes, making the genetic algorithm particularly easy to apply to fuel loading problems with differing core structures and assembly inventories. A nonlinear fitness function has been constructed to direct the search efficiently in the presence of the many local optima that result from the constraint on solutions.

Dynamic multi-partitioning for parallel finite element applications

The central product of the DRAMA (Dynamic Re-Allocation of Meshes for parallel Finite Element Applications) project is a library comprising a variety of tools for dynamic re-partitioning of unstructured Finite Element (FE) applications. The input to the DRAMA library is the computational mesh, and corresponding costs, partitioned into sub-domains. The core library functions then perform a parallel computation of a mesh re-allocation that will re-balance the costs based on the DRAMA cost model. We discuss the basic features of this cost model, which allows a general approach to load identification, modelling and imbalance minimisation. Results from crash simulations are presented which show the necessity for multi-phase/multi-constraint partitioning components

Microwave cure of conductive adhesives for flip-chip & microsystems applications

The curing of conductive adhesives and underfills can save considerable time and offer cost benefits for the microsystems and electronics packaging industry. In contrast to conventional ovens, curing by microwave energy generates heat internally within each individual component of an assembly. The rate at which heat is generated is different for each of the components and depends on the material properties as well as the oven power and frequency. This leads to a very complex and transient thermal state, which is extremely difficult to measure experimentally. Conductive adhesives need to be raised to a minimum temperature to initiate the cross-linking of the resin polymers, whilst some advanced packaging materials currently under investigation impose a maximum temperature constraint to avoid damage. Thermal imagery equipment integrated with the microwave oven can offer some information on the thermal state but such data is based on the surface temperatures. This paper describes computational models that can simulate the internal temperatures within each component of an assembly including the critical region between the chip and substrate. The results obtained demonstrate that due to the small mass of adhesive used in the joints, the temperatures reached are highly dependent on the material properties of the adjacent chip and substrate.

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.

Enhancing the usability of numerical models with case-based reasoning

Numerical models are important tools used in engineering fields to predict the behaviour and the impact of physical elements. There may be advantages to be gained by combining Case-Based Reasoning (CBR) techniques with numerical models. This paper considers how CBR can be used as a flexible query engine to improve the usability of numerical models. Particularly they can help to solve inverse and mixed problems, and to solve constraint problems. We discuss this idea with reference to the illustrative example of a pneumatic conveyor problem. The paper describes example problems faced by design engineers in this context and the issues that need to be considered in this approach. Solution of these problems require methods to handle constraints in both the retrieval phase and the adaptation phase of a typical CBR cycle. We show approaches to the solution of these problesm via a CBR tool.

A versatile characterization of causal relationships

This paper introduces a framework for representing versatile temporal relationships between events and their effects. The framework is based on a simple time model which characterizes each time element as a subset of the set of real numbers and allows expression of both absolute time values and relative temporal relations. The formalism presented here formally specifies the so-called most general temporal constraint (GTC), which guarantees the common-sense assertion that “the beginning of the effect cannot precede the beginning of the cause”. It is shown that there are in fact 8 possible causal relationships which satisfy GTC, including cases where, on the one hand, effects start simultaneously with, during, immediately after, or some time after their causes, and on the other hand, events end before, simultaneously with, or after their causes. The causal relationships characterized in this paper are versatile enough to subsume those representatives in the literature.

Integrating personnel movement simulation into preliminary ship design

Traditionally, when designing a ship the driving issues are seen to be powering, stability, strength and seakeeping. Issues related to ship operations and evolutions are investigated later in the design process, within the constraint of a fixed layout. This can result in operational inefficiencies and limitations, excessive crew numbers and potentially hazardous situations. University College London and the University of Greenwich are in the final year of a three year EPSRC funded research project to integrate the simulation of personnel movement into early stage ship design. This allows the assessment of onboard operations while the design is still amenable to change. The project brings together the University of Greenwich developed maritimeEXODUS personnel movement simulation software and the SURFCON implementation of the Design Building Block approach to early stage ship design, which originated with the UCL Ship Design Research team. Central to the success of this project is the definition of a suitable series of Naval Combatant Human Performance Metrics which can be used to assess the performance of the design in different operational scenarios. The paper outlines the progress made on deriving the human performance metric from human factors criteria measured in simulations and their incorporation into a Behavioural Matrix for analysis. It describes the production of a series of SURFCON ship designs based on the RN Type 22 Batch 3 frigate, and their analysis using the PARAMARINE and maritimeEXODUS software. Conclusions to date will be presented on the integration of personnel movement simulation into the preliminary ship design process.

Integrating personnel movement simulation into prelimary ship design

Traditionally, when designing a ship the driving issues are seen to be powering, stability, strength and seakeeping. Issues related to ship operations and evolutions are investigated later in the design process, within the constraint of a fixed layout. This can result in operational inefficiencies and limitations, excessive crew numbers and potentially hazardous situations. This paper summarises work by University College London and the University of Greenwich prior to the completion of a three year EPSRC funded research project to integrate the simulation of personnel movement into early stage ship design. This integration is intended to facilitate the assessment of onboard operations while the design is still highly amenable to change. The project brings together the University of Greenwich developed maritimeEXODUS personnel movement simulation software and the SURFCON implementation of the Design Building Block approach to early stage ship design, which originated with the UCL Ship Design Research team and has been implemented within the PARAMARINE ship design system produced by Graphics Research Corporation. Central to the success of this project is the definition of a suitable series of Performance Measures (PM) which can be used to assess the human performance of the design in different operational scenarios. The paper outlines the progress made on deriving the PM from human dynamics criteria measured in simulations and their incorporation into a Human Performance Metric (HPM) for analysis. It describes the production of a series of SURFCON ship designs, based on the Royal Navy’s Type 22 Batch 3 frigate, and their analysis using the PARAMARINE and maritimeEXODUS software. Conclusions on the work to date and for the remainder of the project are presented addressing the integration of personnel movement simulation into the preliminary ship design process.

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.

Model-based pilot and data power adaptation in psam with periodic delayed feedback

We consider the optimum design of pilot-symbol-assisted modulation (PSAM) schemes with feedback. The received signal is periodically fed back to the transmitter through a noiseless delayed link and the time-varying channel is modeled as a Gauss-Markov process. We optimize a lower bound on the channel capacity which incorporates the PSAM parameters and Kalman-based channel estimation and prediction. The parameters available for the capacity optimization are the data power adaptation strategy, pilot spacing and pilot power ratio, subject to an average power constraint. Compared to the optimized open-loop PSAM (i.e., the case where no feedback is provided from the receiver), our results show that even in the presence of feedback delay, the optimized power adaptation provides higher information rates at low signal-to-noise ratios (SNR) in medium-rate fading channels. However, in fast fading channels, even the presence of modest feedback delay dissipates the advantages of power adaptation.

Accelerating innovation in the built environment by research and education

Awareness of climate change and adaptations of building stock play a key role in the UK government’s environmental agenda. While some European countries and countries like Japan move forward by bringing their sustainability agenda to the public sector, the UK seems to be slow in embracing these ideas and long term sustainability in improved products and processes for better performance, efficiency and innovative application of renewable technology is yet to come. While funding remains a major constraint research show that a number of detrimental issues including; organisation, risk, mind sets of the stakeholders, planning constraints, reluctance to accept change and the unexploited markets are major contributing factors. Most of these barriers can be overcome with research, development and information and knowledge transfer techniques. Educating all stakeholders can act as an accelerator for innovation. This paper examines innovation in the built environment and how research and education can stimulate this process. It explores drivers and barriers for innovation and how research and education in construction, design, engineering and project management can enhance this process. It presents and discusses lessons learnt from two action research projects in relation to innovation.

Accelerating innovation in the social housing sector in UK

The UK government has been promoting innovation in the construction sector to improve the sustainability of the built environment. It has the potential and strength in developing construction research in design and engineering, but the impact of these processes seems to be slow in reaching the residential sector. While funding remains a major constraint research show that a number of detrimental issues including; organisation, risk, mind sets of the stakeholders, planning constraints,reluctance to accept change and the unexploited markets are major contributing factors. Most of these barriers can be overcome with research, development and information and knowledge transfer techniques. Educating all stakeholders can act as an accelerator for innovation. Given the large stock of existing dwellings, the situation is compounded, by issues related to climate change, to the point that this problem can no longer be ignored and requires an urgent response from all sectors involved. This paper attempts to highlight some of the key issues that are important in accelerating innovation in the housing sector. It briefly looks at the process of innovation in housing and presents lessons learnt from two research projects. The drivers and barriers and the role played by the government are examined in relation to the housing context.