Article Preview
Top2. Literature Review
In order to solve HFS problems, many solution methodologies are proposed in the literature (Linn & Zhang, 1999) and (Ruiz & Vázquez-Rodríguez, 2010). Exact approaches are suitable for small-sized problems but get very time consuming when the size is large. For practical purposes, it is more appropriate to use approximate methods. In fact, they are able to achieve good solutions (or eventually optimal) for scheduling problems in an acceptable time.
We quote hereafter, some recent studies carried out on the HFS problem minimizing the makespan. Exact techniques included branch and bound algorithms (B&B) (Vignier, Commandeur, & Proust, 1997; Néron, Baptiste, & Gupta, 2001; Haouari, Hidri, & Gharbi, 2006), mixed integer programming (Guinet, Solomon, Kedia, & Dussa, 1996), or dynamic programming-based heuristic (Riane, Artiba, & Elmaghraby, 1998). For solving the two-stage HFS problem, some heuristic methods based on Johnson’s algorithm (Johnson, 1954) are developed (Guinet, Solomon, Kedia, & Dussa, 1996; Lee, Cheng, & Lin, 1993). Santos et al. (1996) adapted some pure flow-shop heuristics in the HFS environment. Various intelligent heuristics and meta-heuristics have become popular such as simulated annealing (SA) (Gourgand, Grangeon, & Norre, 1999; Jin, Yang, & Ito, 2006), tabu search (TS) (Nowicki & Smutnicki, 1998), genetic algorithms (GA) (Portmann, Vignier, Dardilhac, & Dezalay, 1998; Jin, Ohno, Ito, & Elmaghraby, 2002; Besbes, Loukil, & Teghem, 2006), approaches based on artificial immune systems (AIS) (Engin & Döyen, 2004).