A Bat Algorithm with Generalized Walk for the Two-Stage Hybrid Flow Shop Problem

2.1. Presentation

A Hybrid Flow Shop (HFS) also called flexible flow shop is a system composed of a set of stages, where each stage is composed of one or more parallel machines (see Figure 1). The different jobs visit the stages in the same order. On each stage, a job is treated by one machine only. Between each stage, the jobs can wait or not in limited or unlimited buffers (Vignier et al., 1999, Billaut et al., 2000). Moreover, all jobs are assumed to be available at the system entrance with release date with value 0.

Scheduling in the HFS consists to find an adequate sequence of the jobs in entrance and an assignment of the jobs on the various machines at the various stages. The objective is optimization of a criterion of performance among the criteria. One can quote the makespan or Cmax (the completion time of the last job on the last stage), max flow time (Fmax), (Srivastava 1998, Dessouky et al., 1998, Portman et al.1998, Lamica 2000, Kyparisis and Koulamas, 2006, Jin et al., 2006, Tang et al., 2006) and due date related objective (Bank et al.,2001, Kim et al., 2002, 2003, Tang et al.2002). This problem can have many constraints (Dekhici and Belkadi, 2010).

2.2. Notation

• •

  M: Number of stages scheduled is M;

• •

  N: Number of tasks scheduled is N;

• •

  l_k: The number of machines in stage k is l_k.

The processing time of job I in stage j if machines are identical is noted t_ij.

Figure 1.

Schema of two stages HFS (l₁=3, l₂=2) C_max