Article Preview
TopIntroduction
This article deals with the scheduling of a reentrant hybrid flow shop. Scheduling consists of organizing operations required to complete a job in order to optimize a criterion. Even though scheduling problems are a well-known area of operational research (Dugardin, Chehade, Amodeo, Yalaoui, & Prins, 2007), the specificity of this system is the reentrant characteristic. In a reentrant shop, a job can be processed more than once on one or several machines. Studied first, in 1983, by Graves and Lamar (1983), the importance of this type of system is growing up since the semi-conductor industry uses it as it is discussed in the paper of Lee and Lee (2003). The review of Gupta and Sivakumar (2006) concerning reentrant scheduling is completed hereafter.
In 2004, Bertel and Billaut (2004) minimized the weighted sum of the tardiness with a genetic algorithm. Pan and Chen (2005) minimized the maximum of the completion time Cmax with several mixed integer programs. In the same year, Wang, Qiao, and Wu (2005) proposed a global heuristic to minimize the Cmax whereas Gupta and Sivakumar (2005) provided a method based on heuristic and simulation to optimize three different criteria. In 2005, Miragliotta and Perona Miragliotta proposed a decentralized heuristic to minimize the work in progress. In this year Choi, Kim, and Lee (2005) minimized the sum of the tardiness (total flow time) by mean of a distributed heuristic and list scheduling.
Chen (2006) minimized the Cmax by mean of a branch and bound algorithm. In 2007, two works minimized the sum of tardiness of the job (denoted as ∑Ti): Mönch, Schabacker, Pabst, and Fowler (2007) with a Genetic Algorithm and Kang, Kim, and Shin (2007) with a three phases algorithm. In the same year two other works dealt with reentrant shop: Chen, Pan, and Wu (2007) Minimizing makespan in reentrant flow-shops using hybrid tabu search, minimized the Cmax and Hsieh, Chen, and Chang (2007) optimized three different criteria trough scheduling policies.
Recently, three works dealt with the minimization of the Cmax:Yang, Kuo, and Chern (2008) proposed a branch and bound algorithm whereas Choi, Kim, Lee, Yoon, Yun, and Chae (2009) gave a branch and bound method and a heuristic algorithm. Finally Chen, Pan, and Lin (2008), with a hybrid genetic algorithm for the re-entrant flow-shop scheduling problem, provided a modular algorithm to minimize it. Moreover, Pearn, Chung, Yang, and Shiao (2008) minimized the workload with a heuristic procedure while Manikas and Chang (2008) minimized a weighted sum of different classical scheduling criteria with a genetic algorithm.
The literature review shows us a lack of multi-objective study, which is why we have decided to develop this type of resolution on this problem. Lastly, we have developed a multi-objective method to solve the reentrant hybrid flow-shop scheduling problem which seems to be more effective than the methods compared in Dugardin, Amodeo, and Yalaoui (2007) and Dugardin, Yalaoui, and Amodeo (2008, 2010). This work is to improve these results by using a local search.
Many local searches exist in the literature concerning the scheduling problems. These neighborhoods are divided into 2 classes: the swap operators and the extract-and-insertion operators as show in the works of Della Croce (1995). Moreover, Grosso, Della Croce, and Tadei (2004) have improved this operator with the dynasearch structure. On the other side Ergun and Orlin (2006) improve the complexity concerning the single machine total weighted tardiness problem. Recently, Huang and Wang (2006) have introduced a procedure called block replacement in order to avoid local optimum.