Three-machine shop scheduling with partially ordered processing routes

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M1,M2 and M_{3}. A job is first processed on M1 and then is assigned either the route (M2,M_{3}) or the route (M_{3},M2). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.

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.

Two-machine flowshop scheduling problems with no-wait jobs

We study a two-machine flow shop scheduling problem with no-wait in process, in which one of the machines is not available during a specified time interval. We consider three scenarios of handing the operation affected by the nonavailability interval. Its processing may (i) start from scratch after the interval, or (ii) be resumed from the point of interruption, or (iii) be partially restarted after the interval. The objective is to minimize the makespan. We present an approximation algorithm that for all these scenarios delivers a worst-case ratio of 3/2. For the second scenario, we offer a 4/3-approximation algorithm.

Scheduling three-operation jobs in a two-machine flow shop to minimize makespan

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented.

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.

Single machine scheduling and due date assignment under series-parallel precedence constraints

We consider a single machine due date assignment and scheduling problem of minimizing holding costs with no tardy jobs tinder series parallel and somewhat wider class of precedence constraints as well as the properties of series-parallel graphs.

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.

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.