Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

Group technology approach to the open shop scheduling problem with batch setup times

This paper studies the problem of scheduling jobs in a two-machine open shop to minimize the makespan. Jobs are grouped into batches and are processed without preemption. A batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. For this NP-hard problem, we propose a linear-time heuristic algorithm that creates a group technology schedule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a -approximation algorithm. Moreover, we show that no group technology algorithm can guarantee a worst-case performance ratio less than 5/4.

Scheduling batches with sequential job processing for two-machine flow and open shops

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.

Scheduling batches with simultaneous job processing for two-machine shop problems

We consider the problem of scheduling independent jobs on two machines in an open shop, a job shop and a flow shop environment. Both machines are batching machines, which means that several operations can be combined into a batch and processed simultaneously on a machine. The batch processing time is the maximum processing time of operations in the batch, and all operations in a batch complete at the same time. Such a situation may occur, for instance, during the final testing stage of circuit board manufacturing, where burn-in operations are performed in ovens. We consider cases in which there is no restriction on the size of a batch on a machine, and in which a machine can process only a bounded number of operations in one batch. For most of the possible combinations of restrictions, we establish the complexity status of the problem.

Numerical simulation of vacuum dezincing of lead alloy

Removing zinc by distillation can leave the lead bullion virtually free of zinc and also produces pure zinc crystals. Batch distillation is considered in a hemispherical kettle with water-cooled lid, under high vacuum (50 Pa or less). Sufficient zinc concentration at the evaporating surface is achieved by means of a mechanical stirrer. The numerical model is based on the multiphysics simulation package PHYSICA. The fluid flow module of the code is used to simulate the action of the stirring impeller and to determine the temperature and concentration fields throughout the liquid volume including the evaporating surface. The rate of zinc evaporation and condensation is then modelled using Langmuir’s equations. Diffusion of the zinc vapour through the residual air in the vacuum gap is also taken into account. Computed results show that the mixing is sufficient and the rate-limiting step of the process is the surface evaporation driven by the difference of the equilibrium vapour pressure and the actual partial pressure of zinc vapour. However, at higher zinc concentrations, the heat transfer through the growing zinc crystal crust towards the cold steel lid may become the limiting factor because the crystallization front may reach the melting point. The computational model can be very useful in optimising the process within its safe limits.

Batching decisions for assembly production systems

The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching.

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.

Integrating personnel movement simulation into preliminary ship design

Traditionally, when designing a ship the driving issues are seen to be powering, stability, strength and seakeeping. Issues related to ship operations and evolutions are investigated later in the design process, within the constraint of a fixed layout. This can result in operational inefficiencies and limitations, excessive crew numbers and potentially hazardous situations. University College London and the University of Greenwich are in the final year of a three year EPSRC funded research project to integrate the simulation of personnel movement into early stage ship design. This allows the assessment of onboard operations while the design is still amenable to change. The project brings together the University of Greenwich developed maritimeEXODUS personnel movement simulation software and the SURFCON implementation of the Design Building Block approach to early stage ship design, which originated with the UCL Ship Design Research team. Central to the success of this project is the definition of a suitable series of Naval Combatant Human Performance Metrics which can be used to assess the performance of the design in different operational scenarios. The paper outlines the progress made on deriving the human performance metric from human factors criteria measured in simulations and their incorporation into a Behavioural Matrix for analysis. It describes the production of a series of SURFCON ship designs based on the RN Type 22 Batch 3 frigate, and their analysis using the PARAMARINE and maritimeEXODUS software. Conclusions to date will be presented on the integration of personnel movement simulation into the preliminary ship design process.

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.

Integrating personnel movement simulation into prelimary ship design

Traditionally, when designing a ship the driving issues are seen to be powering, stability, strength and seakeeping. Issues related to ship operations and evolutions are investigated later in the design process, within the constraint of a fixed layout. This can result in operational inefficiencies and limitations, excessive crew numbers and potentially hazardous situations. This paper summarises work by University College London and the University of Greenwich prior to the completion of a three year EPSRC funded research project to integrate the simulation of personnel movement into early stage ship design. This integration is intended to facilitate the assessment of onboard operations while the design is still highly amenable to change. The project brings together the University of Greenwich developed maritimeEXODUS personnel movement simulation software and the SURFCON implementation of the Design Building Block approach to early stage ship design, which originated with the UCL Ship Design Research team and has been implemented within the PARAMARINE ship design system produced by Graphics Research Corporation. Central to the success of this project is the definition of a suitable series of Performance Measures (PM) which can be used to assess the human performance of the design in different operational scenarios. The paper outlines the progress made on deriving the PM from human dynamics criteria measured in simulations and their incorporation into a Human Performance Metric (HPM) for analysis. It describes the production of a series of SURFCON ship designs, based on the Royal Navy’s Type 22 Batch 3 frigate, and their analysis using the PARAMARINE and maritimeEXODUS software. Conclusions on the work to date and for the remainder of the project are presented addressing the integration of personnel movement simulation into the preliminary ship design process.

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.

