...of the [m.sub.1] machines in stage and, upon completion, the second stage task is processed on any of the [m.sub.2] machines in stage 2. Upon completing processing on the first stage, a job can wait between the two stages and the intermediate storage (buffer) is of unlimited capacity. No machine can process more than one job at a time and no preemption is allowed for the jobs. The machines in stage s, s = 1, 2, are 'uniform'. Let [v.sub.k,s] be the processing speed of machine k at stages. For simplicity we number the machines in increasing order of their speeds so that [v.sub.1,s] = 1 [less than or equal to] [v.sub.2,s] [less than or equal to] [v.sub.3,s] [less than or equal to] ... [less than or equal to] [v.sub.s,s], S = 1, 2. The 'standar d' processing times are denoted by p(j, 1), p(j, 2) in stages 1 and 2; respectively, which are specified in terms of the (relatively) slowest machine at each stage.

The objective is to find a schedule which minimizes the maximum completion time of all the jobs (the makespan), [C.sub.max]. We denote the above problem as the F2(Q[m.sub.1], Q[m.sub.2])/ - /[C.sub.max] problem. This problem is strongly NP-complete (Hoogeveen et al., 1996), and the formal mathematical programming models offer very little help in realistic problems; hence we shall focus on heuristic approaches.

2. Literature review

This type of production system is frequently encountered in practice, ranging over the fiber industry (Salvador, 1973), flexible manufacturing systems (Wittrock, 1988; Lee and Vairaktarakis, 1994), textile industry (Riane et al., 1996), semiconductor industry (Herrmann and Lee, 1992; Lee and Herrmann, 1993), metallurgical industry, glass container industry (Paul, 1979) glass manufacturing industry (Mei, 1996), cable manufacturing industry (Narasimhan and Panwalkar, 1984), among other process industries.

In addition to its applicability to many industries, the above structure may also be encountered in several applications in computer systems. Shen and Chen (1972) and also Buten and Shen (1973) consider the scheduling problem for computer systems with two classes of processors to support a variety of on-line services in addition to carrying an ever increasing computer load.

As one of the earliest studies on the two-stage hybrid flowshop scheduling problem, Buten and Shen (1973) give a heuristic algorithm that they call MJO (for 'Modified Johnson's Order') for the hybrid flowshop problem with two stages, i.e., the F2(P[m.sub.1], P[m.sub.2])/ - /[C.sub.max] problem. Their heuristic is based on a simple transformation of the two stage hybrid flowshop problem into an auxiliary problem that has only one machine in each stage. Buten and Shen (1973) prove that if the jobs satisfy a certain loading constraint, which basically requires that the size of each job should not be relatively too long, then the worst-case performance ratio of MJO is

2 - 1/max{[m.sub.1], [m.sub.2]}

Later, Chen (1995) demonstrated that their proof is not free of errors, which motivated him to develop a new heuristic which he calls CLS (for 'Concatenating List Schedules of Johnson's Order'). The same idea seems to have been developed independently by Lee and Vairaktarakis (1994) to reach the same conclusion. Note that if we set p(j, 2) = for all jobs j [member of] J, then the above bound coincides with the worst-case performance bound (w.c.p.b.) of the Random Decreasing Machine (RDM) rule (randomly create a sequence of jobs, then the first available machine picks a job from the head of the list) for the parallel identical machines (Graham, 1966, 1969). For extensive reviews of prior contributions to the field of flexible flowshops in general, see the papers of Lee and Vairaktarakis (1994, 1998).

Kouvelis and Vairaktarakis (1998) consider the two-stage hybrid flowshop with identical machines and an additional 'flexibility' in the following sense: a job may be processed to completion in either stage 1 or stage 2, or it may be split into two parts with the first part executed in stage 1 and the second in stage 2, in that order.

To the best of our knowledge, the only other treatment of uniform Worm machines is a recent contribution due to Huang and Li (1998). They deal with two stages, but their first stage contains only one machine; the second stage contains M [greater than or equal to] 2 uniform Worm machines. They consider 'families' of different types of jobs with setup times among the families but not within the same family. The setup times are sequence independent. They develop simple lower bounds and propose two heuristics, which efficacy are demonstrated through extensive experimentation.

We view this paper as offering two contributions. The first is the extension of analysis to the case of uniform machines in two stages. The second is to highlight the Qm\[r.sub.i]\[C.sub.max] problem as a fundamental building block in the design of heuristic procedures in hybrid flowshops (see also Lee and Vairaktarakis (1998)).

3. Preliminary: the single stage Qm\ - \[C.sub.max] problem

We first develop several preliminary results related to the Qm\ - \[C.sub.max] problem (a single stage with m machines) that will be needed in later development, and denote the processing time of job j by [P.sub.j]. Instead of the 'First Available Machine (FAM)' rule (Gonzalez et al., 1977; Dobson, 1984; Friesen, 1987; Morrison, 1988), we utilize the 'Earliest Finish Machine (EFM)' rule which is a generalization of the FAM rule to the case of parallel uniform machines. Briefly, EFM assigns the next job in the sequence to the machine that would finish it the earliest.

Let C(j, 1) be the resulting completion time of job j in stage 1 under EFM. The following two propositions give an upper bound (u.b.) and a lower bound (l.b.) to C(j, 1).

Proposition 1. Renumber the jobs after applying EFM according to non-decreasing completion times so that C(1, 1) [less than or equal to] C(2, 1) [less than or equal to] ... [less than or equal to]C(j, 1). Let [C.sup.*](j, 1) denote the optimal completion time of jobs 1 through j. Then we must...

NOTE: All illustrations and photos have been removed from this article.



More articles from IIE Transactions
A problem space algorithm for single machine weighted tardiness proble..., May 01, 2003

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.