An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

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.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

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

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.

Ghost/Machine: cinema in a digital age

Cinema, with its passive cinematic apparatus and linear narrative is often characterised as a contrast to new media narrative strategies, yet from Vertov’s Man with a Movie Camera to Mike Figgis’ TimeCode and Wong Kar Wei’s 2046 cinema provides narrative strategies and spatial conceptualisations which prefigure or are contiguous with new media environments. Both our perception of what cyberspace constitutes and the technology that actualises those perceptions arise out of and are driven by fantasy and desire. This paper will explore the metaphors used to represent and understand new media aesthetics through cinematic representations of new media environments. Two key themes relevant to new media aesthetics emerge. Irigaray, Haraway, and Grosz are used to explore the de-essentialising haptic and penetrative potential of new technologies and their ability to collapse the boundary between the body and the machine. The second fantasy, of new media as a liminal space that expresses the memorialising function of technology and its relation to mourning, is analysed using Benjamin, Burgin and Rutsky. These altered spaces and perceptions of the body and memory of the post-cinematic subject are illustrated through an analysis of Gondry’s Eternal Sunshine of the Spotless Mind and Jonze’s Being John Malkovich. [From the Author]

Effect of machine dependence on wall failure property measurements, Jenike versus an annular shear tester

Annular, ring or torsional shear testers are commonly used in bulk solids handling research for the purpose of powder characterisation or equipment design. This paper reports from a DEFRA sponsored project which aims to develop an industrial powder flow-ability tester, (based on the annular shear tester) that is economic to buy and quick and easy to use in trained but unskilled hands. This paper compares the wall failure loci measured with an annular shear cell with measurements obtained using the accepted standard wall friction tester, the Jenike shear cell. These wall failure loci have been measured for several bulk solids which range from fine cohesive powders to free-flowing granular materials, on a stainless steel 304 2B wall surface.