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.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

On-line algorithms for single machine scheduling with family setup times

The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.

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

Effect of adding 0.3 wt% Ni into the Sn–0.7 wt%Cu solder: part I: wetting behavior on Cu and Ni substrates

Comparative wetting behavior of Sn-0.7Cu and Sn-0.7Cu-0.3Ni solders on Cu and Ni substrates were assessed through the wetting balance test. No-clean (NC), non-activated (R) and water soluble organic acid (WS) fluxes were used to assess the wetting behavior for three different solder bath temperatures of 255, 275 and 295 °C. Experimental results unveiled that adding of 0.3 wt% Ni into Sn-0.7Cu solder can improve the wetting on Cu substrate when NC and WS fluxes are used. However, such addition of Ni did not improve the wetting of Sn-0.7Cu solder for R-type flux. In the case of Ni substrate, addition of Ni helped to improve the wetting for all three types of fluxes as higher wetting forces were documented for Sn-0.7Cu-0.3Ni solder compared to the Sn-0.7Cu solder. Among the fluxes, worst performance was observed for R-type flux. Very large contact angles were recorded for both solders with this kind of flux. Experimental results also revealed that higher solder bath temperature played an important role to lower the contact angle, to increase the wetting force and to enhance the wetting. Computer modeling of wetting balance test also revealed that both the wetting force and meniscus height are inversely proportional to the contact angles. Besides, solder bath depth and radius do not affect significantly on the wetting behavior.

Effect of adding 0.3wt% Ni into the Sn-0.7wt% Cu solder - Part II: Growth of intermetallic layer with Cu during wetting and aging

The growth behavior of intermetallic layer with or without adding 0.3 wt% Ni into the Sn-0.7Cu solder was studied during the wetting reaction on Cu-substrate and thereafter in solid-state aging condition. The Cu-solder reaction couple was prepared at 255, 275 and 295 °C for 10 s. The samples reacted at 255 °C were then isothermally aged for 2-14 days at 150 °C. The reaction species formed for the Sn-0.7Cu/Cu and Sn-0.7Cu-0.3Ni/Cu soldering systems were Cu6Sn5 and (CuNi)6Sn5, respectively. The thickness of the intermetallic compounds formed at the solder/Cu interfaces and also in the bulk of both solders increased with the increase of reaction temperature. It was found that Ni-containing Sn-0.7Cu solder exhibited lower growth of intermetallic layer during wetting and in the early stage of aging and eventually exceeded the intermetallic layer thickness of Sn-0.7Cu/Cu soldering system after 6 days of aging. As the aging time proceeds, a non-uniform intermetallic layer growth tendency was observed for the case of Sn-0.7Cu-0.3Ni solder. The growth behavior of intermetallic layer during aging for both solders followed the diffusion-controlled mechanism. The intermetallic layer growth rate constants for Sn-0.7Cu and Sn-0.7Cu-0.3Ni solders were calculated as 1.41 × 10-17 and 1.89 × 10-17 m2/s, respectively which indicated that adding 0.3 wt% Ni with Sn-0.7Cu solder contributed to the higher growth of intermetallic layer during aging. © 2006 Elsevier B.V. All rights reserved.

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.

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]