Ag+- and Zn2+-exchange kinetics and antimicrobial properties of 11 angstrom tobermorites

Ag+- and Zn2+-exchanged zeolites zeolites and clays have been used as coatings and in composites to confer broad-spectrum antimicrobial properties on a range of technical and biomedical materials. 11 angstrom tobermorite is a bioactive layer lattice ion exchanger whose potential as a carrier for Ag+ and Zn2+ ions in antimicrobial formulations has not yet been explored. In view of this, batch Ag+- and Zn2+-exchange kinetics of two structurally distinct synthetic 11 angstrom tobermorites and their subsequent bactericidal action against Staphylococcus aureus and Pseudomonas aeruginosa are reported. During the exchange reactions, Ag+ ions were found to replace labile interlayer cations; whereas, Zn2+ ions also displaced structural Ca2+ ions from the tobermorite lattice. In spite of these different mechanisms, a simple pseudo-second-order model provided a suitable description of both exchange processes (R-2 >= 0.996). The Ag+- and Zn2+-exchanged tobermorite phases exhibited marked bacteriostatic effects against both bacteria, and accordingly, their potential for use as antimicrobial materials for in situ bone tissue regeneration is discussed. (C) 2008 Elsevier Ltd. All rights reserved.

Call admission control algorithms in OFDM-based wireless multiservice networks

Orthogonal frequency division multiplexing(OFDM) is becoming a fundamental technology in future generation wireless communications. Call admission control is an effective mechanism to guarantee resilient, efficient, and quality-of-service (QoS) services in wireless mobile networks. In this paper, we present several call admission control algorithms for OFDM-based wireless multiservice networks. Call connection requests are differentiated into narrow-band calls and wide-band calls. For either class of calls, the traffic process is characterized as batch arrival since each call may request multiple subcarriers to satisfy its QoS requirement. The batch size is a random variable following a probability mass function (PMF) with realistically maximum value. In addition, the service times for wide-band and narrow-band calls are different. Following this, we perform a tele-traffic queueing analysis for OFDM-based wireless multiservice networks. The formulae for the significant performance metrics call blocking probability and bandwidth utilization are developed. Numerical investigations are presented to demonstrate the interaction between key parameters and performance metrics. The performance tradeoff among different call admission control algorithms is discussed. Moreover, the analytical model has been validated by simulation. The methodology as well as the result provides an efficient tool for planning next-generation OFDM-based broadband wireless access systems.

Changes in the properties of Bacillus thuringiensis after prolonged culture in a rich medium

AIM: To investigate the effect of repeated culture in a rich medium on certain genetic, metabolic, pathogenic and structural characteristics of fresh isolates of Bacillus thuringiensis. METHODS AND RESULTS: Four strains of B. thuringiensis, which had been isolated in vegetative form from leaf surfaces, were grown for 500 generations in batch culture in a rich medium. One of the strains, S4g, differed from the parent in the following respects: greater cell width; changed plasmid profile; complete loss of ability to produce delta-endotoxins; loss of ability to produce beta-exotoxin and disruption of vip3 gene; radically different fatty acid composition; and altered metabolic activity. Two of the other evolved strains (S1g and S6g) showed differences in fatty acid profiles compared with the parents. Genetic finger-printing showed that there were also mutations in the cry genes of two of the evolved strains (S1g and S2g). The delta-endotoxins of strain S6g were significantly less toxic to the larvae of Pieris brassica compared with those of the parent and it also differed in the plasmid content. CONCLUSION: Radical and unpredictable changes can occur in fresh isolates of B. thuringiensis when subjected to growth in the laboratory. SIGNIFICANCE AND IMPACT OF THE STUDY: This is the first analysis of a Gram positive and biotechnologically significant bacterium after repeated laboratory culture. It is of great relevance to the biotechnological exploitation of B. thuringiensis that prolonged growth of environmental isolates on laboratory culture media can have profound effects on their structure, genome and virulence determinants.