یک الگوریتم کلونی مورچه هیبریدی جدید برای برنامه ریزی فلوشاپ بدون انتظار A new hybrid ant colony algorithm for scheduling of no-wait flowshop

1 Introduction The general assumption of majority of flow-shop applications is that the sequencing of the jobs relies on buffers, otherwise they are considered as intermediate storage between machines. The no-wait flow-shop scheduling problem (NWFSP) with makespan criterion is considered in this paper. In NWFSP, each job has to be processed from the first machine to the last without any interruption and the job sequence is unique on all machines. In addition, each machine can handle no more than one job at a time and each job has to visit each machine exactly once. Therefore, the start of a job on the first machine may be delayed in order to meet the no-wait requirement. Given that the release time of all jobs is zero and set-up time on each machine is included in the processing time, the no-wait flow-shop problem is to schedule jobs that minimize the makespan over all jobs. The no-wait flow shop scheduling problem has important applications in modern industry. It has an extensive background in industrial applications, including steel production, mining, logistics, chemical industry and food processing. For example, in steel factories, to avoid cooling and defects in steel, the liquid steel undergoes a chain of operations such as molding into ingots, unmolding, and soaking. Similarly, in the food processing, the canning operation must be operated after cooking operations immediately to ensure freshness (Hall and Sriskandarajah 1996). A comprehensive survey on the research and application of no-wait flow-shop scheduling problem can be found in Hall and Sriskandarayah’s review paper (Hall and Sriskandarajah 1996). In addition, Bagchi et al. (2006) showed that it can be transformed into the asymmetric traveling salesman problem (ATSP) and presented some no-wait and blocking scheduling models. In the operation research literature, many elegant mathematical models and methods have been developed to deal with the real-world problems. Some exact approaches have been proposed to unravel the problems optimally that have the limitation of solving only small-sized problems. On the other hand, heuristics which are based on polynomial time algorithms are the most suitable methods for solving large scheduling problems. In general, heuristics attain good solutions in a reasonable time interval. Additionally, in the recent years meta-heuristics with techniques such as bee colony algorithm (Khorramizadeh and Riahi 2015), genetic algorithm (GA) (Guo et al. 2005), memetic algorithm (MA) (Frutos and Tohme´ 2013), particle swarm optimization (PSO) (Marinakis et al. 2009), Electromagnetism-like Mechanism (SEM) (Bonyadi and Li 2010), and ant colony optimization (ACO) (Riahi and Kazemi 2015) have been developed to generate competitive results for many combinatorial optimization problems. In the recent years, several ant colony algorithms have developed for various kinds of problems including the scheduling problem. Kashan and Karimi (2008) proposed two ACO algorithms with two different visibility functions for total weighted tardiness single machine environment with formation of processing batches. To minimize total completion time in a no-wait two-machine flow-shop, Shyu et al. (2004) designed some specific features including a heuristic for initializing the initial pheromone, a hybrid state transition rule and a hybrid local search. Li et al. (2011) dealt with the minimization of the sum of completion time in a sequence-dependent setups permutational flowshop. The authors used a timelimited dynamic programming algorithm to perform a post-optimization strategy. Mirabi (2011) proposed an ant colony optimization technique for the sequencedependent flowshop scheduling problem.