A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem

Abstract

This paper presents a variable iterated greedy algorithm (IG) with differential evolution (vIG_DE), designed to solve the no-idle permutation flowshop scheduling problem. In an IG algorithm, size d of jobs are removed from a sequence and re-inserted into all possible positions of the remaining sequences of jobs, which affects the performance of the algorithm. The basic concept behind the proposed vIG_DE algorithm is to employ differential evolution (DE) to determine two important parameters for the IG algorithm, which are the destruction size and the probability of applying the IG algorithm to an individual. While DE optimizes the destruction size and the probability on a continuous domain by using DE mutation and crossover operators, these two parameters are used to generate a trial individual by directly applying the IG algorithm to each target individual depending on the probability. Next, the trial individual is replaced with the corresponding target individual if it is better in terms of fitness. A unique multi-vector chromosome representation is presented in such a way that the first vector represents the destruction size and the probability, which is a DE vector, whereas the second vector simply consists of a job permutation assigned to each individual in the target population. Furthermore, the traditional IG and a variable IG from the literature are re-implemented as well. The proposed algorithms are applied to the no-idle permutation flowshop scheduling (NIPFS) problem with the makespan and total flowtime criteria. The performances of the proposed algorithms are tested on the Ruben Ruiz benchmark suite and compared to the best-known solutions available at http://soa.iti.es/rruiz as well as to those from a recent discrete differential evolution algorithm (HDDE) from the literature. The computational results show that all three IG variants represent state-of-art methods for the NIPFS problem.

Introduction

The processing order is the same for all jobs in a flowshop situation. Furthermore, the job sequences are assumed to be permutations; therefore, once a permutation is fixed for all jobs on the first machine, this permutation is maintained for all machines, which is the so-called permutation flowshop scheduling problem (PFSP). Although several performance measures exist for scheduling in a flowshop, the makespan criterion is the most commonly studied performance measure in the literature (see [1], [2] for recent reviews of this problem).

This study focuses on solving a variant of the PFSP in which idle times are not allowed on machines. The no-idle constraint refers to an important practical situation in the production environment in which expensive machinery is employed [3], and idling of such expensive machinery is often undesirable. For instance, the steppers employed in the production of integrated circuits via photolithography are clear examples. Certain other examples arise in industries where less expensive machinery is employed. However, the machines cannot be stopped and restarted. For example, ceramic roller kilns consume large quantities of natural gas when in operation. Idling is not an option in this case because it takes several days to stop and restart the kiln due to notably large thermal inertia. In such cases, idling should be avoided. Another practical example is the furnace used in fiberglass processing in which glass batches are reduced to molten glass. Because it takes three days to heat the furnace back to the required temperature of 2800 °F, the furnace should remain in operation during the entire production season. In addition to the above examples, the three-machine flowshop production of engine blocks in a foundry is presented in [4]. This example includes the casting of sand molds and sand cores. The molds are filled with metal in fusion, and the cores prevent the metal from filling certain species in the mold. The casting machines operate without idle times due to both economic and technological constraints.

In a NIPFS problem, each machine must process jobs without any interruption from the start of processing the first job to the completion of the last job. Therefore, when needed, the start of processing the first job on a given machine must be delayed to meet the no-idle requirement. In this work, we denote the NIPFS problem with the well-known three-fold notation of $F_m/prmu,n{o}_{-}idle/C_{\max }$. The computational complexity of the $F_m/prmu,n{o}_{-}idle/C_{\max }$ problem is briefly commented in [5]. The NP-Hardness of the $F_3/prmu,n{o}_{-}idle/C_{\max }$ problem was proven by [6], [4]. Therefore, this problem has a significant importance both in theory and engineering applications for development of effective and efficient approaches to the problem discussed in this paper.

Despite its practical importance, the $F_m/prmu,n{o}_{-}idle/C_{\max }$ problem has not attracted much attention in the literature [7]. A polynomial time algorithm for optimally solving the F₂/prmu, no_idle/∑C_j problem was presented in [8]. The makespan criterion was studied for the first time in [9], whereas heuristic approaches for the general m-machine NIPFS problem with the makespan criterion were examined in [10]. A branch-and-bound (B&B) method is also presented by [6] for the general m-machine NIPFS problem with the makespan criterion.

Certain mistakes in the paper by [8] were reported in [11]. The $F_3/prmu,n{o}_{-}idle/C_{\max }$ problem was studied in [12], and the same problem was also studied in [4], in which a lower bound and an efficient heuristic are presented. This new heuristic favors the earlier method of the authors [13], who published this work later on in [14]. Kamburowski in [15] further enhanced the idea in [4] by proposing a network representation. A heuristic for the $F_3/prmu,n{o}_{-}idle/C_{\max }$ problem based on the traveling salesman problem (TSP) was proposed in [14]. The $F_2/prmu,n{o}_{-}idle/C_{\max }$ and $F_m/prmu,n{o}_{-}idle/C_{\max }$ problems were studied in two similar papers [12], [16]. In [17], Kalczynski and Kamburowski developed a constructive heuristic, called the KK heuristic, for the $F_m/prmu,n{o}_{-}idle/C_{\max }$ problem with a time complexity of O(n²m). The authors also presented an adaptation of the Nawaz, Enscore and the Ham (NEH) heuristic [18] for the NIPFS problem. In addition, Kalczynski and Kamburowski studied the interactions between the no-idle and no-wait flowshops in [17] as well. Recently, Baraz and Mosheiov introduced an improved two-stage greedy algorithm named GH_BM, which consists of a simple greedy heuristic and an improvement step based on the adjacent pairwise interchange (API) method in [7].

In recent years, meta-heuristics have attracted increasing attention in the solution of scheduling problems because they are able to provide high quality solutions with reasonable computational effort [19]. In addition to the above literature, in two similar papers, Pan and Wang in [20], [21] proposed discrete differential evolution (DDE_LS) and a hybrid discrete particle swarm optimization (HDPSO) algorithm for the same problem. In both papers, a speed-up scheme for the insertion neighborhood is proposed that reduces the computational complexity of a single insertion neighborhood scan from O(n³m) to O(n²m) when the insertion is carried out in order. The speed-up that they proposed is based on the well-known accelerations presented by [22] for the insertion neighborhood for the PFSP. In fact, both in DDE_LS and HDPSO, an advanced local search form, an IG algorithm proposed by [23], is employed as a local search. Both DDE_LS and HDPSO used the well-known benchmark suite of [24] by treating these as NIPFS instances to test the results. In both papers, the authors tested the proposed methods against the heuristics in [7], [25]. Recently, an IG_LS algorithm for the NIPFS problem with the makespan criterion was presented in [3]. These researchers employed their own benchmark suite and examined the performance of IG_LS in detail against the existing heuristics and meta-heuristics from the literature, whereas a continuous DE algorithm is presented in [26]. Most recently, a hybrid discrete differential evolution algorithm (HDDE) was presented in [27] in which a speed-up method based on network representation is proposed to evaluate the entire insertion neighborhood of a job permutation. Through a detailed experimental campaign, it was concluded that the HDDE algorithm was superior to the existing state-of-the-art algorithms from the literature.

In this paper, a vIG_DE algorithm and two other IG variants are presented for comparison to the best-known solutions in [3] as well as solutions presented by the HDDE algorithm in [27]. The computational results show that all three IG variants represent state-of-art methods for the NIPFS problem.

The remaining part of the paper is organized as follows. Section 2 introduces the NIPFS problem. Section 3 presents the vIG_DE algorithm and two other IG variants in detail, and Section 4 discusses the computational results in the context of benchmark problems. Finally, Section 5 presents the concluding remarks.