Multilevel refinement for the vehicle routing problem

Multilevel approaches to computational problems are pervasive across many areas of applied mathematics and scientific computing. The multilevel paradigm uses recursive coarsening to create a hierarchy of approximations to the original problem, then an initial solution is found for the coarsest problem and iteratively refined and improved at each level, coarsest to finest. The solution process is aided by the global perspective (or `global view') imparted to the optimisation by the coarsening. This paper looks at their application to the Vehicle Routing Problem.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

Using set operations to deal with the frame problem

This paper presents a simple approach to the so-called frame problem based on some ordinary set operations, which does not require non-monotonic reasoning. Following the notion of the situation calculus, we shall represent a state of the world as a set of fluents, where a fluent is simply a Boolean-valued property whose truth-value is dependent on the time. High-level causal laws are characterised in terms of relationships between actions and the involved world states. An effect completion axiom is imposed on each causal law, which guarantees that all the fluents that can be affected by the performance of the corresponding action are always totally governed. It is shown that, compared with other techniques, such a set operation based approach provides a simpler and more effective treatment to the frame problem.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

Multilevel refinement strategies for the capacity vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL algorithm, which uses a combination of standard VRP heuristics, is developed first to solve instances of the VRP. A ML version, which extends the global view of these heuristics, is then created, using variants of the construction and improvement heuristics at each level. Finally some multilevel enhancements are developed. Experimentation is used to find suitable parameter settings and the final version is tested on two well-known VRP benchmark suites. Results comparing both SL and ML algorithms are presented.

The application of multilevel refinement to the vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL heuristic, termed the combined node-exchange composite heuristic (CNCH), is developed first to solve instances of the VRP. A ML version (the ML-CNCH) is then created, using the construction and improvement heuristics of the CNCH at each level. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML 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.

Multilevel approaches applied to the capacitated clustering problem

This paper presents two multilevel refinement algorithms for the capacitated clustering problem. Multilevel refinement is a collaborative technique capable of significantly aiding the solution process for optimisation problems. The central methodologies of the technique are filtering solutions from the search space and reducing the level of problem detail to be considered at each level of the solution process. The first multilevel algorithm uses a simple tabu search while the other executes a standard local search procedure. Both algorithms demonstrate that the multilevel technique is capable of aiding the solution process for this combinatorial optimisation problem.

Workplace violence and intentions to quit: results from a survey of London nurses

Study Objective: Work-place violence, harassment and abuse is an increasing feature of nurses’ experience of work in many countries. There is some evidence that the experience of workplace violence affects levels of job satisfaction (Hesketh et al 2003) and career decisions (e.g. Mayer et al 1999, Fernandes et al 1999). This paper reports on verbal and physical abuse by patients, relatives and carers, as well as racial and sexual harassment in Acute Hospitals in London and investigates whether workplace violence affects nurses’ intentions to leave either their current job or the nursing profession, controlling for a number of other factors that are known to affect career decisions, such as workload, pay and own health. Method: A questionnaire designed by two of the authors (Reeves and West) to assess many different aspects of nurses work life was used in a postal survey of nurses grades A to I practising in twenty London acute trusts in 2002. A total of 6,160 clinical nurses were mailed the questionnaires and 2,880 returned completed questionnaires, resulting in an overall response rate of 47%, discounting undelivered questionnaires. Respondents worked in a wide variety of clinical settings but mainly in acute medical and surgical wards. In addition to descriptive statistics, results were analysed using logistic regression with robust standard errors: the appropriate test when the dependent variable is dichotomous and the individual respondents clustered within units (nurses working within hospitals are not statistically independent). Results: Our results show high levels of racial (%), sexual (%) and other, unspecified forms of harassment (%), as well as verbal and physical abuse (14% had been physically assaulted with 5% being assaulted more than once), over the previous 6 months. A very small number (1%) reported experiencing all three forms of harassment; 12% two forms and 29% one form. Only 45% of this sample intended to stay in nursing for at least 3 years; 40% were undecided and 15% intended to leave. Logistic regression estimates showed that reported levels of abuse and harassment had a significant impact on respondents’ career intentions, even in models that controlled for known factors affecting career decisions. About 70% of our respondents reported that they had had too little training in dealing with aggressive behaviour—or none at all—but there was no statistical relationship between lack of training and reported assaults. Conclusions: The international shortage of health care workers is due at least in part to low retention rates. It is crucial to investigate nurses’ experiences of work to identify the factors that shape their career decisions. Workplace violence is increasingly acknowledged as an international, service-wide, health care problem. This paper adds to the literature that shows that workplace violence has an impact on nurses’ career decisions. The implications for managers and policy makers are that strengthening systems of security and providing nurses with training in interpersonal relationships including dealing with aggressive patients could slow nurse turnover.