Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
Introduction
Permutation flowshop scheduling (PFSP) has been extensively studied in the literature and has important applications in manufacturing and service systems [1], [2], [3], [4]. In the traditional permutation flowshop scheduling problem, jobs are processed on machines in the same permutation, and work-in-process inventory is allowed since there are infinite buffer capacities amongst consecutive machines. In other words, jobs are allowed to be waiting for their next operations. However, if there does not exist any storage capacity amongst machines, the traditional PFSP become a blocking flowshop scheduling problem (BFSF) [5]. In this case, a job cannot leave the machine unless the next machine is free. The BFSP has important applications in industry which can be found in [5,6]. A comprehensive review on flowshop scheduling with blocking and no-wait constraint can be found in Hall and Sriskandarajah [7].
In this paper, we consider the BFSP with the makespan criterion. With the notation of Graham et al. [8], this problem is denoted as . About the computational complexity of the problem, even though Gilmore and Gomory’s algorithm [9] can solve it to optimality when the number of machines is two ( it is proven to be NP-Hard by Hall and Sriskandarajah [7] when . For this reason, heuristic approaches should be considered for scheduling a large number of jobs, which is commonly required in industry.
Due to the NP-Hard nature of the problem, constructive heuristic and meta-heuristic algorithms have been developed for solving the BFSP. Regarding the constructive heuristics, a profile fitting (PF) heuristic is developed by McCormick et al. [10] in order to solve sequencing problems with blocking to minimize cycle time. The PF heuristic basically tries to sequence the next job having minimum idle and blocking times on machines. Another approach is presented by Leisten [11] in order to deal with flowshop scheduling problems with finite and unlimited buffers to maximize the buffer usages and to minimize the machine blocking times. However, the heuristic developed in [11] was not able to yield better solutions than the NEH heuristic, which is initially proposed in [12] to solve the traditional PFSP. Based on the makespan properties defined by Ronconi and Armentano [13], Ronconi [6] proposed a note on constructive heuristics and developed three constructive heuristics, called minmax (MM), MM combined with NEH (MME), and PF combined with NEH (PFE), respectively for the BFSP with the makespan criterion. In the light of computational analysis, it was demonstrated that the MME and PFE heuristics were superior to the NEH algorithm in problems with up to 500 jobs and 20 machines. Abadi et al. [14] proposed an improvement heuristic for minimizing cycle time in blocking flowshop which can be employed for the BFSP with the makespan criterion. Ronconi and Henriques [15] tried to minimize the total tardiness in a flowshop with blocking and presented some constructive heuristics providing promising results for the problems considered. In addition to above, some effective heuristics based on PF approach were proposed in Pan and Wang [16]. These PF based heuristics are also inspired from LR heuristic proposed by Liu and Revees [17] for the PFSP with total flowtime criterion. They combined PF heuristic with the partial NEH implementation and called the heuristics as PF_NEH(x), WPF_NEH(x) and PW_NEH(x), where x is the number of sequences generated by considering the first x number of jobs in the initial order of jobs. In order to retain good characteristics of the PF heuristic, the NEH heuristic is applied to only the last jobs. Their PW_NEH(5) heuristic was substantially better than NEH, MME, PFE, WPFE and PWE heuristics from the literature.
Regarding the meta-heuristic algorithms, a genetic algorithm (GA) was presented in Caraffa et al. [18]. Ronconi [19] presented a branch and bound algorithm to report the upper bounds for Taillard’s benchmark suite [20]. Grabowski and Pempera [21] presented a fast tabu search. Wang et al. [22] proposed a hybrid genetic algorithm. Liu et al [23] developed a hybrid particle swarm optimization algorithm. Qian et al. [24] developed a differential evolution algorithm. Liang et al. [25] proposed a multi-swarm particle swarm optimization algorithm. Harmony search algorithms were developed by Wang et al. [26], [27]. Wang et al. [28] proposed a hybrid discrete differential evolution algorithm (HDDE). Ribas et al. [29] proposed an iterated greedy algorithm (IGA) with excellent results, where all best known solutions were further improved. Wang et al. [30] developed a three phase algorithm. effective heuristics with a local search were also presented in [16]. A revised artificial immune algorithm (RAIS) was presented by Lin and Ying [31], where an IG algorithm was also developed. A memetic algorithm (MA) was presented by Pan et al. [32]. A competitive variable neighborhood search (SVNS) algorithms were proposed by Ribas et al. [33] and all the best known solutions reported in [29] were further improved by the SVNS algorithms.
Main contributions of this paper can be summarized as follows. We propose a constructive heuristic with results, which are superior to those in the current literature. For the PFSP and its variants with the makespan criterion, the reduction methods of computational complexity for the insertion neighborhood were proposed by Grabowski and Pempera [5], Taillard [34], Nowicki and Smutnicki [35], Smutnicki [36], and Nowicki [37]. By inspiring from these reduction techniques, Wang et al. [28] developed a speed-up method to evaluate the whole insertion neighborhood for the BFSP with the makespan criterion. We show in this paper that this speed-up method is extremely effective in solving the BFSP with the makespan criterion. Along with it, we also employ a simple speed-up method from Lia et al. [38], for the swap neighborhood, which is adapted for the BFSP with the makespan criterion. In addition, an iteration jumping probability is proposed to jump from one neighborhood structure to another one; hence resulting in a variable neighborhood search algorithm. Instead of employing these two neighborhood structures in a framework of the variable neighborhood descend (VND) algorithms [39], we present two powerful local search algorithms, where the search process is guided by an iteration jumping probability determining which neighborhood structure will be employed. By means of a jump to the swap neighborhood with a small probability, it is shown that some additional enhancements can be gathered while retaining the effectiveness of the insertion neighborhood. We also show that the performance of the iterated greedy algorithm significantly depends on the speed-up method employed. The parameters of the iterated greedy algorithms are tuned through a design of experiments approach on randomly generated benchmark instances. Extensive computational results on Taillard’s well-known benchmark suite show that the proposed iterated greedy algorithms with speed-up methods are equivalent or superior to the best performing algorithms from the literature. Especially, we show that iterated greedy algorithms proposed are substantially and significantly better than SVNS algorithms, which are recently proposed by Ribas et al. [33]. Ultimately, 85 out of 120 problem instances are further improved with substantial margins.
The rest of the paper is organized as follows. In Section 2, the blocking flow shop scheduling problem with speed-up methods is formulated. Section 3 presents the IG algorithms with iteration jumping, VND and SVNS variants. Section 4 presents the design of experiment approach for parameter tuning. Extensive computational results and comparisons are provided in Section 5. Finally, Section 6 gives the concluding remarks.
Section snippets
Blocking flow shop scheduling problem
In the blocking flow shop scheduling problem, jobs form the set have to be processed on machines from the set with the same permutation on each machine without any intermediate buffer. Each job has a sequence of operations. Each operation has a processing time denoted as The setup time is assumed to be included in the processing time. Only one job can be processed on each machine. Since the waiting times are not allowed in the flowshop due to the no
Iterated greedy algorithms
The IG algorithm is developed by Ruiz and Stützle [40]. In the IG algorithm, new solutions are simply generated as follows: The current solution first goes under destruction–construction phase, where jobs are randomly taken from the current solution and they are re-inserted into partial solution sequentially. Then a local search is applied. An acceptance criterion is imposed on the new solution after a local search. These simple steps are repeated until a stopping criterion is satisfied.
Design of experiments for parameter settings
In this section, we present a Design of Experiments (DOE) approach [49] for parameter settings of the IG_JP algorithm. In order to carry out experiments, we generate random instances with the method proposed in [20]. In other words, random instances are generated for each combination of and . Ten instances are generated for each job and machine combination of , , , , , , , , , , , and , respectively.
Computational results
In this section, we compare IG_IJ and IG_RIS algorithms to IG_VND variants and SVNS variants as well as to IGA [29], HDDE [28] and MA [32] algorithms from the literature. Parameters of IG_IJ and IG_RIS algorithms are determined through a DOE approach given in Section 4. For the IG_IJ and IG_RIS algorithms and IG_VND variants, the destruction size, iteration jumping probability and temperature adjustment parameter are taken as , , , respectively. As suggested in Ribas et al.
Conclusions
This paper presents iterated greedy algorithms for solving the blocking flowshop scheduling problem (BFSP) with the makespan criterion. In this paper, we propose a constructive heuristic to generate an initial solution. The constructive heuristic generates better results than those currently in the literature. We adapted well-known speed-up methods from the literature for both insertion and swap neighborhood structures. Furthermore, an iteration jumping probability is proposed to change the
References (50)
- et al.
An estimation of distribution algorithm for lot-streaming flow shop problems with setup times
Omega
(2012) - et al.
Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem
Omega
(2010) - et al.
Makespan and workstation utilization minimization in a flowshop with operations flexibility
Omega
(2011) - et al.
Sequencing of jobs in some production system
Eur J Oper Res
(2000) A note on constructive heuristics for the flowshop problem with blocking
Int J Prod Econ
(2004)- et al.
A heuristic algorithm for the m-machine, n-job flow shop sequencing problem
Omega
(1983) - et al.
Some heuristic algorithms for total tardiness minimization in a flowshop with blocking
Omega
(2009) - et al.
Effective heuristics for the blocking flowshop scheduling problem with makespan minimization
Omega
(2012) - et al.
Constructive and composite heuristic solutions to the P//SCi scheduling problem
Eur J Oper Res
(2001) - et al.
Minimizing makespan in a blocking flowshop using genetic algorithms
Int J Prod Econ
(2001)
Benchmarks for basic scheduling problems
Eur J Oper Res
The permutation flow shop problem with blocking. A tabu search approach
Omega
An effective hybrid genetic algorithm for flow shop scheduling with limited buffers
Comput Oper Res
An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers
Comput Oper Res
Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms
Expert Syst Appl
A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem
Comput Ind Eng
A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems
Comput Oper Res
An iterated greedy algorithm for the flowshop scheduling with blocking
Omega
A three-phase algorithm for flowshop scheduling with blocking to minimize makespan
Comput Oper Res
Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm
Omega
Some efficient heuristic methods for the flowshop sequencing problem
Eur J Oper Res
A fast tabu search algorithm for the permutation flow-shop problem
Eur J Oper Res
The permutation flow shop with buffers: a tabu search approach
Eur J Oper Res
Variable neighborhood search
Comput Oper Res
A simple and effective iterated greedy algorithm for the permutation flowsop scheduling problem
Eur J Oper Res
Cited by (108)
A feedback learning-based selection hyper-heuristic for distributed heterogeneous hybrid blocking flow-shop scheduling problem with flexible assembly and setup time
2024, Engineering Applications of Artificial IntelligenceDynamic shop-floor scheduling using real-time information: A case study from the thermoplastic industry
2023, Computers and Operations ResearchA hybrid meta-heuristic for the flexible flow shop scheduling with blocking
2022, Swarm and Evolutionary ComputationA heuristic and meta-heuristic based on problem-specific knowledge for distributed blocking flow-shop scheduling problem with sequence-dependent setup times
2022, Engineering Applications of Artificial IntelligenceA matrix-cube-based estimation of distribution algorithm for blocking flow-shop scheduling problem with sequence-dependent setup times
2022, Expert Systems with Applications