Search

We consider the problem of mining association rules on a shared-nothing multiprocessor. We present three algorithms that explore a spectrum of trade-offs between computation, communication, memory usage, synchronization, and the use of problem-specific information. The best algorithm exhibits near perfect scaleup behavior, yet requires only minimal overhead compared to the current best serial algorithm. Index Terms - Data mining, association rules, parallel algorithms.

The nonhomogeneous normalized version of the delayed least mean square algorithm with a decreasing step size has sure convergence in a mixing input condition and when a certain law of large numbers is satisfied. In nonhomogeneous case, rigorous sample convergence analysis for the least mean square type algorithms, when they are made to operate with a delay in the coefficient adaption, is absent.

A large number of algorithms exist for digital control which work well with high precision floating point computation. When implemented in finite wordlength processors without inherent floating point capability, these control algorithms often fail to demonstrate their effectiveness. The software described here has been developed to test the performance of digital controllers under such finite wordlength situations. It is also shown, how, with a suitable restructuring of the conventional discrete-time shift operator models, considerably improved robustness to such situations can be achieved with marginally added computations. Key words: Controller implementation, fixed-point arithmetic, finite wordlength control.

The asymptotic performance of the second-order ESPRIT, fourth-order ESPRIT and virtual ESPRIT (VESPA) algorithhm was assessed. Specifically, the asymptotic variance of the direction-of-arrival estimates derived by the least squares versions of the algorithms was analyzed under the assumption of a non-Gaussian signal. Second-order ESPRIT was found to be the best estimator based on the results and Monte Carlo simulations.

Performance analysis of four parallel sorting algorithms using the LogP model shows that the model is a good predictor of communication performance. The LogP model uses communication latency, overhead, bandwidth and the number of processors as parameters. The analysis involves the implementation of the algorithms in Split-C, followed by comparison of the LogP-predicted performances and the actual ones on a CM-5 for a range of problem sizes. Results from the study suggest that overhead is the most important communication parameter in sorting algorithms.

A restricted dynamic programming heuristic algorithm has been developed for the time dependent traveling salesman problem (TSP). The new algorithm cannot guarantee optimality since it retains only a user-specified number of partial tours at each stage. However, it permits the user to choose a middle ground between an optimal solution and a nearest-neighbor solution. It can also solve TSPs which are larger than the exact algorithm.

The reliability of an image analysis algorithm for atomic force microscopy (AFM) of thin metal films was evaluated by comparison with manual analysis of images and transmission electron micrographs of Ag films deposited on Formvar-coated Cu grids. In order to extract quantitative nanostructural information using the algorithm discussed herein, the optimal fitting parameters were found to be low-pass filtering to reject high-frequency noise, a 5 x 5 point grid for identification of particle maxima, and a linear least-squares fit to a hemispheroidal model of particle shape. Metal particle dimensions were defined from the height and radius of the hemispheroid fit. Due to the close spacing of particles in these Ag films, tip geometry causes the greatest error in the height measurements, rather than width measurements. In addition, the effect of scanning parameters such as scan rate and size, applied load, and humidity on particle count and dimensions was examined. Increasing the scan rate reduced the number of resolvable Ag particles, decreased the apparent particle height, and increased the apparent particle radius. Under conditions of low capillary force, a net repulsive force of [approximately]19 nN resulted in subtle tip-induced changes in the Ag surface morphology. The Ag film surface was damaged at a net repulsive force of [approximately]23 nN. At slow scan rates, the moisture layer did not significantly affect the quality of the AFM images obtained over a broad relative humidity range. Finally, the Ag surface structure was found to be very homogeneous over a relatively large area.

A space-marching technique is proposed for solving the inverse heat conduction-radiation problem associated with the estimation of surface temperatures and fluxes from simulated transient temperatures. The technique uses an iterative algorithm to analyze different values of the conduction-radiation parameter. Its computational time is also one order of magnitude smaller than other type of methods used in solving the inverse heat conduction-radiation problem.

The problem of scheduling the one-time production of several units of a single product is examined. To this end, the problem is modelled using two penalty cost structures to account for trade-off between the need to finish each unit by a certain due date and learning-on-the-job effects. In addition, the performances of a simulated annealing procedure, a genetic algorithm and a pair-wise swap heuristic for solving the problem are compared.

This paper presents a mathematical review of methods and algorithms used to compute milling cutter placement for multi-axis finished-surface machining. In general, these methods and algorithms compute tool path points based on tangent-plane contact between the milling cutter and the surface while maintaining a fixed tool orientation. This tangent-plane method of tool positioning and orientation is examined by discussing its strengths and weaknesses. Errors resulting from the tangent-plane approach are typically determined using a posteriori cutter path checking and graphic visualization techniques. Although these checking techniques have proved useful in identifying the tool path errors before actual machining, the problem of generating an error-free tool path remains. In this paper, we discuss the analysis of tool path position and orientation data as they are generated. This a priori analysis method is used to show error locations along the lateral face of the tool. The conclusion is reached that additional research is needed in the area of simultaneous multi-axis tool path planning, if errors are to be eliminated and the efficiency of the milling machine is to be improved. The reader is referred to research efforts that extend beyond the traditional or computer-aided design (CAD, vendor supplied) tool path planning methods. Some of these efforts show great promise in eliminating gouging and improves machine tool efficiency., 1. Introduction To achieve the intended performance of a product (e.g., an impeller or turbine blade) or capture its desired aesthetics (e.g., a car fender or hood), engineers and designers [...]

R.M. Russell and L.J. Krajewski took into account the transportation rate structure for less-than-truckload shipments in their optimal purchase order quantity algorithm. Application of the algorithm to a wide array of freight classes and lengths-of-haul shows that the use of freight rate schedules with the algorithm led to errors in order size decisions. Slight adjustments to the algorithm are needed before it can be used to determine the optimal purchase order quantity and the lowest total annual cost.

The overlapping generations economies in which agents employ genetic algorithms to learn correct decision rules, are examined. Results from computer simulations indicate that a genetic algorithm converges to the unique monetary steady state in case of a constant money supply policy and to the low-inflation stationary equilibrium in case of a constant real deficit financed through seignorage. The characteristics of genetic algorithm adaptation are contrasted with the ability of other learning algorithms.

When a common object, attached to multiple robot arms, is cooperatively manipulated to move along a constrained surface, the control task requires the simultaneous control of the motion trajectory of the attached object on the constrained surface; the constrained force due to the contact with the surface; and the internal force exerted by the arms on the object. To accomplish such a control objective, an adaptive sliding mode control algorithm is presented by developing a new concise dynamic model of the system and exploiting its particular properties. Detailed analysis on the tracking properties of the object's position, the constrained force, and the internal force are given. The stability analysis shows that the proposed algorithm can achieve satisfactory tracking performance.

It is well known that dc offsets degrade the performance of analog adaptive filters. In this paper, the effects of dc offsets on four variations of the stochastic gradient algorithm are analyzed. Assuming a Gaussian probability distribution for the input signal and error signal, the output mean squared error (MSE) performance in the presence of dc offsets is evaluated for each of the algorithms. The theoretical work is compared with computer simulations and the results, together with convergence properties of each of the algorithms and their respective hardware requirements, are used in selecting the most appropriate algorithm. Although a Gaussian input distribution is assumed, it may reasonably be inferred that the critical results obtained should also hold for other input distributions.

The Viterbi Algorithm (VA) is the maximum likelihood decoding algorithm for convolutionally encoded data. Improvements in the performance of a concatenated coding system that uses VA decoding (inner decoder) can be obtained when, in addition to the standard VA output, an indicator of the reliability of the VA decision is delivered to the outer stage of processing. Two different approaches of extending the VA are considered. In the first approach, the VA is extended with a Soft Output (SOVA) unit that calculates reliability values for each of the decoded output information symbols. In the second approach, coding gains are obtained by delivering a list of the L best estimates of the transmitted data sequence, List Viterbi decoding Algorithm (LVA). In this work, our main interest is to evaluate LVA and SOVA in comparison to each other, determine suitable applications for both algorithms and to construct extended versions of LVA and SOVA with low complexity that perform the task of the other algorithm. We define a List Output VA using the output symbol reliability information of the SOVA to generate a list of size L and that also has a lower complexity than the regular LVA for a long list size. We evaluate the List-SOVA in comparison to the LVA. Further, we introduce a low complexity Soft Symbol Output Viterbi algorithm that accepts the (short) list output of the LVA and calculates for each of the decoded information bits a reliability value. The complexity and the performance of the Soft-LVA (LVA and soft decoding unit) is a function of the list size L. The performances of Soft-LVA and SOVA are compared in a concatenated coding system. A new software implementation of the iterative serial version of the LVA is also included in the paper.

