Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment

The paper considers the single machine due date assignment and scheduling problems with n jobs in which the due dates are to be obtained from the processing times by adding a positive slack q. A schedule is feasible if there are no tardy jobs and the job sequence respects given precedence constraints. The value of q is chosen so as to minimize a function ϕ(F,q) which is non-decreasing in each of its arguments, where F is a certain non-decreasing earliness penalty function. Once q is chosen or fixed, the corresponding scheduling problem is to find a feasible schedule with the minimum value of function F. In the case of arbitrary precedence constraints the problems under consideration are shown to be NP-hard in the strong sense even for F being total earliness. If the precedence constraints are defined by a series-parallel graph, both scheduling and due date assignment problems are proved solvable in time, provided that F is either the sum of linear functions or the sum of exponential functions. The running time of the algorithms can be reduced to if the jobs are independent. Scope and purpose We consider the single machine due date assignment and scheduling problems and design fast algorithms for their solution under a wide range of assumptions. The problems under consideration arise in production planning when the management is faced with a problem of setting the realistic due dates for a number of orders. The due dates of the orders are determined by increasing the time needed for their fulfillment by a common positive slack. If the slack is set to be large enough, the due dates can be easily maintained, thereby producing a good image of the firm. This, however, may result in the substantial holding cost of the finished products before they are brought to the customer. The objective is to explore the trade-off between the size of the slack and the arising holding costs for the early orders.

Constructive notice and independent legal advice: a study of lending institution practice

Cases on when lending institutions will be put on inquiry as to circumstances giving rise to presumption of undue influence, and results of research on lending practice of residential mortgage lenders in light of case law. [From Legal Journals Index]

Law in the community: the University of Greenwich/Greenwich Association of Disabled People Centre for Independent Living (GAD) research project

The GAD Advocacy Service is funded by the London Borough of Greenwich Directorate of Neighbourhood Services; its remit to support disabled people experiencing Hate Crime, Domestic Violence and Harassment. Run by disabled personnel and giving advice to all disabled people it is unique in London. Since its inception in 2004, the Advocacy Service has been stretched to its limit - there is a need to extend the remit of the Advocacy Service to give specialist legal advice on other issues. In 2003, the CEDRM-UK project was set up in the University of Greenwich Law Department as part of the Disability Rights Promotion International Legal Education and Research Project; its objectives were firstly, to facilitate the collection of data on the effectiveness of legislation in promoting the rights of disabled persons; and secondly, to pilot new methods in teaching and training in Human Rights Law – students acquire an expertise in Human Rights Law through research into the practical application of legislation relating to civil and human rights in the daily life of the community. In July 2007, GAD and CEDRM-UK embarked on a joint project to report on the work of the Advocacy Service and to create a database to support its caseload. The 2008-9 Project team will report on their work and findings relating to facilitating equality in the workplace; the inclusion of cancer, HIV and multiple sclerosis within the legal definition of disability and the implications of the statutory duty to promote disability equality for the provision of extracurricular activities for schoolchildren. [From the Author]

Multiple-locus sequence typing analysis of Bacillus thuringiensis recovered from the phylloplane of clover (Trifolium hybridum) in vegetative form

The chromosomal genotype, as judged by multi locus sequence typing, and the episomal genotype, as judged by plasmid profile and cry gene content, were analyzed for a collection of strains of Bacillus thuringiensis. These had been recovered in vegetative form over a period of several months from the leaves of a small plot of clover (Trifolium hybridum). A clonal population structure was indicated, although greater variation in sequence types (STs) was discovered than in previous collections of B. cereus/B. thuringiensis. Isolates taken at the same time had quite different genotypes, whereas those of identical genotypes were recovered at different times. The profiles of plasmid content and cry genes generally bore no relation to each other nor to the STs. Evidently, although relatively little recombination was occurring in the seven chromosomal genes analyzed, a great deal of conjugal transfer, and perhaps recombination, was occurring involving plasmids. A clinical diarrheal isolate of B. cereus and the commercial biopesticide strain HD-1 of B. thuringiensis, both included as out-groups, were found to have very similar STs. This further emphasizes the role of episomal elements in the characteristics and differentiation of these two species.

Fostering 'habits of reflection, independent study and free inquiry': an analysis of the short-lived phenomenon of General/Liberal Studies in English vocational education and training

In 1957, 12 years after the end of World War II, the Ministry of Education issued Circular 323 to promote the development of an element of ‘liberal studies’ in courses offered by technical and further education (FE) colleges in England. This was perceived to be in some ways a peculiar or uncharacteristic development. However, it lasted over 20 years, during which time most students on courses in FE colleges participated in what were termed General or Liberal Studies classes that complemented and/or contrasted with the technical content of their vocational programmes. By the end of the 1970s, these classes had changed in character, moving away from the concept of a ‘liberal education’ towards a prescribed diet of ‘communication studies’. The steady decline in apprenticeship numbers from the late 1960s onwards accelerated in the late 1970s, resulting in a new type of student (the state-funded ‘trainee’) into colleges whose curriculum would be prescribed by the Manpower Services Commission. This paper examines the Ministry’s thinking and charts the rise and fall of a curriculum phenomenon that became immortalised in the ‘Wilt’ novels of Tom Sharpe. The paper argues that the Ministry of Education’s concerns half a century ago are still relevant now, particularly as fresh calls are being made to raise the leaving age from compulsory education to 18, and in light of attempts in England to develop new vocational diplomas for full-time students in schools and colleges.