Article Preview
Top1. Introduction
The actual situations that give rise to scheduling problems are wide and varied. This paper considered a specific class of multiple machine scheduling problems with parallel identical machines, called the hybrid flow shop (HFS) scheduling problems. An HFS scheduling problem is a classical flow-shop in which parallel machines are available to perform the same operation. It can be briefly described as follows: a set of jobs ‘j’ has to be processed on a set of processing centers. Each center includes a set of parallel machines. Each job consists of a sequence of operations processed at successive centers and all jobs pass through centers in the same order. There is no distinction between machines in a center. Hence, any machine at each center may process a job. HFS schematic view shows in Figure 1 (see Figure 1 in the Appendix).
Figure 1. Schematic view of hybrid flow shop
- •
The hybrid flow shop problems have the following characteristics:
- •
The number of processing machines ‘m’ is at least 2.
- •
Each stage ‘k’ has M (k) ≥ 1 machines in parallel and in at least one of the stages M (k) > 1.
- •
All jobs are processed following the same production sequence: stage 1, stage 2…….stage m.
- •
Each job j requires a processing time on machines.
Top2. Hybrid Flow Shop Classification
The HFS problems are classified according to their shop configuration, constraints, assumptions, and the objective function considered. The configuration defines the structure of the shop, including the number of stages and the number and characteristics of the machines per stage. The configuration compared four parameters α 1, α 2, α 3 and α 4. α 1 denotes the general configuration of the shop (i.e., Hybrid flow shop). α 2 is the number of stages in the shop. α 3 and α 4 describe the properties of machines per stage. The notation (α 3 α 4) k means that there are α 4 parallel machines of the type α 3 in stage k (Pinedo, 2002).
The second element is list of constraints and assumptions. The most common constraints and assumptions are:
- 1.
Job j cannot start processing before its release date rj.
- 2.
The jobs are processed in every stage in the same order.
- 3.
The precedence constraints between operations from different jobs.
- 4.
The processing of job j is restricted to the set of machines at stage k. This is known as eligibility.
- 5.
The preemptions are permitted.
- 6.
The buffer capacities between stages are limited. The jobs must wait in the previous stage until sufficient space is released.
- 7.
The machines are available at all times.
- 8.
No-wait jobs are not allowed to wait between two successive stages. This implies that the shop operates under the First in First out (FIFO) discipline.
The objective function is a third element. The HFS problems are NP-hard problems even with m = 2 according to Hoogeveen, Lenstra, and Veltman (1996). So the most of the authors are considered only single objective functions. The objective functions are described in Table 1 (see Table 1 in the Appendix).