Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders (as in the job-shop), while the operations of the other jobs may be processed in arbitrary order (as in the open-shop). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

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.

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.

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.

Adult personality inconsistency and problems with parents: uncovering the roots of the false self

Research has established that individuals who tend to vary their personality depending on who they are with, show a variety of signs of psychological maladjustment in comparison to those who do not; they show more negative affect (Baird, Le and Lucas, 2006), lower life satisfaction (Suh, 2002), lower self-esteem (Sheldon et al., 1997), lower role-satisfaction (Donahue et al., 1993), higher rates of depression (Lutz and Ross, 2003), more anxiety (Diehl, Hastings and Stanton, 2001) and poorer physical health (Cross, Gore and Morris, 2003). It has also been shown that personality variability is positively related to the experience of inauthenticity and falsity (Sheldon et al., 1997). Donahue, Roberts, Robins and John (1993) found that personality inconsistency of this type is related to tension within the family. Psychoanalytic theory has also linked the operation of an adult false self to experiences with parents, particularly in early life (Winnicott, 1960). It was hypothesized that personality variability and the adult experience of falsity in social situations would be related to an emotionally unstable relationship with parents. The method to test this comprised a questionnaire-based survey given to a non-clinical population. The final sample comprised 305, with 193 women and 112 men, aged from 19 to 55. The first questionnaire asked participants to rate personality traits, including emotional stability, in three social contexts - with parents, with friends and with work colleagues. The second part involved 3 questions; participants were asked to select in which of the aforementioned three social contexts they felt “most themselves”; in which they were “most authentic” and in which they “put on a front”. It was found, consistent with predictions, that an index of overall personality variability calculated from the personality questionnaire correlated strongly with emotional instability around parents (r = 0.46, p<0.001), while not correlating with emotional instability in either of the other two contexts measured. This suggests a specific link between a person’s relationship with their parents and their overall personality integration. Furthermore, it was found that participants who cited one of the three social contexts (parents, friends, work colleagues) as being one in which they were “more themselves” or “more authentic” had significantly higher ratings of emotional instability with parents than those participants who found that they were equally authentic across settings (F = 9.8, p<0.005). The results suggest a clear link between a person’s relationships with their parents and their adult personality integration. An explanation is that individuals who experience an anxious or ambiguous attachment with their parents in childhood may fear rejection or abandonment in later life, and so habitually adapt their personality to fit in to social contexts as adults, in order to be accepted by others and to minimize the possibility of social rejection. These individuals meanwhile retain an emotionally unstable relationship with their parents in adulthood. This interpretation is speculative but is open to empirical testing. Clinicians should be aware that attachment problems with parents may underlie poor personality integration in adulthood.

Multi-stage scheduling problems with precedence constraints

Abstract not available

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is NP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore-Gomory traveling salesman problem and solve it in polynomial time. (c) 2000 John Wiley & Sons, Inc.

Complexity of mixed shop scheduling problems: A survey

We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to establishing the boundary between polynomially solvable and NP-hard problems. When the number of operations per job is unlimited, we focus on problems with a fixed number of jobs.

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.

Guidance on interviewing child witnesses in Scotland

The guidance was commissioned from Dr Amina Memon and Lynn Hulse at Aberdeen University. Their work was overseen by a steering group with representatives from the Scottish Executive Justice Department, the Crown Office and Procurator Fiscal Service, NCH Scotland, the Association of Chief Police Officers in Scotland, the Association of Directors of Social Work, the Law Society for Scotland, the Scottish Association of Community Child Health and the Scottish Children’s Reporter Administration. A full list of those involved is given in the Appendix C. pt. 1. Guidance on interviewing child witnesses in Scotland -- pt. 2. Guidance on the questioning of children in court -- pt. 3. Lord Justice-General's memorandum on child witnesses: appendix to Guidance on the questioning of children in court -- pt. 4. Guidance on child witness court familiarisation visits -- pt. 5. Information about child, young and vulnerable adult witnesses to inform decision-making in the legal process: good practice guide -- pt. 6. Code of practice to facilitate the provision of therapeutic support to child witnesses in court proceedings -- pt. 7. Guidance on the conduct of identity parades with child witnesses.

Schedules with due-date assignment and position-dependent processing times

Single machine scheduling problems are considered, in which the processing of jobs depend on positions of the jobs in a schedule and the due-dates are assigned either according to the CON rule (a due-date common to all jobs is chosen) or according to the SLK rule (the due-dates are computed by increasing the actual processing times of each job by a slack, common to all jobs). Polynomial-time dynamic programming algorithms are proposed for the problems with the objective functions that include the cost of assigning the due-dates, the total cost of disgarded jobs (which are not scheduled) and, possibly, the total earliness of the scheduled jobs.

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.

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.