An integrated ant colony optimization algorithm (IACS-HFS) is proposed for a multistage hybrid flow-shop scheduling problem. The objective of scheduling is the minimization of the makespan. To solve this NP-hard problem, the IACS-HFS considers the assignment and sequencing sub-problems simultaneously in the construction procedures. The performance of the algorithm is evaluated by numerical experiments on benchmark problems taken from the literature. The results show that the proposed ant colony optimization algorithm gives promising and good results and outperforms some current approaches in the quality of schedules.
TopLiterature 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).