A new evolutionary clustering search for a no-wait flow shop problem with set-up times

https://doi.org/10.1016/j.engappai.2012.05.017Get rights and content

Abstract

This paper addresses the m-machine no-wait flow shop problem where the set-up time of a job is separated from its processing time. The performance measure considered is the total flowtime. A new hybrid metaheuristic Genetic Algorithm–Cluster Search is proposed to solve the scheduling problem. The performance of the proposed method is evaluated and the results are compared with the best method reported in the literature. Experimental tests show superiority of the new method for the test problems set, regarding the solution quality.

Introduction

The general flow shop scheduling problem is a production problem where a set of n jobs has to be processed with identical flow pattern on m machines. When the sequence of job processing on all machines is the same we have the flow shop sequencing production environment known as the permutation flow shop. Since there is no job passing permitted, the number of possible schedules for n jobs is n!.

There are a few simplifications considered on this environment; one of these assumptions is that there exists an infinite storage capacity between machines. Under this situation, jobs are allowed to wait for machines to be available for as much time as necessary. In practice, this means that an interruption of the current processing job might take place in between machines. In many scheduling environments, however, processing of some or all jobs needs to be carried out without interruptions between machines. This situation is commonly known as “no-wait”. A typical example comes from steel production where the steel ingots are not allowed to wait between production stages or otherwise they would cool off. Other examples can be found in chemical and pharmaceutical industries, among many others. These types of problems are reviewed in detail in Hall and Sriskandarajah (1996); Framinan and Nagano (2008) and Framinan et al. (2010).

Another widely accepted assumption is to neglect the setup times by considering them as being part of the processing times. This assumption may be valid when setups are small, independent of the processing sequence, and inseparable from the processing times. However, this is not the case for many production environments where setup times are large and can be separated from processing times.

In this paper we tackle a flow shop scheduling problem with both no-wait and separate sequence independent setup time constraints with the criterion of total completion time minimization. This criterion is more realistic than the more common makespan minimization (Cmax) as it is known to increase productivity while at the same time reduce the work-in-progress (WIP). Following the three field notation of Graham et al. (1979) this problem is denoted as Fm/nowait,sij/Ci for the general m machines case.

Regarding the objective of total completion time, Aldowaisan and Allahverdi (1998) deal with the F2/nowait,sij/Ci problem and provide sequencing rules for some special cases as well as a dominance rule and a heuristic method for the general case. The same problem is considered in Aldowaisan (2001), where a global dominance relation along with a heuristic and a branch and bound method is provided. In a related work (Allahverdi and Aldowaisan (2000)) the authors extend the work of Aldowaisan and Allahverdi (1998) to three machines with an improved dominance rule and present five high performing heuristics. Recently, Shyu et al. (2004) have presented an ant colony optimization algorithm (ACO) that works with a TSP representation of the F2/nowait,sij/Ci problem. The results show that the algorithm is better than the heuristic of Aldowaisan and Allahverdi (1998). The ACO algorithm of Shyu et al. (2004) for the two machine case and the five heuristics of Allahverdi and Aldowaisan (2000) can be extended to the m machines case.

In Brown et al. (2004) an algorithm called TRIPS based on variants of the TSP is presented for Fm/nowait,sij/Ci and Fm/nowait,sij/Cmax problems.

Ruiz and Allahverdi (2007) showed an effective rule for the four machine case that can also be used for m machines. Five simple and fast heuristics were proposed along with two easy to code stochastic local search methods, one of them being based on Iterated Local Search (ILS). All seven methods were compared to two recent algorithms, which are the ACO of Shyu et al. (2004) and the TRIPS of Brown et al. (2004) (TRIPS). Their results, confirmed through statistical analyses, show that the proposed methods are more effective and efficient when compared to the existing algorithms.

This paper is organized as follows. In Section 2, the general concepts of the Clustering Search (CS) algorithm are introduced. In Section 3 we detail a metaheuristic method that combines Genetic and Cluster Search Algorithms for the No-Wait Flow Shop problem with Setup Times. Section 4 presents the results obtained through computational experiments; furthermore, the method's performance is evaluated and compared to the best method found in the literature. Finally, conclusions are presented in Section 5.

Section snippets

Clustering search algorithm

The Clustering Search algorithm generalizes the Evolutionary Clustering Search (ECS), proposed by Oliveira and Lorena, 2004, Oliveira and Lorena, 2007, that employs clustering for detecting promising areas of the search space. It is particularly interesting to find out such areas as soon as possible to change the search strategy over them. An area can be seen as a search subspace defined by a neighborhood relationship in the metaheuristic coding space. In the ECS, a clustering process is

Evolutionary clustering search for a no-wait flow shop with set-up times

Inspired by the ECS proposed in Ribeiro Filho et al. (2007) to solve the Permutational Flow Shop problem with the objective of minimizing total flow time, we have adapted the metaheuristic that combines Genetic Algorithms (GA) and CS to the no-wait flow shop problem with separated set-up times. The ECS uses a GA to implement the SM component of the CS and generate solutions that allow the exploration of promising regions by the other components of CS.

The Evolutionary Clustering Search for

Computational results

Although some methods were mentioned in this paper, the new ECS_NSL has been compared only to the best-known existing algorithm that is based on Iterated Local Search proposed by Ruiz and Allahverdi (2007) (ILS_RA).

In the computational tests, the heuristics were coded in C and have been run on a microcomputer Intel Core 2 Quad, 2.4 GHz, 2 Gb RAM.

The computational experience was performed on two instance groups from Ruiz and Allahverdi (2007). The first one, called “small”, comprises all

Final remarks

The main objective of this paper was applying CS to the no-wait flow shop problem with set-up times of original and unedited form.

The experimental results of the simulation from the given tables lead us to the following major conclusions:

  • (i)

    Computational results lead us to an experimental conclusion that ILS_RA is not superior to the CS_NSL for the small instances set. Moreover, taking into account the percentage of success, it is expected that CS_NSL provides a total completion time lower than

Acknowledgments

This research was supported by National Council for Scientific and Technological Development – CNPq, Brazil (Grant no. 554546/2009-4, 476753/2011-2, 303000/2010-4, 300692/2009-9 and 470813/2010-5). The authors would like to thank unanimous referees for their helpful recommendations which improved the quality of the paper significantly.

References (18)

There are more references available in the full text version of this article.

Cited by (50)

  • Flow shop scheduling with jobs arriving at different times

    2018, International Journal of Production Economics
View all citing articles on Scopus
View full text