Models generated by a gradient descent learning algorithm were compared to evaluate the suitability of KSIM models derived from group participation strategies. KSIM models are commonly used by policymakers to predict system behavior in a qualitative manner based on known or assumed causal relationships between system quantities. The results showed that there are certain limits to the dynamic performance of KSIM models. Thus, they are thus not suited for many real systems.

A common framework to compare and characterize phase aberration correction algorithms based on their stability, capacity to reduce phase errors and noise sensitivity shows that low interelement correlation of the transducer arrays causes defective correction from one row to another. Variations in the size and position of the aperture area that generates the reference signal induce changes in the performance of the algorithms. Algorithms that use large reference frames are less affected by missing elements and noise than those using small reference areas.

Sliding window order recursive least-squares (SW-ORLS) algorithms comprise of two independent features, global array architecture and local cell implementation. Global array architecture deals with the linking of basic modules forming SW-ORLS estimates of different orders while local cell implementation discusses implementation of one-step order update by various forms of time-recursive scalar SWLS estimation. Time and order updates of SW-ORLS are discussed as a function of two hyperbolic Householder Transformation algorithms.

Exact and first-order error analysis helps analyze the numerical properties of the fixed-point (FP) conditions of the Schur and split Schur algorithms that calculate reflection coefficients. The Schur algorithm error-weight vectors match Levinson-like recursions while those of split Schur propagation mechanism satisfy split-Levinson-like recursions. Schur algorithm gives better results for signals of small eigenvalue spread than the split Schur under FP conditions.

This paper considers an adaptive output error identifier with a signum function in its update kernel. It is shown that the classical strict positive real (SPR) condition required for the convergence of traditional adaptive identifiers does not suffice for the convergence of this signed identifier. Instead, what is needed is a stronger operator condition called the strict dominant passive (SDP) condition. We give an analog of the Kalman-Yakubovic-Popov Lemma for the SDP conditions and, using it, give a convergence proof under the assumptions of persistent excitation and SDP.

The augmented linear clustering algorithm and neural networks were found to be superior to ZODIAC, or the non-hierarchical clustering method. This was gleaned from an evaluation of the performance of several cell formation methods for a wide range of data set sizes. The ZODIAC, in turn, was found to be generally superior to array-based methods such as the direct clustering analysis and the improved rank order clustering algorithm.

Two distinct algorithms associated with packet filtering were studied to elucidate the bridges that interconnected Ethernet's local area network (LAN) to Fiber Distributed Data Interface (FDDI) backbones. The algorithm performance was compared with maximum Ethernet traffic and the rise in traffic generated on a local Ethernet. FDDI served as a backbone for lower-speed LAN's such as Token Ring and Ethernet.

A comparative study of the Rosenblatt, Backpropagation and LMS training algorithm, with respect to a single layer perceptron, revealed the three algorithms to exhibit negligible learning performance differences when selecting specific parametric values. The perceptron demonstrated an ability to recognize a specific nonlinear system possessing Gaussian inputs. A memoryless nonlinear device facilitated the output processing of the perceptron which was an adaptive linear combiner.

The objective of this study was to evaluate alternative methods for producing both Normalized Difference Vegetation Index (NDVI) and single-channel composite images of land surfaces from the Advanced Very High Resolution Radiometer (AVHRR). As a goal, it was specified that the composite image should approximate as much as possible a single-date image with a constant, near-nadir geometry. The comparative performance of three single-step [maximum NDVI (MaN), maximum apparent temperature (MaT), maximum difference of channels 2 minus 1 (MaD)] and two two-step [maximum NDVI followed by maximum temperature (MaNMaT) or by minimum scan angle (MaNMiSc)] criteria in creating composite images was evaluated for three land cover types, namely, cropland, coniferous forest, and deciduous forest within a boreal ecosystem. The assessment was carried out using 18 images obtained with various acquisition geometries in mid-summer over a 1000 X 1000 km area in Manitoba, Canada. In addition, MaT performance was compared with that of MaN for all Canada during two compositing periods. It was found that among the five criteria tested, MaT and MaNMiSc were the most effective one- and two-step criteria, respectively. MaN preferentially selected off-nadir pixels from the forescatter region, the degree varying with land cover type; the overall NDVI values were higher than for MaT. MaD showed a very strong preference for high backscatter region pixels, regardless of land cover type. Depending on cover type, the NDVI values resulting from MaD were higher or lower than those from a nadir image. Based on ranking of the five techniques using statistics of the differences between composite and reference images, it was found that MaT and MaNMiSc performed similarly, and better than the remaining criteria. Results of the tests show that although statistically reasonable approximations of the reference image could be produced by one or more methods, none of the criteria could consistently yield composites closely resembling the nadir image on a pixel basis, even for a reasonably long compositing period. Therefore, pixel-specific applications of the composites relying on individual channels will likely have to be based on data corrected for bidirectional effects. The results suggest that such corrections are also required for NDVI and, by analogy, for other AVHRR channel combinations.

The Global Precipitation Climatology Project (GPCP) was established by the World Climate Research Programme to produce global analyses of area- and time-averaged precipitation for use in climate research. To achieve the required spatial coverage, the GPCP uses simple rainfall estimates derived from IR and microwave satellite observations. In this paper, we describe the GPCP and its first Algorithm Intercomparison Project (AIP/1), which compared a variety of rainfall estimates derived from Geostationary Meteorological Satellite visible and IR observations and Special Sensor Microwave/Imager microwave observations with rainfall derived from a combination of radar and raingage data over the Japanese islands and the adjacent ocean regions during the June and mid-July through mid-August periods of 1989. To investigate potential improvements in the use of satellite IR data for the estimation of large-scale rainfall for the GPCP, the relationship between rainfall and the fractional coverage of cold clouds in the AIP/1 dataset is examined. Linear regressions between fractional coverage and rainfall are analyzed for a number of latitude-longitude areas and for a range of averaging times. The results show distinct differences in the character of the relationship for different portions of the area. In general, to the south and east of the mountainous axis of Japan, rainfall and fractional coverage are highly correlated for thresholds colder than 245 K, and correlations can be increased by averaging in space and in time up to the dominant period of the precipitation events. To the north and west of the axis, the correlations between rainfall and fractional coverage, while generally smaller for all scales, are highest for thresholds warmer than 245 K. The proportional coefficients relating rainfall to fractional coverage at cold thresholds, however, differ greatly between the two periods and both differ significantly from those found for the GARP (Global Atmospheric Research Program) Atlantic Tropical Experiment. These results suggest that the simple IR-based estimation technique currently used in the GPCP can be used to estimate rainfall for global tropical and subtropical areas, provided that a method for adjusting the proportional coefficient for varying areas and seasons can be determined.

Previous studies conducted on the linear seismic responses of structures failed to establish any specific criterion for evaluating earthquake effects on different types of structures. This can be attributed to the inaccuracy of the algorithms used in the frequency domain analysis of such structures. Unless these errors are corrected, researchers will continue to shun any development obtained using the equivalent random vibration approach for seismic response analysis.

A linear time algorithm for solving the weighted perfect domination problem in series-parallel graphs is proposed. The weighted perfect domination problem involves finding a minimum-sized perfect dominating set of a graph. The algorithm is optimal, as any algorithm for the weighted perfect domination problem needs to process all vertices of the graph. Special chordal graphs such as k-trees, internal graphs and strongly chordal graphs may also solve the problem.

The performance of several programming-based heuristics and algorithms used in the solution of the resource constrained project scheduling problem was evaluated by means of computational techniques. A Pascal-based problem generator called NGNR was employed to generate a group of test problem with activities ranging from 16 to 36. The heuristics, namely the MINSLIK, SDFIRST, LDFIRST and MIXED, were then used together with the SCICONIC optimizing software to provide solutions to the problems. Results indicate that the heuristics MINSLIK, SDFIRST and LDFIRST outperform the other solutions and are specially suited for project scheduling problems.

A comparison of the accuracy of several orthogonal-grid finite-difference time-domain (FDTD) schemes is made in both two and three dimensions. The relative accuracy is determined from the dispersion error associated with each algorithm and the number of floating point operations required to obtain a desired accuracy level. In general, in both 2-D and 3-D, fourth order algorithms are more efficient than second order schemes in terms of minimizing the number of computations for a given accuracy level. In addition, in 2-D, a new second order approach proposed by Chen, Ney, and Hoefer is much more accurate than the popular Yee scheme for a given amount of computation and can be as efficient as the fourth order algorithms. In 3-D, Yee's algorithm is slightly more efficient than Chen's approach in terms of operations, but much more efficient in terms of memory requirements.

