الگوریتم مصنوعی کلونی زنبور عسل گسسته برای به حداقل رساندن مجموع زمان جریان در جایگشت جریان مغازه ها

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.

Flowshop scheduling is among the most prevalent problems in the field of deterministic scheduling in engineering industries [3], [14], [22], [29] and [47]. The permutation flowshop represents a particular case in which solutions are represented by the permutations of n jobs, i.e., π = {π1, π2, … , πn}. Each job comprises a set of m operations that must be performed by different machines. Each machine can process only one operation at a time. While all jobs have the same permutations on every machine, these jobs, once initiated, cannot be interrupted (preempted), and the release times of all jobs are zero. Given the processing time pjk for job j on machine k, we consider the total flowtime criterion as the objective function to be minimized. In the above specified context, F(πj), denoted by the flowtime of job πj, is equivalent to the completion time C(πj, m) of job πj on the last machine m because the release times of all jobs are zero. As a result, the total flowtime TFT(π) of a permutation π can be computed by summing up flowtimes or completion times of all jobs and defined as View the MathML sourceTFT(π)=∑j=1nF(πj)=∑j=1nC(πj,m). Then the optimal permutation View the MathML sourceπ∗=π1∗,π2∗,…,πn∗ in the set of all permutations of Π is determined by TFT(π∗) ⩽ TFT(π) for each permutation π belonging to Π. Under these specifications, the completion time for the n-job and m-machine problem is computed as follows: equation(1) C(π1,1)=pπ1,1C(π1,1)=pπ1,1 equation(2) View the MathML sourceC(πj,1)=C(πj-1,1)+pπj,1j=2,…,n equation(3) View the MathML sourceC(π1,k)=C(π1,k-1)+ppi1,kk=2,…,m equation(4) View the MathML sourceC(πj,k)=max{C(πj-1,k),C(πj,k-1)+pπj,k}j=2,…,n;k=2,…,m Many different algorithms have been proposed over time in an attempt to find the exact solution to minimizing the total flowtime (TFT). Several variants of branch and bound algorithms were developed [4], [5], [11] and [41]; Ignall and Scharge [11] were the first to apply the branch and bound scheme based on two lower bounds in the two-machine flow shop problem. Then Bansal [4] extended their idea to the m-machine case. Recent publications [5] and [41] have detailed the development of lower bounding methods either based on Lagrangian relaxation or by introducing slack variables. These exact methods have been successfully implemented in a limited number of small instances due to lengthy execution times. For large instances in the n-job and m- machine total flowtime problem, some efficient heuristics have been developed in [2], [7], [8], [10], [23], [26], [31] and [45]. The NEH constructive method, proposed by Nawaz et al. [28], was claimed to be the best for makespan minimization in flow shops, but not effective for total flowtime minimization. Therefore, to minimize total flowtime, the heuristics in both Woo and Yim [45] and Framinan and Leisten [7] were founded on different insertion schemes from NEH. Furthermore, a composite heuristic proposed by Allahverdi and Aldowaisan [2] adopted the insertion with pair-wise exchange from Framinan and Leisten [7] to improve their solutions. So far, no heuristic is optimal for total flowtime minimization. In comparison to heuristic methods, metaheuristic methods always obtain better results, as they compose many different kinds of algorithmic components [9], [12], [21], [27], [32], [42], [43], [46] and [48]. Very recently, an estimation of distribution algorithm (EDA) hybridized with variable neighborhood search (VNS) has been introduced in [13]. In addition to EDA, two genetic local search algorithms have been proposed in [24] and [25]. The first one employs a local search called insertion search with cut and repair, denoted by hGLS, and the second one is the genetic algorithm hybridized with a tabu search, denoted by tsGLS. These three algorithms improved almost all the best known solutions in the existing literature. Among metaheuristics, modeling the collective behavior of self-organized systems and applying these models to solve real-world problems has been ongoing and has become a class of its own, known as swarm intelligence. Earlier works implementing the ant colony optimization (ACO) and particle swarm optimization (PSO) algorithms were conducted to simulate the swarm behavior of ant colonies and flocks of birds, respectively. Recently, some algorithms were proposed by modeling the specific intelligent behaviors of honeybee swarms [1], [15], [16], [17], [18], [19], [29], [40] and [44]. Karaboga in [15], [16], [17], [18] and [19] introduced an artificial bee colony (ABC) algorithm to optimize multi-variable and multi-modal continuous functions. Numerical comparisons demonstrated that the performance of the ABC algorithm is as competitive as other population-based algorithms with the advantage of employing fewer control parameters [15], [16], [17], [18] and [19]. Furthermore, a discrete version of the ABC algorithm has been recently applied to the lot-streaming flowshop scheduling problem in [29]. Tereshko attempted to model the forage behavior of a honeybee colony based on reaction–diffusion equations [40]. Wede and Farooq proposed a routing algorithm, called BeeAdHoc, for energy efficient routing in mobile ad hoc networks [44]. Clearly, swarm intelligence can be understood as an algorithmic framework inspired by the aggregate behavior of the social insects and animals [1]. It has drawn the attention of researchers because of its advantages such as scalability, fault tolerance, adaptation, speed, modularity, autonomy, and parallelism [20]. As there is no detailed work that describes the use of the ABC algorithm to deal with the PFSP under the TFT criterion, we present a novel discrete ABC (DABC) algorithm as well as the hybrid version of our previous discrete differential evolution (hDDE) algorithm in [30] in order to solve the PFSP with the TFT criterion in this paper. The proposed algorithms are hybridized with a local search procedure, denoted by LocalSearch() based on swap and insertion neighborhood structures. The main purpose of the hybridization stems from the fact that DABC and DDE carry out the global search by exploration of the search space, whereas local search is responsible for intensifying the search on the local minima. Therefore, the balance in global and local searches has been effectively achieved. Through an experimental analysis, it is shown that the performance of the proposed algorithms is as competitive as the recent three best performing algorithms in terms of solution quality and CPU usage time. Ultimately, 44 out of the 90 best-known solutions recently provided by the EDA, tsGLS, and hGLS algorithms are further improved by the proposed algorithms with short-term search. For long-term search, the new best-known solutions are reported for Taillard’s benchmark suite [35]. The remaining paper is organized as follows. Section 2 introduces the DABC; and Section 3 presents the hDDE algorithm. The details of the local search algorithms developed for the PFSP with TFT criterion are provided in Section 4. Section 5 discusses the computational results over benchmark problems. Finally, Section 6 comprises the concluding remarks.

In this paper, we considered the applications of the DABC and hDDE algorithms to the PFSP under the TFT criterion. The DABC algorithm is hybridized with a variant of iterated greedy algorithms employing a local search procedure based on insertion and swap neighborhood structures. In addition, we also presented a hybrid version of our previous discrete differential evolution algorithm employing the same local search procedure. To the best of our knowledge, our proposal is the first application of DABC to the PFSP with the TFT criterion. The performances of the proposed algorithms were tested by using Taillard’s benchmark suite that is commonly used in the scheduling literature. The proposed algorithms were superior to the traditional IG_RS algorithm, and it has been shown that the performances of the DABC and hDDE algorithms are highly competitive with (if not better than) the best performing estimation distribution and genetic local search algorithms that have appeared recently in the existing literature. Ultimately, 44 out of the 90 best-known solutions provided recently by the EDA, tsGLS, and hGLS algorithms are further improved by the DABC and hDDE algorithms with short-term searches. With long-term searches, the new best-known solutions are reported for all problems in the benchmark suite of Taillard. For future research, DABC will be extended to solve other scheduling problems such as no-wait flowshop, no-idle flowshop, blocking flowshop, etc. in the existing literature.