A polynomial algorithm for the three-machine open shop with a bottleneck machine

The paper considers the three‐machine open shop scheduling problem to minimize themakespan. It is assumed that each job consists of at most two operations, one of which is tobe processed on the bottleneck machine, the same for all jobs. A new lower bound on theoptimal makespan is derived, and a linear‐time algorithm for finding an optimalnon‐preemptive schedule is presented.

Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m⩾2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation.

An open shop scheduling problem with a non-bottleneck machine

This paper considers the problem of processing n jobs in a two-machine non-preemptive open shop to minimize the makespan, i.e., the maximum completion time. One of the machines is assumed to be non-bottleneck. It is shown that, unlike its flow shop counterpart, the problem is NP-hard in the ordinary sense. On the other hand, the problem is shown to be solvable by a dynamic programming algorithm that requires pseudopolynomial time. The latter algorithm can be converted into a fully polynomial approximation scheme that runs in time. An O(n log n) approximation algorithm is also designed whi finds a schedule with makespan at most 5/4 times the optimal value, and this bound is tight.

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.

Social and demographic factors of young fathers in the UK and USA

Research on disadvantaged young fathers has been minimally addressed in the literature, particularly in the UK. In both countries teenage pregnancy rates are high and costly in terms of social policy and community provision. This paper explores 2 studies involving 24 young men with an average age of 17 on the transition to young fatherhood; one study was conducted in the UK with white young men and the other in the USA with black young men. The findings from both studies indicated common themes from their stories, particularly with regard to the high levels of disadvantage and social exclusion they had been exposed to in their demographic environments and the anti-social behaviour they described engaging in, prior to the birth of their child/ren. Specifically, a significant proportion of the young men described how they had been immersed in drug and gun crimes and how this shaped their lives and neighbourhoods. Becoming fathers is presented by both sets of young men as rescuing them from this criminal lifestyle.

Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

Abstract not available

A polynomial algorithm for the three-machine open shop with a bottleneck machine

Abstract not available

Two-stage open shop scheduling with a bottleneck machine

Abstract not available