Non-preemptive two-machine open shop scheduling with non-availability constraints

We study a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. No preemption is allowed in the processing of any operation. The objective is to minimize the makespan. We consider approximability issues of the problem with more than one non-availability intervals and present an approximation algorithm with a worst-case ratio of 4/3 for the problem with a single non-availability interval.

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.

Two-Machine Shop Scheduling with an Uncapacitated Interstage Transporter

In this paper we study the two-machine flow shop and open shop problems to minimize the makespan with a single interstage transporter that may carry any number of jobs between the machines at a time. For each of these problems we present a best possible approximation algorithm within a class of schedules with at most two shipments. As a by-product of this research, for the problem of minimizing the makespan on parallel identical machines we analyze the ratio of the makespan for a non-preemptive schedule over the makespan of a preemptive schedule.

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.

Transporting jobs through a two-machine open shop

We consider the two-machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a 7/5-approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009

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.

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]

‘Nothing will prevent me from doing a good job’. The professionalisation of part-time teaching staff in further and adult education

Approximately 85,000 part-time teaching staff working in further education (FE) and adult and community learning (ACL) are often seen as ‘a problem’. The intrinsic ‘part-timeness’ of these staff tends to marginalise them: they remain under-recognised and largely unsupported. Yet this picture is over-simplified. This article examines how part-time staff make creative use of professional autonomy and agency to mitigate problematic ‘casual employment’ conditions, reporting on results from Learning and Skills Development Agency-sponsored research (2002–2006) with 700 part-time staff in the learning and skills sector. The question of agency was reported as a key factor in part-time employment. Change is necessary for the professional agency of part-timers to be harnessed as the sector responds to ambitious sectoral ‘improvement’ agendas following the Foster Report and FE White Paper. Enhanced professionalisation for part-time staff needs greater recognition and inclusion in change agendas.