An Improved Ant Colony Algorithm for the Dual Time Windows Constraining Job Shop Scheduling Problem
In this paper,we carry out research on a new Job Shop Scheduling problem in production scheduling applications,namely the Dual Time Windows Constraining Job Shop Scheduling problem(DTWJSP),which involves job machining time window constraints and equipment working time window constrains.We regard maximizing the job completion rate as the scheduling objective of DTWJSP and establish a dual time windows constraining job shop scheduling mathematical model,then make detail analysis on scheduling objective and solving complexity.Based on the characteristic and complexity of problem we propose an improved ant colony algorithm,in which we add new solutions using heuristic and stochastic methods except a conventional construction approach in each generation solutions produced by ant colony algorithm.Besides,a neighborhood search method is used to obtain local optimal solution and bi-directional convergence is used in the pheromone update step,this combination of methods effectively avoids local optima and improves the search efficiency.We compare the improved algorithm with classical ant colony algorithm using a variety of instances,the experimental results demonstrated that the improvement is effective and the improved algorithm is feasible and efficient.
Dual time windows job shop scheduling problem improved ant colony algorithm neighborhood search bi-directional convergence
Jungang Yan Zhongshan Zhang Lining Xing YingWu Chen
College of Information System and Management National University of Defense Technology changsha,Hunan,China
国际会议
重庆
英文
1519-1525
2017-03-25（万方平台首次上网日期，不代表论文的发表时间）