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.

Scheduling batches with sequential job processing for two-machine flow and open shops

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P6≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.

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.

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

An approximation algorithm for the two-machine flow shop with a single 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.

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.

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.

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.

Representations of multicultural identities in British Cinema

This paper explores the transnational and interstitial dimensions of cultural production in Britain today, and the representation of migrant and diasporic identities in contemporary mainstream British cinema. The box office success of films like Gurindha Chadha’s Bhaji on the Beach (1993) and Bend it Like Beckham (2002) and East is East (Daniel O’Donnell 1999) and their precursors My Beautiful Launderette (Stephen Frears 1985), Sammy and Rosie Get Laid (Stephen Frears 1987) and the TV mini-series Buddha of Suburbia (Roger Mitchell 1993) seem to celebrate and articulate a set of values around hybridity and alterity: a discourse of multiculturalism. This paper will engage with a series of key questions. Are there ideological values implicit within and common to all these texts? Can we map a rhetoric or discourse of multiculturalism within popular culture? Do mainstream representations of immigrant identities represent a discourse of resistance, a decolonising global culture or is this Western brand of multiculturalism still located within an Orientalising gaze? In what ways are multiculturalism and postcolonialism overlapping and yet opposing rhetorics? [From the Author]

'Chocolate makes you autism': impairment, disability and childhood identities

This paper discusses perceptions and experiences of impairment and disability from the perspectives of learning disabled children, their parents and their social workers. The author reports on findings from her doctoral study that adults often fail to take into account the views and experiences of learning disabled chidren. As a result, these children developed their own interpretations of impairment and disability based on their experiences and interactions with others. Whilst this indicates that they are active social interpreters, it also suggests that adults should make greater efforts to inform and consult learning disabled children. The author concludes by reflecting on the relevance of these findings to contemporary theories of disability and childhood.

SK1-like functors for division algebras

We investigate the group valued functor G(D) = D*/F*D' where D is a division algebra with center F and D' the commutator subgroup of D*. We show that G has the most important functorial properties of the reduced Whitehead group SK1. We then establish a fundamental connection between this group, its residue version, and relative value group when D is a Henselian division algebra. The structure of G(D) turns out to carry significant information about the arithmetic of D. Along these lines, we employ G(D) to compute the group SK1(D). As an application, we obtain theorems of reduced K-theory which require heavy machinery, as simple examples of our method.

Reduced K-theory for Azumaya algebras

Abstract In the theory of central simple algebras, often we are dealing with abelian groups which arise from the kernel or co-kernel of functors which respect transfer maps (for example K-functors). Since a central simple algebra splits and the functors above are “trivial” in the split case, one can prove certain calculus on these functors. The common examples are kernel or co-kernel of the maps Ki(F)?Ki(D), where Ki are Quillen K-groups, D is a division algebra and F its center, or the homotopy fiber arising from the long exact sequence of above map, or the reduced Whitehead group SK1. In this note we introduce an abstract functor over the category of Azumaya algebras which covers all the functors mentioned above and prove the usual calculus for it. This, for example, immediately shows that K-theory of an Azumaya algebra over a local ring is “almost” the same as K-theory of the base ring. The main result is to prove that reduced K-theory of an Azumaya algebra over a Henselian ring coincides with reduced K-theory of its residue central simple algebra. The note ends with some calculation trying to determine the homotopy fibers mentioned above.

Identity issues for looked after children with no knowledge of their origins - Implications for research and practice

In the area of child care policy and practice, the benefits for children who are separated from their birth parents of maintaining some form of connection with their family of origin is now widely accepted. The arguments in support of this are found mainly in research concerning adoption and stem from four inter-related themes: children's rights to know of their heritage and background; parents' rights to information about the well-being of their children; the benefits of having knowledge about origins; and concerns about the impact of not knowing. The effects on the developing identities of those who, for various reasons, are unlikely ever to know the details of their birth parent(s) is an under-researched issue. Karen Winter and Olivia Cohen use a case study to illustrate some of the gaps concerning knowledge in this area. They argue that there is much to be learnt from the development of research projects which have as their focus the accounts of children and young people, from a wide range of care arrangements, regarding identity issues where they have no connections with or knowledge about their birth parent(s).

Multiplicative spectra of Banach spaces

The multiplicative spectrum of a complex Banach space X is the class K(X) of all (automatically compact and Hausdorff) topological spaces appearing as spectra of Banach algebras (X,*) for all possible continuous multiplications on X turning X into a commutative associative complex algebra with the unity. The properties of the multiplicative spectrum are studied. In particular, we show that K(X^n) consists of countable compact spaces with at most n non-isolated points for any separable hereditarily indecomposable Banach space X. We prove that K(C[0,1]) coincides with the class of all metrizable compact spaces.