ant colony optimization algorithm scheduling
67866847
An Improved Ant Colony Optimization Algorithm Based on Hybrid Strategies for Scheduling Problem
In this paper, an improved ant colony optimization(ICMPACO) algorithm based on the multi population strategy, co evolution mechanism, pheromone updating strategy, and pheromone diffusion mechanism is proposed to balance the convergence speed and solution diversity, and improve the optimization performance in solving the large scale optimization problem. In the proposed ICMPACO algorithm, the optimization problem is divided into several sub problems and the ants in the population are divided into elite ants and common ants in order to improve the convergence rate, and avoid to fall into the local optimum value. The pheromone updating strategy is used to improve optimization ability. The pheromone diffusion mechanism is used to make the pheromone released by ants at a certain point, which gradually affects a certain range of adjacent regions. The co evolution mechanism is used to interchange information among different sub populations in order to implement information sharing. In order to verify the optimization performance of the ICMPACO algorithm, the traveling salesmen problem (TSP) and the actual gate assignment problem are selected here. The experiment results show that the proposed ICMPACO algorithm can effectively obtain the best optimization value in solving TSP and effectively solve the gate assignment problem, obtain better assignment result, and it takes on better optimization ability and stability.
IEEE Access
Wu Deng Junjie Xu Huimin Zhao
213212334
FACO: a hybrid fuzzy ant colony optimization algorithm for virtual machine scheduling in high performance cloud computing
High performance cloud computing has recently become the focus of much interest. Extensive research has shown that scheduling and load balancing are among the key aspects of performance optimization. The allocation of a set of requests into a set of computing resources, which is considered as an NP hard problem, aims to distribute efficiently the load within the cloud architecture. To resolve this problem, the last decade has seen a growing trend towards using hybrid approaches to combine the advantages of different algorithms. In this paper, we propose a hybrid fuzzy ant colony optimization algorithm (FACO) for virtual machine scheduling to guarantee high efficiency in a cloud environment. The proposed fuzzy module evaluates historical information to calculate the pheromone value and select a suitable server while keeping an optimal computing time. The experimental work presented in this study provides one of the first investigations into how to choose the optimal parameters of ant colony optimization algorithms using the Taguchi experimental design. We have simulated the proposed algorithm through the Cloud Analyst and CloudSim simulators by applying different cloud configurations to evaluate the performance of the proposed algorithm. Our findings highlight how response time and processing time are improved compared to the Round Robin algorithm, Throttled algorithm and Equally Spread Current Execution Load algorithm, especially in the case of a high number of nodes. FACO algorithm could be applied to define efficient cloud architecture adapted to high performance applications.
J. Ambient Intell. Humaniz. Comput.
Awatif Ragmani Amina Elomri Noreddine Abghour Khalid Moussaid Mohammed Rida
70280017
An adaptive hybrid approach: Combining genetic algorithm and ant colony optimization for integrated process planning and scheduling
Abstract Optimization algorithms can differ in performance for a specific problem. Hybrid approaches, using this difference, might give a higher performance in many cases. This paper presents a hybrid approach of Genetic Algorithm (GA) and Ant Colony Optimization (ACO) specifically for the Integrated Process Planning and Scheduling (IPPS) problems. GA and ACO have given different performances in different cases of IPPS problems. In some cases, GA has outperformed, and so do ACO in other cases. This hybrid method can be constructed as (I) GA to improve ACO results or (II) ACO to improve GA results. Based on the performances of the algorithm pairs on the given problem scale. This proposed hybrid GA ACO approach (hAG) runs both GA and ACO simultaneously, and the better performing one is selected as the primary algorithm in the hybrid approach. hAG also avoids convergence by resetting parameters which cause algorithms to converge local optimum points. Moreover, the algorithm can obtain more accurate solutions with avoidance strategy. The new hybrid optimization technique (hAG) merges a GA with a local search strategy based on the interior point method. The efficiency of hAG is demonstrated by solving a constrained multi objective mathematical test case. The benchmarking results of the experimental studies with AIS (Artificial Immune System) GA, and ACO indicate that the proposed model has outperformed other non hybrid algorithms in different scenarios.
Mehmet Fatih Uslu Suleyman Uslu Faruk Bulut
204079550
Robust Scheduling of Hot Rolling Production by Local Search Enhanced Ant Colony Optimization Algorithm
Scheduling of a hot strip mill is an important decision problem in the steel manufacturing industry. Previous studies on the hot strip mill scheduling problem have mostly neglected the random factors in production. However, random variations in processing times are inevitable due to unpredictable delays and disturbances. In this article, we adopt a robust optimization approach to deal with the uncertainty in processing times. The advantage is that no assumption has to be made regarding the distribution of random data, and the obtained schedule will remain strictly feasible when the variations have not exceeded a predefined uncertainty set. First, a mixed integer linear programming model is presented to formulate the robust scheduling problem. Then, a hybrid metaheuristic algorithm, which combines ant colony system (ACS) and enhanced local search, is proposed to provide an efficient solution to the problem. Finally, extensive computational experiments involving both randomly generated and real world instances have been conducted to verify the effectiveness of the proposed algorithm. It is shown that the algorithm achieves optimality for small instances and outperforms two state of the art metaheuristics when used to solve large instances.
IEEE Transactions on Industrial Informatics
Rui Zhang Shiji Song Cheng Wu
214265190
Optimal design of adaptive power scheduling using modified ant colony optimization algorithm
For generating and distributing an economic load scheduling approach, artificial neural network (ANN) has been introduced, because power generation and power consumption are economically non identical. An efficient load scheduling method is suggested in this paper. Normally the power generation system fails due to its instability at peak load time. Traditionally, load shedding process is used in which low priority loads are disconnected from sources. The proposed method handles this problem by scheduling the load based on the power requirements. In many countries the power systems are facing limitations of energy. An efficient optimization algorithm is used to periodically schedule the load demand and the generation. Ant colony optimization (ACO) based ANN is used for this optimal load scheduling process. The present work analyse the technical economical and time dependent limitations. Also the works meets the demanded load with minimum cost of energy. Inorder to train ANN back propagation (BP) technics is used. A hybrid training process is described in this work. Global optimization algorithms are used to provide back propagation with good initial connection weights.
Vijo M Joy S M Krishnakumar
226314530
Task scheduling optimization strategy using improved ant colony optimization algorithm in cloud computing
In order to solve the problems of unbalanced load, slow convergence speed and low utilization of virtual machine resources existing in the previous task scheduling optimization strategies, this paper proposes a task scheduling optimization strategy using improved ant colony optimization algorithm in cloud computing. Firstly, based on the principle of cloud computing task scheduling, a scheduling model using improved ant colony algorithm is proposed to avoid the optimization strategy falling into local optimization. Then, task scheduling satisfaction function is constructed by combining the three objectives of the shortest waiting time, the degree of resource load balance and the cost of task completion to search the optimal solution of task scheduling. Finally, the reward and punishment coefficient is introduced to optimize the pheromone updating rules of ant colony algorithm, which speeds up the solution speed. Besides, we use dynamic update of volatility coefficient to optimize overall performance of this strategy, and introduce virtual machine load weight coefficient in the process of local pheromone updating, so as to ensure the load balance of virtual machine. The feasibility of our algorithm is analyzed and demonstrated by experiments with Cloudsim. The experimental results show that the proposed algorithm has the fastest convergence speed, the shortest completion time, the most balanced load and the highest utilization rate of virtual machine resources compared with other methods. Therefore, our proposed task scheduling optimization strategy has the best performance.
Xian Wei
225682569
A time sensitive network scheduling algorithm based on improved ant colony optimization
Abstract Cyber physical system (CPS) is the core technology of Industry 4.0. The deterministic behaviors of the CPS require real time deterministic guarantee. Therefore, this paper improves the ant colony optimization (ACO) into a scheduling algorithm for time triggered flows in time sensitive network (TSN) a standard developed by the IEEE 802.1 Working Group that fully satisfies the strict end to end delay requirements of industrial applications. Simulation results show that the improved ACO (IACO) can schedule the time triggered flows in the TSN excellently, and outperform the traditional ACO in convergence speed, optimization ability and the proneness to local optimum trap. To sum up, this paper provides an effective real time guarantee for the TSNs.
Jidong Chen Wei Ning Hao Yu Zhidong Wang Guanshi Pang
216441691
A Hybrid Ant Colony Optimization and Simulated Annealing Algorithm for Multi Objective Scheduling of Cellular Manufacturing Systems
During the last 2 decades, there have been many manufacturing companies in various industries that used the advantages of cellular manufacturing layouts. However, determining the best schedule for cellular layouts considering uncertain product demands is a big concern for scientists. In this research, a multi objective decision making model is proposed in the process of dynamic cellular production planning where the market demands are uncertain. In this regard, a non linear mixed integer programming model is developed. The complexity of the model is high to consider the model as NP hard. Therefore, a hybrid Ant colony Optimization and Simulated Annealing Algorithms are proposed to solve the problem. Then, the Taguchi method is used to estimate appropriate sets of parameters of the proposed algorithm. The results demonstrated that the proposed algorithm can generate the best part routes of products in terms of time, cost and load variance in a reasonable time. The algorithm is then used for a cellular production plant which is the producer of heavy vehicles parts.
Int. J. Appl. Metaheuristic Comput.
Aidin Delgoshaei Ahad Ali
59337002
Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities
Abstract We study the problem of scheduling on parallel batch processing machines with different capacities under a fuzzy environment to minimize the makespan. The jobs have non identical sizes and fuzzy processing times. After constructing a mathematical model of the problem, we propose a fuzzy ant colony optimization (FACO) algorithm. Based on the machine capacity constraint, two candidate job lists are adopted to select the jobs for building the batches. Moreover, based on the unoccupied space of the solution, heuristic information is designed for each candidate list to guide the ants. In addition, a fuzzy local optimization algorithm is incorporated to improve the solution quality. Finally, the proposed algorithm is compared with several state of the art algorithms through extensive simulated experiments and statistical tests. The comparative results indicate that the proposed algorithm can find better solutions within reasonable time than all the other compared algorithms.
Appl. Soft Comput.
Zhao-hong Jia Jianhai Yan Joseph Y -T Leung Kai Li Huaping Chen
221461538
An improved ant colony optimization job scheduling algorithm in fog computing
With the application of internet of things technology, fog computing has provided computing and storage services near the bottom network. It can solve the problem of rapid response and bandwidth consumption of delay sensitive applications at the edge of local network as a highly virtualized platform. However, in the case of large scale service requests, if the job scheduling problem cannot be effectively solved, it will increase service delay, reduce resource utilization and user satisfaction. In this paper, we have improved the basic ant colony optimization (ACO) and developed a new job scheduling strategy improved ant colony optimization named IACO. IACO can assign to the resource with the lowest total cost of all selected tasks, which is always determined by calculating the total cost value of the task on the resource. We have finished some experiments by imitating the foraging process of multiple ants and repeated it iteratively. The optimal task scheduling sequence can be obtained through the different pheromone concentration left by ants. Experimental results show that IACO scheduling algorithm is better than ACO in the total cost, completion time and economic cost.
Chao Yin Tongfang Li Xiaoping Qu Sihao Yuan