We study the performance of scheduling algorithms for a manufacturing system, called the |no-wait flowshop', which consists of a certain number of machine centers. Each center has one or mo identical parallel machines. Each job is processed by at most one machine in each center. The proble of finding the minimum finish time schedule is considered here in a flowshop consisting of two machi centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. the case of two centers, one with a single machine and the other with [m.sub.1] two heuristics are p with tight performance guarantees of 3 - (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of 8/3 - 2/(3m). It is also shown that this b can be reduced to 2(1 + [Epsilon]). For the flowshop with any number of machines in each center, we heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers. Keywords: No-wait flowshop; Scheduling; Heuristic algorithms; Worst case analysis; Performance bou 1. Introduction We study the performance of algorithms which schedule jobs through a manufacturing system, known as the no-wait flowshop with parallel machines'. A no-wait flowshop consists of a set of k [greater than or equal to] 2 machine centers [[Z.sub.1], [Z.sub.2],..., [Z.sub.k]] with center [Z.sub.j] having [m.sub.j] [greater than or equal to] 1 parallel machines. There are n jobs {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n} to be processed. The func [Pi]([J.sub.i]) = [p.sub,i1], [p.sub.i2],..., [p.sub.ik] will denote the various tasks or equivalently the processing times required by [J.sub.i] in centers [Z.sub.1], [Z.sub.2],..., [Z.sub.k], respectively. By this we mean that job [J.sub.i] will first be processed in [Z.sub.1] for [p.sub.i1] units of time and then in [Z.sub.2] for [p.sub.i2] units of time and so on until it finally completes its processing in [Z.sub.k] for [p.sub.ik] units of time. Task [p.sub.ij] may be processed on any of the [m.sub.j] identical parallel machines {[M.sub.j1], [M.sub.j2],..., [M.sub.jmj]} in [Z.sub.j]. In a no-wait flowshop, each job must be processed continuously from its start in the first machine center, to its completion in the last machine center, without any interruption on machines and without any waiting in between the machine centers. The scheduling problems in no-wait flowshop with parallel machines arise in the chemical processing and petro-chemical production environment, where there are several simple flow lines. The nature of the processor at each level in the flow lines is such that they are effectively identical and hence interchangeable (Salvador, 1973). Another example of a no-wait situation arises in hot metal rolling industries, where the metals have to be processed at continuously high temperature. In recent years, a considerable amount of interest has arisen in no-wait scheduling problems. This interest appears to be motivated as much by applications as by questions of research interest (refer to the survey papers on no-wait scheduling by Hall and Sriskandarajah, 1991, and Goyal and Sriskandarajah, 1988). The no-wait flowshop with parallel machines represents a generalization of the traditional no-wait flowshop and the identical parallel machine shop. The former corresponds to the case [m.sub.j] = 1, 2 [less than or equal to] j [less than or equal to] k, while the latter corresponds to the case k = 1 and [m.sub.1] [greater than or equal to] 2, i.e., only one machine center with more than one parallel machine. These special cases have been studied extensively in the literature (refer the survey papers of Lawler et al., 1982, 1989, and Lenstra and Rinnooy Kan, 1985). We consider the problem of scheduling n jobs through such a flowshop in order to minimize the total finish time or what is also known as the makespan of the schedule. Efficient algorithms for minimizing makespan in a no-wait flowshop are not likely to exist, as even the special cases mentioned above (with the notable exception of k = 2, [m.sub.1] = [m.sub.2] = 1; Gilmore and Gomory, 1964) belong to the class of the NP-complete problems (Garey and Johnson, 1979; Rock, 1982; Sriskandarajah, 1986; Sriskandarajah and Ladet, 1986). While it is possible to design an algorithm using branch-and-bound techniques, as in Salvador (1973), such algorithms are time consuming even for a moderate number of jobs. Thus, instead of looking for exact optimization algorithms, we seek heuristic algorithms which hopefully obtain good solutions in reasonable computing times. In this paper, we evaluate the performance of certain heuristic algorithms for no-wait flowshops with parallel machines. That is, we are interested in knowing how close the solution obtained by a particular algorithm is to the optimal solution. Often, the average case performance evaluation of an algorithm is carried out by empirical studies. This involves running the heuristic on large problem sets with known or estimated optimal solutions and comparing these to the heuristically obtained results. The usefulness of such an evaluation method depends on how realistic the problem instances are. However the difficulty of choosing a set of realistic sample problem instances remains, as there is always a risk of not considering the instances for which the algorithm may perform poorly. The approach which we pursue in this paper is known as the |worst case performance evaluation'. It consists of a rigorous mathematical analysis that determines how close the heuristic solution is to the optimal solution in the worst case. Along this line, some of the work done in the flowshop and the parallel machines environments appears in Coffman et al. (1978), Friesen (1984), Friesen and Langston (1986), Gonzalez and Sahni (1978), Graham. (1966, 1969), Hochbaum and Shmoys (1987), Rock (1982), and Rock and Schmidt (1983); see also the survey papers of Lawler et al. (1982,1989) and Lenstra and Rinnooy Kan (1985). There exist few studies on the development of scheduling algorithms for no-wait flowshops with parallel machines. Salvador (1973) has developed a branch and bound algorithm to find minimum finish time schedules for a no-wait flowshop with parallel machines model that arises in an actual application in the synthetic fiber industry. The worst case analysis of some heuristic algorithms in the context of the no-wait flowshop with parallel machines has been carried out in Sriskandarajah (1986) and Sriskandarajah and Sethi (1989). This paper extends the author's previous work by analyzing the performance of some heuristics in the no-wait flowshop manufacturing environment. A number of studies consider the buffer between the machine centers instead of no-wait restriction. Wittrock (1988) has proposed a heuristic algorithm primarily to minimize the finish time and secondarily to minimize the in-process inventory. Some heuristic algorithms for two machine center flowshops with parallel machines in the worst case performance context have been studied in Buten and Shen (1973), Langston (1987) and Sriskandarajah and Sethi (1989). Arthanari (1974) has studied the flowshop consisting of two machine centers [Z.sub.1] and [Z.sub.2] with [m.sub.1] [greater than or equal to] 2 and [m.sub.2] = 1. He has developed a branch and bound based heuristic procedure for minimizing the makespan. The remainder of the paper is organized as follows. In the next section, we specify the notation of the problem. In Section 3, we analyze the performance of some algorithms for no-wait flowshops particularly for k = 2. More specifically, we consider the case of no-wait flowshops of k = 2 with [m.sub.1] = 1, [m.sub.2] = m [greater than or equal to] 2 in Section 3.1 while the case k = 2 with [m.sub.1] = m [greater than or equal to] 2, [m.sub.2] = 1 is considered in Section 3.2. The algorithms proposed for these cases are analyzed in the worst case performance context. Section 3.3 considers the case of k = 2 with [m.sub.1] = [m.sub.2] = m [greater than or equal to] 2. In Section 3.4, an algorithm for the general case [F.sub.2] ~ no-wait, [m.sub.1] [greater than or equal to] 2, [m.sup.2] [greater than or equal to] 2 ~ [C.sub.max] is provided and its upper bound performance is derived. Section 4 concludes the paper. 2. Notation of the problem For classification of scheduling problems and notation, we follow Lawler et al. (1982). A problem is represented by the form a [Alpha] ~ [Beta] ~ [Gamma], which in our case is [F.sub.k] ~ no-wait, [m.sub.1], [m.sub.2],..., [m.sub.k] ~ [C.sub.max], where [Alpha] = [F.sub.k] represents the flowshop environment with k machine centers, [Beta] = {no-wait, [m.sub.1], [m.sub.2],..., [m.sub.k]} indicates the no-wait restriction and the number of machines at each center. If any [m.sub.i] is not specified, it is assumed to be 1 by default. Similarly, if the no-wait restriction is not specified, it is assumed that the intermediate storage is unlimited. [Gamma] = [C.sub.max] is the optimality criterion, i.e., minimization of finish time (makespan). The finish time [C.sub.max] of the schedule S can be defined as follows. Let [C.sub.i] be the finish time of job [J.sub.i] under schedule S, then [C.sub.max] = [max.sub.i]{Ci}. The special case [F.sub.1] ~ no-wait, m ~ [C.sub.max] can also be represented as [P.sub.m] [parallel] [C.sub.max], where [P.sub.m] represents the parallel machine environment with m machines. 3. Performance of the scheduling algorithms for no-wait flowshops In this section, we investigate the worst case behavior of certain heuristic algorithms for two special cases of the no-wait flowshop. The first and the second subsections of this section deal with [F.sub.2] ~ no-wait, [m.sub.1] = 1, [m.sub.2] = m [greater than or equal to] 2 [veertical bar] [F.sub.2] ~ no-wait, [m.sub.1] = m [greater than or equal to] 2, [m.sub.2]= ~ [C.sub.max] respective The third subsection deals with [F.sub.2] no-wait, [m.sub.1] = [m.sub.2] = m [greater than or equal to] 2 [veertcal bar] [C.sub.max] while the last sub considers the flowshop with any number of machines in each center ([F.sub.2] ~ no-wait, [m.sub.1] [greater than or equal to] 2, [m.sub.2] [greater than 2 ~ [C.sub.max]). In this paper, we assume that tasks with zero processing time spend [Epsilon] amount of time in the machines, where [Epsilon] is a small positive number (i.e., [approximate] = 0). 3. 1. Algorithms for the case [F.sub.2] ~ no-wait, [m.sub.1] = 1, [m.sub.2] = m [greater than or equal to] 2 [veertical bar] [C.sub.max]: Worst case performance Let us first explore the worst case performance of the list scheduling algorithm, which assigns the next job in the list to the first available machine. 3. 1.1. List scheduling algorithm [H.sub.1] In this algorithm, a list (or permutation) of the job indices 1, 2,..., n is provided. Jobs are scheduled in the order in which they appear on the list. This heuristic is studied by Graham (1966) for the parallel machine shop with m [greater than or equal to] 2 machines, i.e., [P.sub.m] [parallel] [C.sub.max]. He showed that if f and f * are the finish times, respectively, of a list schedule and an optimal schedule for any given job set, then f/f*] [less than or equal to] r with r = 2 - (1/m). The value r is said to be the worst-case performance bound for the list scheduling algorithm. In Theorem 1, we establish the worst-case bound for the list scheduling algorithm for the case [F.sub.2] ~ no-wait, [m.sub.1] = 1, [m.sub.2] = m [greater than or equal to] 2 ~ [C.sub.max]. In order to prove the result in this section, we define schedule [S.sub.j] as the order of the job indices obtained by the list scheduling algorithm. There is no loss of generality in assuming that the order of the job indices [S.sub.J] = [1, 2,..., n]. Figure 1 for [S.sub.j], regarded as [S.sub.J], can be divided into three types of sections, namely x, y and w (or lengths x, y and w respectively). Section [Chi]. This is the portion of [S.sub.j] in which the machine in center [Z.sub.1] is busy throughout. The length of the sections x are measured by [[Chi].sub.i], i = 1,..., l(x). There are l(x) such sections: [Chi] = [Mathematical Expression Omitted] Section y. In Section y, all center 2 machines are busy throughout while the machine in center 1 is idle throughout. The length of the sections y are measured by [y.sub.i], i = l(y). There are l(y) such sections: y = [Mathematical Expression Omitted] Section w. It is the last portion of [S.sub.j], where the machine in [Z.sub.1] is idle throughout while at least one machine in [Z.sub.2] is idle throughout. The length of the section w is measured by w. Property. In [S.sub.J], l(x) [greater than or equal to] 0, 1(y) [greater than or equal to] 0 and w One can easily conceive these properties for [S.sub.J]. In general, the [S.sub.J] takes the following form: [[Chi].sub.1] [y.sub.1] [[Chi].sub.2] [y.sub.2] ... [[Chi].sub.l [y.sub.l] where every section y fol section x. For example, the following forms are possible for [S.sub.J We refer to these forms as [S.sub.J1], [S.sub.J2], [S.sub.J3]. (i) [Mathematical Expression Omitted] (ii) [Mathematical Expression Omitted] (iii) [Mathematical Expression Omitted] [y.sub.l] = 0. In Figure 1, we have given an example for [S.sub.J2] with l = 2, [y.sub.2] = 0, i.e., the form of [S.sub.J2] is: [[Chi].sub.1] [y.sub.1]w. Note that the length [[Chi].sub.1], can be equal to zero, if [p.sub.i1] = 0, for 1 [less than or equal to] i [less than or equal to] 4. Theorem 1. For the case [F.sub.2] ~ no-wait, [m.sub.1 = 1, [m.sub.2] = m [greater than or equal to] 2 ~ [C.sub.max], let [p.sub.i1], [p.sub.2], 1 [less than or equal to] processing times of job [J.sub.i] on machine centers [Z.sub.1] and [Z.sub.2], respectively. Let f be the finish time of the job set {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n) obtained by the list sch algorithm and let f* be the finish time of an optimal schedule of the job set. Then f/f* [less than or equal to] 3 - 1/m, and this bound is the best possible. Proof. From Figure 1, we have (1) f = x + y + w. We derive worst case bounds for two separate cases: Case 1: (2) y + w/m [greater than or equal to] w, Case 2: (3) y + w/m < w. Case 1. It is evident that (4) f* [greater than or equal to] y + w/m. Using (1) and (4), we obtain [Mathematical Expression Omitted] i.e., (5) [Mathematical Expression Omitted] Using (2) and (5), we obtained (6) f/f* [less than or equal to] 3 - 1/m. Case 2. Since w cannot be more than max{[p.sub.i2]}, it is evident that (7) f* [greater than or equal to] max{[p.sub.i2]} [greater than or equal to] w and (8) f* [greater than or equal to] [Chi]. Relation (3) implies that (9) y/w < 1 - 1/m. Using (1) and (7), we have (11) f/f* [less than or equal to] [Chi]/f* + y/w + w/f*. Using (10), (7), (8) and (9), we have (10) f/f* [less than or equal to] 3 - 1/m. A worst case example which is similar to the one obtained for the list scheduling algorithm for [F.sub.2] ~ [m.sub.1] = 1, [m.sub.2] = m [greater than or equal to] 2 ~ [C.sub.max] can be construct (refer to Sriskandarajah and Sethi, 1989). This completes the proof. It can be noted from the worst example that the poorer performance of the list scheduling algorithm may be due to the fact that the jobs with larger first tasks are scheduled at the beginning of the schedule and the jobs with larger second tasks are scheduled at the end of the schedule. In order to improve the above bound, we propose the following algorithm which schedules jobs in the nonincreasing order of [p.sub.2.] 3.1.2. Algorithm [H.sub.2] In this algorithm, jobs are scheduled in the nonincreasing order of [p.sub.i2]. The following theorem provides the worst case bound for [H.sub.2]. Theorem 2. For the case [F.sub.2] ~ no-wait, [m.sub.1] = [m.sub.2] = m [greater than or equal to] 2 ~ [C.sub.max], let [p.sub.i1], [p.sub.i2] 1 [less than or equal to] processing times of job [J.sub.i] on machine centers [Z.sub.1] and [Z.sub.2], respectively. Let f be the finish time of the job set {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n} obtained by algorithm [H and let f* be the finish time of an optimal schedule of the job set. Then f/f* [less than or equal to] 2, and this bound is the best possible. Proof. Let, in Figure 1, [S.sub.J] be a schedule of [H.sub.2] Then (12) f = x + y + w, where [S.sub.j] = [1, 2,..., n]. It is evident that (13) f* [greater than or equal to] y. Now we should prove that (14) f* [greater than or equal to] x + w. Note that the schedule [S.sub.J] can take three forms namely [S.sub.j1], [S.sub.J2], as defined in Section 3.1.1. In [S.sub.3], (15) w = 0. Thus, relation (14) is true for [S.sub.J3]. Note that in [S.sub.J3], m jobs finish at time In [S.sub.J1] (or [S.sub.J2]), since w > 0, at most m - 1 jobs can finish at time f. Let q be the smallest index of a job that finishes at f. If w [less than or equal to] [min.sub.i]([p.sub.i2]}, then relation (14) is true. Let w > [min.sub.i]{[p.sub.i2]}; then it is true that 1 [less than or equal to] q < n. Now we remove jobs [J.sub.q+1], [J.sub.q+2], ... and [J.sub.n] from the schedule [Sub.J1] (or [S.sub.J2]). The remaining jobs {[J.sub.1], [J.sub.2],..., [J.sub.q]}, which form a schedule of [S.sub.J2] type, have the same finish time f. Now it is obvious that (16) [Mathematical Expression Omitted] where [Mathematical Expression Omitted] is the optimal finish time of the jobs {[J.sub.1], [J.sub.2],..., [J.sub.q]} It can be easily seen that (17) [Mathematical Expression Omitted] and (18) [Mathematical Expression Omitted] Using (16)-(18), we obtain (19) [Mathematical Expression Omitted] Hence we have proved that relation (14) is true for [S.sub.J1] (or [S.sub.J2]). Using (12)-(14), we obtain (20) f/F* [less than or equal to] 2. A worst case example is shown in Figure 2a with the following job set: J = {[J.sub.a], [J.sub.b] (i) ~ 1 [less than or equal to] i [less than or equal to] [m.sub.1] [J.sub with processing times; [Pi][J.sub.a] = [[Epsilon], [Epsilon], [Pi][[J.sub.b] (i)] = [[Epsilon], L ] [less than or equal to] i [less than or equal to] [m.sub.1] [Pi][J.sub.c] = [L - (m - 1)[Epsilon], [Epsilon], where >> m[Epsilon]. The corresponding optimal schedule of J is shown in Figure 2b. From Figures 2a and 2b, we have (21) f/f* = 2L - (m - 3)[Epsilon]/L + m[Epsilon], or (22) [Mathematical Expression Omitted] Thus (23) [Mathematical Expression Omitted] This completes the proof. It is of interest to note that the problem [F.sub.2] ~ no-wait, [m.sub.1] = [m.sub.2] = 1 ~ [C.sub.max] can be solved by a polynomial time algorithm due to Gilmore and Gomory (1964). The worst case performance of this algorithm is given in Theorem 3 for the case [F.sub.2] ~ no-wait, [m.sub.1] = ~ [m.sub.2] = m = 2 ~ [C.sub.max]. It has to be noted that the worst case performance of the algorithm due to Johnson (1954) for the case [F.sub.2] ~ [m.sub.1] = 1, [m.sub.2] = m = 2 ~ [C.sub.max] is analyzed and obtained in Sriskandarajah and Sethi (1989). Theorem 3. For the case [F.sub.2] ~ no-wait, [m.sub.1] = 1 [m.sub.2] = m = 2 ~ [C.sub.max], let be the finish time of the job set J = {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n) obtained by the Gilmore and Gomory algorithm and let f * be the finish time of an optimal schedule of the job set. Then f/f* [less than or equal to] 2, and the bound is the best possible. Proof. The proof follows from the technique used in Sriskandarajah and Sethi (1989). 3.2. Algorithms for the case [F.sub.2] ~ no-wait, [m.sub.1] = m [greater than or equal to] 2, [m.sub.2] = 1 ~ [C.sub.max: Worst case performance Any schedule for [F.sub.2] ~ no-wait, m.sub.1] = 1 [m.sub. 2] = m [greater than or equal to] 2 ~ [C.sub.max] can be viewed as a schedule to the problem [F.sub.2] ~ no-wait, [m.sub.1] = m [greater than or equal to] 2, [m.sub.2] = 1 ~ [C.sub.max] by interchanging the role of machine centers [Z.sub.1] and [Z.sub.2] and considering the schedule in reverse direction. It is easy to see that the following list scheduling algorithm has the same worst case bound of 3 - (1/m). 3.2.1. List scheduling algorithm [Mathematical Expression Omitted] In this algorithm, we interchange the values of [p.sub.i1] and [p.sub.i2] for each i = 1, 2,..., n. Then jobs are scheduled for [F.sub.2] ~ no-wait, [m.sub.1] = 1 [m.sub.2] = [m.sub.2] [greater than or equal to] 2 ~ [C.sub.max] in the order in which they appear on the list. If we interchange the role of [Z.sub.1] and [Z.sub.2] and consider the schedule in reverse direction, this will form a valid schedule for [F.sub.2] ~ no-wait, [m.sub.1] = m [greater than or equal to] 2, [m.sub.2] = 1 ~ [C.sub.max]. Corollary 4. The worst case bound of algorithm [Mathematical Expression Omitted] is 3 - (1/m). Proof. Follows from Theorem 1. 3.2.2. Algorithm [Mathematical Expression Omitted] In this algorithm, we interchange the values of [p.sub.i1] and [p.sub.i2] for each i = 1, 2,..., n. Then jobs are scheduled for [F.sub.2] ~ no-wait, [m.sub.1]= [m.sub.2] = m [greater than or equal to] 2 ~ [C.sub.max] in nonincreasing order of [p.sub.i2]. If we interchange the role of Z, and [Z.sub.2] and consider the schedule in reverse direction, this will form a valid schedule for [F.sub.2] ~ no-wait, [m.sub.1] = m [greater than or equal to] 2, [m.sub.2] 1 ~ [C.sub.max]. Corollary 5. The worst case bound of algorithm [Mathematical Expression Omitted] is 2. Proof. Follows from Theorem 2. In a similar manner, a heuristic based on Gilmore and Gomory's algorithm can be devised for the special case [F.sub.2] ~ no-wait, [m.sub.1] = 2, [m.sub.2] = 1 ~ [C.sub.max] with the worst case bound of 2. The detailed description of the algorithm is as follows: * interchange the values of [p.sub.i1] and [p.sub.i2] for each i = 1, 2,..., n. * using Gilmore and Gomory's algorithm, find a job order (sequence) for [F.sub.2] ~ no-wait, [m.sub.1] = 1, [m.sub.2] = 1 ~ [C.sub.max]. * schedule jobs in same order for [F.sub.2] ~ no-wait, [m.sub.1] = 1, [m.sub.2] = 2 ~ [C.sub.max]. * In the above schedule, by interchanging the role of [Z.sub.1] and [Z.sub.2] and considering the schedule in reverse direction, a valid schedule for [F.sub.2] ~ no-wait, [m.sub.1] = 2, [m.sub.2] = 1 ~ [C.sub.max] is obtained. 3.3. Algorithms for the case [F.sub.2] ~ no-wait, [m.sub.1] [m.sub.2] = m [greater than or equal to] 2 ~ [C.sub.max]: Worst case performance In this section, an algorithm is proposed by combining the list scheduling algorithm and the algorithm given by Gilmore and Gomory (1964) for the case of [F.sub.2] ~ no-wait, [m.sub.1] = [m.sub.2] = m [greater than or equal to] 2 ~ [C.sub.max]. Then the worst-case performance bound is derived. Now we sketch our algorithms: Let [J.sub.i], 1 [less than or equal to] i [less than or equal to] n, be n jobs requiring processing times [Pi][J.sub.i] = [[p.sub.i1], [p.sub.i2] and let [T.sub.i] = [P.sub.i1] + [p.sub.i2], 1 [less than or The heuristic algorithms analyzed in this subsection were first proposed in Sriskandarajah and Sethi (1989). 3.3.1. Algorithm [H.sub.a] Step 1. Partition the problem into m flowshop problems each having two machine centers with each center having exactly one machine: {[M.sub.11] [M.sub.21]}, {[M.sub.12]} [M.sub.22]},..., {[M.sub.1m] [M.sub.2m]}, where [M.sub.ij] is the i-th machine center in the i-th flowshop. See Figure 3. Step 2. A virtual parallel machine shop with m machines is formed by considering each flow shop {[M.sub.1j], [M.sub.2j]}, as a single machine [M.sub.j]. Using list scheduling algorithm, schedule n jobs (of processing time requirements [T.sub.1], [T.sub.2],..., [T.sub.n]) in the parallel machine shop. In this way, jobs are allocated to m flowshops. Step 3. Since each flowshop consists of two machines, we can solve each of the m flowshops optimally using the algorithm proposed by Gilmore and Gomory (1964). (This step may be replaced by a list scheduling rule.) Note that in Step 2, we try to solve the makespan minimization problem in the parallel machine shop ([P.sub.m] [parallel] [C.sub.max]). Since this problem belongs to the class of NP-complete problems (Garey and Johnson, 1979), the list scheduling heuristic is chosen to schedule the jobs. The following result was obtained in Sriskandarajah and Sethi (1989). Theorem 6. Let f be the finish time of the job set {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n} obtained by algorithm [H.sub.a] be the finish time of an optimal schedule of the job set. Then f/f* [less than or equal to] 3 - 1/m, and the bound is the best possible. Note that the bound obtained in Theorem 6 is valid even if Step 3 is replaced by a list scheduling rule. Corollary 7. For the case [F.sub.k] ~ no-wait, [m.sub.1] m,..., m [greater than or equal to] 2 ~ [C.sub.max], let f be the finish time of the job set J = {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n} obtained by algorith and f* be the finish time of an optimal schedule of J. Then f/f* [less than or equal to] k + 1 - 1/m. Proof. The proof is easy and similar to that of Theorem 6. Note that algorithm [H.sub.a] uses a list schedule in Step 3 for k > 2. 3.3.2. Algorithm [H.sub.2] Step 1. Same as in [H.sub.a]. Step 2. Same as in [H.sub.a], but instead of the list scheduling algorithm, the LPT (longest processing time first) rule is used to allocate n jobs to the m parallel shops. Step 3. Same as in [H.sub.a]. Since LPT is a better algorithm than the list scheduling algorithm for [P.sub.m] [parallel] [C.sub.max] (Graham, 1966, 1969), we expect algorithm [H.sub.b] to perform better than [H.sub.a] in the worst case performance context. A performance bound for [H.sub.b] is established in Theorem 9. We require the following Lemma to prove Theorem 9. Lemma 8. Let f be the optimal finish time of the job set J = {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n) with [Pi] [J.sub.i] the no-wait flowshop and let [Mathematical Expression Omitted] be the optimal finish time of J with [Pi] [J.sub.i] = [[T.sub.i] in the m parallel machine shop, where [T.sub.i] = [p.sub.i1] + [p.sub.i2]. Then [Mathematical Expression Omitted]. Proof. Given a schedule S (finish time f) for J in the no-wait flowshop, one can construct a schedule [S.sub.o] (finish time [f.sub.0]) for J in the parallel machine shop using the following procedure. ~t will be shown later that the resulting schedule So requires the finish time to be bounded by 2f, i.e., [f.sub.o] [less than or equal to] 2f. The procedure first forms machine groups. Each group which consists of two machines is formed by arbitrarily taking one machine from each center. Then a schedule is constructed by noting that whenever machines from different groups process the same job, the schedule can be rearranged (possibly with preemptions) to schedule all of the jobs in the same group. Given this rearranged schedule, we can easily construct a parallel machine schedule with length 2f. For more detail, the reader may refer to the following procedure and the illustration of the procedure on an example problem. Procedure: Step 1. Group the machines such that each group consists of two machines. Note that each group is formed by taking one machine from each machine center. Group [G.sub.i] = {[M.sub.1i], [M.sub.2i]}, 1 [less than or equal to] i [less than o m. (See the example given in Figure 4a for m = 3.) Step 2 Identify the type of jobs: there are three types of jobs. Type-1 job: If the machines that process a job [J.sub.i] belong to the same group, then the job [J.sub.i] is said to be a type-1 job. (In the example given in Figure 4a, the jobs [J.sub.1], [J.sub.3], [J.sub.5], [J.sub.6], [J.sub.8], [J.sub.11], [J.sub.12], [ [J.sub.14] and [J.sub.15] are type-1 jobs. Note that the first and the second tasks of the job [J.sub.i] are denoted as [J.sub.i](1), [J.sub.i](2) respectively). Type-2 job: If the machines that process a job [J.sub.i] belong to different groups, then the job [J.sub.i] is said to be a type-2 job. (In the example given in Figure 4a, the jobs [J.sub.2], [J.sub.4], [J.sub.7] and [J.sub.10] are type-2 jobs). Type-3 job: The idle time slots left out in the schedule S are represented by dummy jobs which are identified as type-3 jobs. (In the example given in Figure 4a, the jobs [J.sub.d1] and [J.sub.d2] are type-3 jobs). Step 3. Move the tasks in a certain way that the type-2 jobs are converted to type-1 jobs. The moving procedure is as follows: Step 3.1. Find a type-2 job [J.sub.i]. Find the group (let it be [G.sub.j]) in which the first task [J.sub.i](1) is processed (or scheduled). Find the group (let it be [G.sub.k]) in which the second task [J.sub.i](2) is processed (or scheduled). Let f([J.sub.i](1)) be the finish time of [J.sub.i](1) in G,. Step 3.2. In [G.sub.j], form a task set ([t.sub.G],) that has to be moved to [G.sub.k]. Step 3.2(a). Set G = [G.sub.j], L = f ([J.sub.i](1)) and [t.sub.G] = 0. Step 3.2(b). If there is a type-1 job [J.sub.u] whose first task starts at L in G, then L [left arrow] L + p[[J.sub.u](1)] + p[[J.sub.u] (2)], [t.sub.g] [left arrow] [t.sub.g] [union] {[J.sub.u](1), [J.sub.u] (2)), where p[[J.sub.](q)] is the processing time of the q-th task of job [J.sub.u] (q = 1 or 2). Otherwise there exists a type-2 or type-3 job ([J.sub.v]) which starts at L in G. If [J.sub.v] is type-2 and the task [J.sub.v](q) is in G (where q may be equal to 1 or 2), then L [left arrow] L + p[[J.sub.v](q)], [t.sub.G] [left arrow] [t.sub.G] [union] {[J.sub.v](q)}. If [J.sub.v] is type-3 (denote this job as [Jd.sub.w]), then L [left arrow] L + p[[Jd.sub.w], [t.sub.G] [left arrow] [t.sub.G] [union] {[Jd.sub.w]}. Step 3.2(c). Repeat Step 3.2(b) until L Step 3.2(d). When L = f, set [t.sub.Gj] = [t.sub.G]. Step 3.3. In [G.sub.k], form a task set [t.sub.Gk]) that has to be moved to [G.sub.j]. Step 3.3(a). Set G =[G.sub.k], L = f([J.sub.i](1)) + p [J.sub.i](2)] and [t.sub.G] = {[J.sub.i](2)}. Step 3.3(b). Same as Step 3.2(b) above. Step 3.3(c). Repeat Step 3.3(b) until L Step 3.3(d). When L = f, set [t.sub.Gk], = [t.sub.G] Step 3.4. Remove the tasks ([t.sub.Gj]) from [G.sub.j]. This leaves a series of empty slots in [G.sub.j]. Schedule these slots with the tasks [t.sub.Gk] in the same order as they were scheduled in [G.sub.k]. Step 3.5. Remove the tasks ([t.sub.Gk]) from [G.sub.k. This leaves a series of empty slots in [G.sub.k]. Schedule these slots with the tasks [t.sub.G] in the same order as they were scheduled in [G.sub.j]. Note that the following operations are possible when scheduling the slots in Steps 3.4 and 3.5: * Preempt the tasks if necessary. * The first task of a job can be scheduled in the second center machines. The second task of a job can be scheduled in the first center machines. Step 3.6. Repeat Steps 3.1 to 3.5 until all the type-2 jobs are converted to type-1 jobs. This procedure is illustrated on an example (see Figure 4a-4f). Note that in Step 3.2(b) (also in Step 3.3(b)), we look for a type-1 job whose first task starts at L in group G. If there is no such job, then there exists always a type-2 job or type-3 job which starts at L in G. One can easily see that this property is valid for the flowshop with no-wait restriction. In Steps 3.4 and 3.5, we move two task sets between two groups. It has to be noted that the sets have equal amount of total task processing time as the tasks of each set are processed continuously form the finish time of the first task of a type-2 job until the finish time f of the schedule S. Therefore, moving the two sets between two groups neither changes the finish time f nor affects the schedule of other jobs. In each such move, at least one type-2 job is converted to a type-1 job and no new type-2 job is created. Therefore the procedure terminates in a finite number of iterations which is bounded by the total number of type-2 jobs. Thus the procedure guarantees the conversion of all the type-2 jobs to type-1 jobs. At the end of the procedure, we have new job assignment to the groups, where all the jobs are either type-1 or type-3 jobs. Note that the jobs in each group are processed preemptively on two machines with the schedule length not larger than f. A parallel machine schedule can be constructed by transferring the jobs in each group to a single machine in the parallel machine shop. Then the jobs in each group are scheduled so that tasks 1 and 2 of each job are processed nonpreemptively on the same machine. The resulting parallel machine schedule [S.sub.o] has the finish time [f.sub.o] which is clearly less than or equal to 2f. Now let S be the optimal schedule of finish time f*. Using the above procedure, a parallel machine schedule [S.sub.o] of finish time [f.sub.o] can be constructed with [f.sub.o] [less than or equal to] 2f*. Since the optimal finish time [Mathematical Expression Omitted], we have [Mathematical Expression Omitted]. This completes the proof. Illustration of the procedure. The job set J {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] 15) is considered to illustrate the that converts type-2 jobs to type-1 jobs. The processing time of the jobs are given as follows: [Pi][[J.sub.1] = [0, 3], [Pi][[J.sub.2]] = [2, 3], [Pi][[J.sub.3] = [3, 9], [Pi][J.sub.4] + [4, 1], [Pi][J.sub.5] = [5, 0], [Pi][J.sub.6] = [0, 2], [Pi][J.sub.7] = [3, 2], [Pi][J.sub.8] = [2, 7] [Pi][J.sub.9] = [1, 3] [Pi][J.sub.10] = [4, 3], [Pi][J.sub.11], = [2, 2], [Pi][J.sub.12] = [1, 0], [Pi][J.sub.3] = [0, 4], [Pi][J.sub.14] = [4, 2] and [Pi][J.sub.15] = [9, 1]. Note that a schedule S is given in Figure 4a for J in the no-wait flowshop with m = 3. The finish time of schedule S is f, where f = 14. The job [J.sub.7] which is a type-2 job belongs to the groups [G.sub.1] and [G.sub.2]. Let us convert the job [J.sub.7] to type-1 job. The task set that has to be moved to [G.sub.1] from [G.sub.2] is [t.sub.G2], where [t.sub.G2] ={[J.sub.72], [J.sub.4](2), [J.sub.4](1), [J.sub.5](1), [J.sub.5(2)}. The total processing time of tasks in each set [t.sub.G1] [t.sub.G2]) is equal to 11. Figure 4b provides the Gantt chart representation of the schedule S, after moving the task sets between the groups. Note that the task [J.sub.5](1) is preempted and is represented by two new tasks, namely [Mathematical Expression Omitted]. Also note that the first task [J.sub.8](1) is scheduled in the second center machine [M.sub.21] and the second task [J.sub.8](2) is scheduled in the first center machine [M.sub.11] (See Figure 4b). But the tasks [t.sub.G1] are scheduled in [G.sub.2] in the same order as they were scheduled in [G.sub.1]. Similarly the tasks [t.sub.G], are scheduled in [G.sub.1], in the same order as they were scheduled in [G.sub.2]. Now we convert job [J.sub.2] to type-1 job. The job [J.sub.2] belongs to the groups [G.sub.1] and [G.sub.2] The task set that has to be moved to [G.sub.1] from [G.sub.2] is [t.sub.G2], where [t.sub.G2] = {[J.sub.2](2), [J.sub.9](1), [J.sub.10](1), [J.sub.11](1), [J.sub.11](2)}. Similarly, the task set that has to be moved to [G.sub.2] from [G.sub.1] is [t.sub.G1] where [t.sub.G1] = {[J.sub.3](1), [J.sub.3](2)}. The total processing time of tasks in each set ([t.sub.G1], [t.sub.G2]) is equal to 12. Figure 4c provides the Gantt chart representation of the schedule S, after moving the task sets between the groups. Note that we need to preempt the task J3(2) into two tasks, namely [Mathematical Expression Omitted]. Convert the following jobs (one after the other): [J.sub.4], [J.sub.9] and [J.sub.10] (see Figures 4d-4f). Now we have converted all the type-2 jobs to type-1. See Figure 4f for the final schedule S. Now we are ready to prove Theorem 9. Theorem 9. Let f be the finish time of the job set {[J.sub.i] ~ 1 [less than or equal to] i [less than or equal to] n) obtained by algorithm [H.sub.b] be the finish time of an optimal schedule of the job set. Then f/f* [less than or equal to] 8/3 - 2/3m Proof. Consider the allocation of jobs to m parallel machines in Step 2. Let [f.sub.o] be the finish time of the jobs in the parallel machine shop and [Mathematical Expression Omitted] be the optimal finish time of jobs. Since Step 2 uses the LPT rule, from Graham (1969), we have (24) [Mathematical Expression Omitted] It is clear that (25) f [less than or equal to] [f.sub.o]. From Lemma 8, we have (26) [Mathematical Expression Omitted] Using the results in (25) and (26) in (24), we obtain (27) f/f* [less than or equal to] 8/3 - 2/3m. (27) This completes the proof. The exact worst case bound [r.sub.b] of algorithm [H.sub.b] is not known, since no job set with f/f* = 8/3 - 2/3m has been found. However, an example of a job set with f/f* = 7/3 - 2/3m has been found in Sriskandarajah and Sethi (1989). Thus, [r.sub.b] must lie in the following interval: 7/3 - 2/3m [less than or equal to] [r.sub.b] [less than or equal to] 8/3 - 2/3m. The performance bound of [H.sub.b] may be improved by replacing LPT with a better algorithm in Step 2 (call the new algorithm [H.sub.c]). In what follows, we will determine the interval in which the worst case bound [r.sub.c] of [H.sub.c] must lie. It should be noted that better heuristic algorithms such as Multifit (Coffman et al., 1978; Friesen, 1984), improved Multifit (Friesen and Langston, 1986), and the [Epsilon]-approximation algorithm (Hochbaum and Shmoys, 1987) are available for Step 2 with performance guarantees ([r.sub.o]) of 6/5, 72/61, and 1 + [Epsilon], respectively. Sriskandarajah and Sethi (1989) have shown that [r.sub.c] [greater than or equal to] 2, even if an optimal algorithm is used in Step 2 of [H.sub.c]. It can be deduced from Theorem 9 that [r.sub.c] [less than or equal to] 2r.. Thus, [r.sub.c] must lie in the following interval: 2 [less than or equal to] [r.sub.c] [less than or equal to] 2 [r.sub.o], where [ performance guarantee of the algorithm used in Step 2. Note that regardless of the algorithms used in Steps 2 and 3, the worst case bound of the overall algorithm [H.sub.c] will be greater than or equal to 2. Therefore, a substantially different design for the heuristic than the one presented here is required if one wishes to reduce the bound to less than 2. 3.4. An algorithm for the case [F.sub.2] ~ no-wait, [m.sub.1] [greater than or equal to] 2, [m.sub.2] [greater than or equal to] 2 ~ [C.sub.max] Upper bound performance In this section, an algorithm is proposed for the general case of [F.sub.2] ~ no-wait, [m.sub.1] [greater than or equal to] 2, [m.sub.2] [greater 2 ~ [C.sub.max]. Then the upper bound performance is derived. Without any loss of generality, we may assume [m.sub.1] [less than or equal to] [m.sub.2] since any schedule for [F.sub.2] ~ no-wait, [m.sub.1] [less than or equal to] [m.sub.2] ~ [C.sub.max] can also form a valid schedule for [F.sub.2] ~ no-wait, m ~ [greater than or equal to] [m.sub.2] ~ [C.sub.max] if we interchange the role of [Z.sub.1] and [Z.sub.2] in the former problem and consider the schedule in the reverse direction. Now we sketch our algorithm: Let [J.sub.i], 1 [less than or equal to] i [less than or equal to] n, be n jobs requiring processing times [Pi][J.sub.i] [p.sub.i1], [p.sub.i2], [T.sub.i] = [p.sub.i1] + [p.sub.i2], 1 [less than or equal to] = [m.sub.2]/[m.sub.1], where k is the smallest integer greater than or equal to [m.sub.2]/[m.sub.1]. 3.4.1. Algorithm [H.sub.g] Step 1. Partition the problem into [m.sub.1] flowshop with parallel machine problems, each having two machine centers with the first center having exactly one machine and at the most k parallel machines in the second center: {[M.sub.1],j [M.sub.2],(j-1)k+1, [M.sub.2],(j - 1)k+2 ... , [M.sub.2],(j - 1)k+k,}, j = 1, 2,..., [m.sub.1], where [M.sub.2],(j - 1)k + r is the r-th parallel machine in the j-th flowshop. See Figure 5. Step 2. A virtual parallel machine shop with [m.sub.1] machines is formed by considering each flowshop defined above as a single machine [M.sub.j]. Using the algorithm due to Hochbaum and Shmoys (1987), schedule n jobs (of processing time requirement [T.sub.2], [T.sub.2],..., [T.sub.n]) in the parallel machine shop. In this way, jobs are allocated to [m.sub.1] flowshops. Step 3. Solve each of the [m.sub.1] flowshops using the algorithm [H.sub.2] proposed in Section 3.1.2. if the flowshop has parallel machines; otherwise solve the flowshop using the algorithm proposed by Gilmore and Gomory (1964). (This step may be replaced by a list scheduling rule.) The following result can be obtained for algorithm [H.sub.g]. Theorem 10. Let f be the finish time of the job set {[J.sub.i] 1 [less than or equal to] i [less than or equal to] n} obtained by algorithm [H.sub.g] an be the finish time of an optimal schedule of the job set. Then f/f* [less than or equal to] (1 + [[m.sub.2]/[m.sub.1]]) (1 + [Epsilon]). Proof. Consider the allocation of jobs to [m.sub.1] parallel machines in Step 2. Let [f.sub.o] be the finish time of the jobs in the parallel machine shop and [Mathematical Expression Omitted] be the optimal finish time of jobs. Since Step 2 uses the algorithm due to Hochbaum and Shmoys (1987), we have (28) [Mathematical Expression Omitted] It is clear that (29) f [less than or equal to] [f.sub.o]. Using the procedure and techniques of Lemma 8, we can obtain the following relation which is similar to the one derived in the same Lemma: (30) [Mathematical Expression Omitted] Using the results in (29) and (30) in (28), we obtain (31) [Mathematical Expression Omitted] This completes the proof. The exact worst case bound of algorithm [H.sub.g] is not known, since no job set with f/f* = (1 + [[m.sub.2]/[m.sub.1]]) (1 + [Epsilon] has been found. Note that the bound obtained in Theorem 10 is valid even if Step 3 is replaced by a list scheduling rule. 4. Concluding remarks We have designed heuristic algorithms and established their performance bounds for the problem of finding minimum finish time schedules in no-wait flowshops with 2 machine centers. These bounds are quite useful, particularly because they enable us to guarantee that a proposed algorithm will never exceed the optimal solution by more than a known percentage. In the worst case performance context, algorithm H2 performs better than the list scheduling algorithm [H.sub.1] for [F.sub.2] ~ no-wait, [m.sub.1] = 1, [m.sub.2] = m [greater than or equal to] 2 ~ [C.su while algorithm [H.sub.b] performs better than algorithm [H.sub.a] for [F.sub.2] ~ no-wait, [m.sub.1] = 1, [m.sub.2] = m [greater than or equal to] 2 ~ [C.su One possible extension of this paper could be to study the worst case performance of the algorithms [H.sub.1] and [H.sub.2] for the flowshop with any number of machines in each center ([F.sub.2] ~ no-wait, [m.sub.1] [greater than or equal to] 2, [m.sub.2] [greater than or equal to] 2 ~ [C.sub.max]) as wel for algorithms [H.sub.b, [H.sub.c] and [H.sub.g]. The heuristic algorithms often behave significantly better in practice than their worst case guarantees. Therefore, it might be interesting to study average case performance under appropriate assumptions on the type of jobs that need to be processed in the system. Acknowledgement The author wishes to thank two anonymous referees, whose detailed comments on an earlier draft improved the paper. This research was supported by NSERC Grant OGP0104900 and FCAR Grant 89-EQ-4144. References Arthanari, T.S. (1974), 'On some problems of sequencing and grouping', Ph.D. Thesis, Indian Statistical Institute, Calcutta, India. Buten, R.E., and Shen, V.Y. (1973), 'A scheduling model for computer systems with two classes of processors', in: Proceedings Sagamore Computer Conference on Parallel Processing, 130-138. Coffman, Jr., E.G., Garey, M.R., and Johnson, D.S. (1978), 'An application of bin-packing to multiprocessor scheduling', SIAM Journal on Computing 7, 1-17. Friesen, D.K. (1984), 'Tighter bounds for multifit processor scheduling algorithm', SIAM Journal on Computing 13, 170-181. Friesen, D.K., and Langston, M.A. (1986), 'Evaluation of a multifit-based scheduling algorithm', Journal of Algorithms 7, 35-59. Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, CA. Gilmore, P., and Gomory, R. (1964), 'Sequencing a one-state variable machine: A solvable case of the Travelling Salesman Problem', Operations Research 12, 665-679. Gonzalez, T., and Sahni, S. (1978), 'Flowshop and jobshop schedules: Complexity and approximation', Operations Research 26, 36-52. Goyal, S.K., and Sriskandarajah, C. (1988), 'No-wait shop scheduling: Computational complexity and approximate algorithms', Opsearch 25, 220-244. Graham, R.L. (1966), 'Bounds for certain multiprocessing anomalies', Bell System Technical Journal 45, 1563-1581. Graham, R.L. (1969), 'Bounds on multiprocessing timing anomalies', SIAM Journal on Applied Mathematics 17, 416-429. Hall, N.G., and Sriskandarajah, C. (1991), 'Machine scheduling problems with blocking and no-wait in process', Working Paper no. 91-05, Department of Industrial Engineering, University of Toronto, Canada. Hochbaum, D.S., and Shmoys, D.B. (1987), 'Using dual approximation algorithms for scheduling problems: Theoretical and practical results', Journal of the A CM 34, 144-162. Langston, M.A. (1987), 'Interstage transportation planning in the deterministic flowshop environment', Operations Research 35/4, 556-564. Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G. (1982), 'Recent developments in deterministic sequencing and scheduling: A survey', in: M.A.H. Dempster et al. (eds.), Deterministic and Stochastic Scheduling, Reidel, Boston, MA, 35-73. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. (1989), 'Sequencing and scheduling: Algorithms and complexity', Report BS-R8909, Center for Mathematics and Computer Science, Amsterdam, The Netherlands. Lenstra, J.K., and Rinnooy Kan, A.H.G. (1985), 'Sequencing and scheduling', in: M. OhEigeartaigh, J.K. Lenstra and A.H.G. Rinnooy Kan (eds.), Combinatorial Optimization: Annotated Bibliographies, Wiley, Chichester, 164-189. Rock, H. (1982), 'Three machine no-wait flowshop: Complexity and approximation', Report 82-07, Fachbereich Informatik, Technical University of Berlin, Berlin. Rock, H., and Schmidt, G. (1983), 'Machine aggregation heuristics in shop scheduling', Methods of Operations Research 45, 303-314. Salvador, M.S. (1973), 'A solution of a special class of flowshop scheduling problems', in: Proceeding of the Symposium on the Theory of Scheduling and its Applications, Springer-Verlag, Berlin, 83-91. Sriskandarajah, C. (1986), L'ordonnancement dans les ateliers: complexite et algorithmes heuristiques', Doctorate Thesis, Laboratoire d'automatique, Ecole National Superieure d'Ingenieurs Electriciens de Grenoble, France. Sriskandarajah, C., and Ladet, P. (1986), 'Some no-wait shops scheduling problems: Complexity aspect', European Journal of Operational Research 24, 424-445. Sriskandarajah, C., and Sethi, S.P. (1989), Scheduling algorithms for flexible flowshops: Worst and average case performance', European Journal of Operational Research 43,143-160. Wittrock, R.J. (1988), 'An adaptable scheduling algorithm for flexible flow lines', Operations Research 36, 445-453., A study on scheduling heuristic algorithms for no-wait flowshop manufacturing systems was conducted. The system is composed of several machine centers with identical parallel machines responsible for processing jobs. The proposed algorithms were evaluated in a worst case performance situation. Results show that minimum finish time schedules for flowshops with two machine centers require an algorithm within an optimal solution.

We consider scheduling problems that involve processors of different classes and jobs with fixed start and finish times. We allow preemption of jobs, but impose restrictions on the assignment processors to jobs. We present polynomial-time algorithms for finding the minimal-cost preemptive solutions for two special cases in which the number of job classes is at most one more than the numb processor classes. We then discuss a generalized version in which a processor can be assigned only t subset of the jobs and a job can be done only by a subset of the processors. We prove that for this the problem of finding a preemptive feasible schedule with a given combination of processors can be solved in polynomial time, by transforming it into a transportation-network problem. Next, we extend these results to cyclic scheduling problems. Further, we discuss some transformations among these cl scheduling problems and provide simpler proofs of NP-completeness for the nonpreemptive versions of the first two cases., A study on polynomial-time algorithms for preemptive scheduling of various classes of processors to perform jobs with fixed start and finish times was conducted. The algorithm was used to determine minimal-cost preemptive solutions for two scheduling problems. Results show that the algorithm was able to assign a preemptive feasible schedule in polynomial time using a combination of processors.

This paper extends T.C.E. Cheng's approach for optimal assignment of slack due-dates and sequencing in the single-machine shop to the case when preemption is allowed and there are precedenc constraints and ready times of jobs. It is shown that under special conditions the presented algorit may be used when preemption is not allowed., A study was conducted on optimal determination of slack due-dates for a set of jobs using single machine scheduling. The proposed algorithm is applied to instances wherein preemption is permitted and ready times of jobs and precedence constraints in the single-machine shop exists. Results show that optimal assignment of due-dates is vital to scheduling management and that the proposed algorithm can be applied to instances when preemption is not permitted.

In this paper, we address an n-job, single machine scheduling problem with an objective to minimize the flow time variance. We propose heuristic procedure based on genetic algorithms with the potential to address more generalized objective function such as weighted flow time variance. The development and implementation of the algorithm is supported with literature review and statistical analysis of the results. Some general guidelines to select the parameter values of the genetic algor are also developed using an experimental design approach., Studies were conducted on reducing flow time variance in a single-machine scheduling problem using a heuristic procedure based on genetic algorithms designed to address completion time variance problems. Results show that the algorithm required proper selection of parameter values for successful implementation. Results also show that population size and number of generations influence algorithms more than the other parameters.