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.

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.

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.

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.

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

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.

Scheduling parallel dedicated machines with the speeding-up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two-machine problem is NP-hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst-case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple-choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

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.

Tied to the job: affective and relational components of nurse retention

Paper investigates whether affective and relational components of nurses' experience of work have a significant impact on their intentions to leave either the job or the nursing profession in models that control for other factors (sociodemographic, work conditions, perceptions of quality of care) that are known to affect career decisions. [Abridged Abstract]