Hybrid Multi-Objective Methods to Solve Reentrant Shops

Hybrid Multi-Objective Methods to Solve Reentrant Shops

Frédéric Dugardin (LOSI, University of Technology of Troyes, Troyes, France), Farouk Yalaoui (LOSI, University of Technology of Troyes, Troyes, France) and Lionel Amodeo (LOSI, Industrial Systems Optimization Department, University of Technology of Troyes, Troyes, France)
Copyright: © 2012 |Pages: 18
DOI: 10.4018/jal.2012100102
OnDemand PDF Download:


This article examines the multi-objective scheduling of a reentrant hybrid flow shop. This type of shop is composed of several stages made of several identical parallel machines. When a task has to be processed on a stage, it is assigned to the machine with the smallest workload. This problem shows a reentrant structure: each task must be processed several times at each stage. In this paper, this problem is solved by minimizing two objectives: the makespan (maximum completion time of the jobs) and the total tardiness of the tasks. A new method is improved with different local searches: Adjacent and Non Adjacent Pairwise Interchange, Extract and Backward-Shifted Reinsertion, and Extract and Forward-Shifted Reinsertion. Every local search is tuned with statistical method (design of experiment) and the best one is worked out. This method is compared with the best one in several instances. The results involve three different measures.
Article Preview


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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 7: 2 Issues (2017): 1 Released, 1 Forthcoming
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing