الگوریتم گسسته ی مصنوعی کلنی زنبور عسل با استراتژی های جهش کامپوزیت برای جایگشت مسئله زمانبندی گردش فروشگاه

The Permutation Flow Shop Scheduling Problem (PFSSP) is an NP-hard problem of wide engineering and theoretical background. In this paper, a kind of discrete artificial bee colony with composite mutation strategies is presented to compensate the defects of the single mutation scheme that is easy to get into the local best for PFSSP, named CDABC. Firstly, to make ABC suitable for PFSSP, we regard each discrete job permutation as a food source and apply discrete operations to generate a new neighbourhood food source for different bees. Secondly, the Nawaz-Enscore-Ham (NEH) heuristic is combined with the random initialization to initialize the population with a certain quality and diversity. Thirdly, the composite mutation strategies are proposed to enable the DABC to solve the permutation flow shop scheduling. Finally, the fast local search is used for enhancing the best individual. Within our knowledge, there are few papers to discuss artificial bee colony algorithm about PFSSP with the objective of minimizing total flow time and maximum lateness of jobs. In this sense, our work can be viewed as a start point for researchers to develop ABC-based algorithms to solve PFSSP. Additionally, simulations and comparisons based on PFSSP benchmarks are carried out, which shows that our algorithm is very competitive. We have also evaluated our algorithm with the well known DMU problems. For the problems with the objective of minimizing makespan, the algorithm CDABC obtains 26 new upper bounds of the 40 instances, and for the problems with the objective of maximum lateness, CDABC obtains 137 new upper bounds of the 160 instances. These new upper bounds can be used for future algorithms to compare their results with ours.

Scheduling problems are taking the very essential effect in both manufacturing systems and industrial process for improving the utilization efficiency of resources; therefore, it plays a central role in developing efficient scheduling technologies [1]. The Permutation flow shop problem (PFSSP), one of the important problems in actual production of manufacturing system, can be viewed as a simplified version of the flow shop problem, and has been proved to be non-deterministic-polynomial-time (NP)-hard [2] and [3]. Due to its significance in both academic and engineering applications, the permutation flow shop with the criterion of minimizing the makespan, maximum lateness of jobs, or total flow time, a great diversity of methods have been proposed to solve PFSSP and obtained some achievements. Many methods have been introduced for solving PFSSP with the objective of minimizing the makespan, total flow time or maximum lateness of the jobs since the pioneering work of Johnson [4] on the two machine permutation flow shop problem. However, due to unacceptable computation time, exact algorithms such as branch and bound method [5], [6], [7] and [8] and mixed integer linear programming method [9] cannot be applied to the middle and large-scale problems with acceptable time. Heuristic algorithms based on the constructive operation were then proposed to solve the large-sized scheduling problems. This kind of algorithms can be broadly classified into three categories: constructive heuristic algorithms, improvement heuristic algorithms and hybrid heuristic algorithms [10], [11], [12] and [13]. The constructive heuristics are mainly simple heuristics that build a feasible scheduling from scratch as it is seen in [14], [15], [16], [17] and [18]. Among them, The NEH heuristic is one of the most successful constructive heuristics and can provide comparable results with meta-heuristics. Constructive heuristics usually can obtain a nearly optimal solution in a reasonable computational time, while the solution qualities are not satisfactory. The improvement heuristics are mainly meta-heuristics that start from the previous generated solutions and subsequently approach the optimal solution by improving the solutions with domain dependent knowledge. The meta-heuristics mainly include Simulated Annealing algorithm (SA) [19] and [20], Genetic Algorithm (GA) [21], [22] and [23], Particle Swarm Optimization algorithm (PSO) [24] and [25], ant colony algorithm (ACO) [26], tabu search algorithm [27], [28], [29] and [30], Iterated Local Search algorithm (ILS) [31], and Estimation of Distribution Algorithm (EDA) [32]. Improvement heuristics usually can obtain fairly satisfactory solutions, while the solution processes are always time-consuming and vary dramatically according to their structure and parameters. Rather recently, it has become evident that the concentration on a sole meta-heuristic has some limitations. Researchers have found that a skilled combination of two or more meta-heuristic techniques, as called hybrid heuristics, can improve the performance especially when dealing with real-world and large-scale problems. Many hybrid heuristic-based algorithms have been investigated in the past few years. In [33], a hybrid SA algorithm was introduced combining the operators of GA with local searches. In [34], the genetic algorithm is integrated into a novel local search scheme resulting into two hybrid algorithms: the insertion search and the insertion search with cut-and-repair (ISCR). In [35], two effective heuristics are used during the local search to improve all generated chromosomes in every generation. In [36], Wang and Zheng used the well-known Nawaz–Enscore–Ham (NEH) combined with GA to generate the initial population, and applied multi-crossover operators to enhance the exploring potential. In [37] Murata et al. proposed a hybrid genetic algorithm with local search. In [38], a probabilistic hybrid heuristic that combined NEH with SA was proposed for solving PFSSP. In [24], Tasgetiren et al. applied the PSO algorithm to solve PFSSP by using a small position value rule, and the proposed algorithm, as called PSOVNS, was combined with the variable neighborhood-based local search algorithm. Liu and Wang, in [10], proposed an efficient particle swarm optimization-based Mimetic Algorithm (MA) for PFSSP to minimize the maximum completion time. In this algorithm, the PSO-based searching operators and some special local search operators are used to balance the exploration and exploitation abilities. In [26], an ant-colony-based algorithm was proposed to solve PFSSP, combining the fast local search to enhance the solutions. In [39], a hybrid algorithm that combined (Framinan–Leisten) FL heuristic with iterated local search algorithm is proposed. Bassem and Eddaly applied the EDA algorithm to solve PFSSP by using a small position value rule, and the new algorithm, as called EDAVNS, was combined with the variable neighborhood search algorithm as an improvement procedure after creating a new offspring [32]. Zhang et al. [40] proposed an Improved PSO algorithm (IPSO) based on the “alldifferent” constraint to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operator is used to search its neighborhood. Kuo et al. [41] proposed a new hybrid particle swarm optimization model named HPSO that combines Random-Key (RK) encoding scheme, Individual Enhancement (IE) scheme, and particle swarm optimization to minimize makespan. By the RK encoding scheme, this strategy can exploit the global search ability of PSO thoroughly and by the IE scheme, it can enhance the local search ability of particles. Zhang and Sun [42] proposed an alternative two-phase particle swarm optimization called ATPPSO to solve the flow shop scheduling problem with the objective of minimizing makespan. It includes two processes: the attractive process and the repulsive process, which are executed alternatively. In order to refrain from the shortcoming of premature convergence, a two-point reversal crossover operator is defined, and in the repulsive process, each particle is made to fly towards some promising areas which can introduce some new information to guide the swarm searching process. A fast makespan computation method based on matrix is designed to improve the algorithm speed. Rregarding minimizing maximum lateness of permutation flow shop scheduling, within our knowledge, only few of researchers have used the minimizing maximum lateness as the performance measures of proposed algorithm. In [43], Tasgetiren et al. use the PSOV NS to find the optimal solution. This algorithm can find 156 out of 160 upper bounds where 155 of them were improved. In [44], Zheng and Yamashiro proposed a new quantum differential evolutionary algorithm; this algorithm based on the basic Quantum-Inspired Evolutionary algorithm (QEA) is encoded and decoded by using the quantum rotating angle and a simple strategy. This algorithm can find 157 out of 160 upper bounds where 156 of them were improved. From the literature, we can find that particle swarm optimization, genetic algorithm, ant colony algorithm, variable neighborhood search, and hybrid strategies based on them are the most popular for the PFSSP at present. Recently, an evolution technique, the artificial bee colony algorithm is a new population-based heuristic evolutionary algorithm that is simple to be implemented and has little or no parameters to be tuned [45]. This approach is inspired by the intelligent foraging behaviour of honeybee swarm. Up to now, most published works on ABC mainly have focused on solving the complex continuous optimization problem [46] and [47]. Within our knowledge, only few of researchers have used the ABC algorithm to solve the scheduling. In 2010, Pan et al. [48] proposed a discrete artificial bee colony to solve the lot-streaming flow shop scheduling with the criterion of total weighted earliness and tardiness penalties under both idling and no-idling cases. Therefore, this field of study is still in its early days, a large number of future researches are necessary in order to develop ABC-based algorithms for solving PFSSP other than only for those areas the inventors originally focused on. In this paper, we propose a discrete artificial bee colony with composite mutation strategies and fast local search for solving PFSSP. The crucial idea behind CDABC can be summarized as follows. Firstly, to make ABC suitable for solving PFSSP, we presented a food source as a discrete job permutation and applied the discrete operation to generate new neighborhood food source for three different bees. Secondly, the NEH heuristic was combined with the random initialization to initialize the population with certain quality and diversity. Thirdly, composite mutation strategies were presented to compensate the defects of the single mutation to get easily into the local best for PFSSP. Finally, multiple different neighborhoods was designed and incorporated as a local search scheme into the searching process to enrich the searching behaviors and to avoid premature convergence. Fast local search is proposed as a component of CDABC, for the sake of improving CDABC’s local search performance. The rest of this paper is organized as follows. In Sections 2 and 3, we will introduce PFSSP and ABC, respectively. In Section 4, the CDABC algorithm is proposed after presenting solution representations, initial population, employed bee colony, onlooker bee colony, scout bee colony, composite mutation schemes, and fast local search. The experimental results of the CDABC and comparisons to other previous algorithms are shown in Section 5. In the last section, we conclude this paper and point out some future work.

The permutation flow shop scheduling problem is important both in theoretical and engineering application fields. In this paper, we propose a discrete artificial bee colony-based hybrid algorithm, i.e. CDABC, to solve PFSSP. As we know, the original ABC algorithm is a continuous optimization algorithm; therefore, it cannot be used to solve PFSSP directly. We construct a direct relationship between the job sequence and the vector of individuals in ABC. In this way, the resulting discrete ABC algorithm can solve PFSSP problem, and what’s more, several heuristics and local search methods are incorporated into our algorithm. These methods help our algorithm to obtain a better initialization, better individuals during search, and a better global searching ability as well. Up to now, only few ABC algorithms can solve the scheduling problems. As to PFSSP, within our knowledge, our algorithm is the first one to solve this problem. In this sense, our algorithm may help other researchers focus on solving this problem, and what’s more, in order to evaluate the performance of the proposed CDABC algorithm, we compare CDABC with several state-of-the-art PFSSP algorithms with benchmark problems of PFSSP. Experimental results have shown that our algorithm can usually produce statically better results than other algorithms. Especially, for the DMU problems from Demirkol with the objective of minimizing makespan, the algorithm CDABC obtains 25 new upper bounds of the 40 instances and for the DMU problems with the objective of maximum lateness, CDABC obtains 137 new upper bounds of the 160 instances. These new results can be used for future research to provide new algorithms and to compare their results with our solutions. Moreover, our further work is to study the theoretical aspects as well as the performance of the technique. The other problem is to extend the algorithm to solve other combination problem such as job shop scheduling.