Shortest route optimization of job-shop scheduling based on ant colony algorithm

Shortest route optimization of job-shop scheduling based on ant colony algorithm

Hui Wang

Finance Department, Ludong University, Yantai 264025, China

Corresponding Author Email:
| |
31 August 2017
| Citation



This paper aims to design the best and versatile solution to job-shop scheduling problem (JSP). For this purpose, the ant colonly algorithm (ACA) was integrated to the shortest route optimization of the JSP, and a strategy was developed to solve the shortest scheduling route with the improved ACA (IACA). The proposed strategy was verified through case analysis and simulation experiment. The results show that the ACA is suitable to optimize the scheduling route of real-world JSP. With the increase of the pheromone residual coefficient, the route length of the ACA first increased and then decreased. The IACA worked out a better solution than the genetic algorithm with fewer iterations. The IACA is more adaptable and versatile than the genetic algorithm in shortest route optimization, as well as the IACA’s relative advantage in the global optimization ability for JSP. The research findings shed new light on the optimization of dynamic JSP with multiple objectives.


Job-shop scheduling problem (JSP), shortest route optimization, ant colony algorithm (ACA), simulation, number of iterations

1. Introduction
2. Basic theories of the ACA and the improved ACA (IACA)
3. ACA-Based shortest route optimization of static JSP
4. IACA-Based shortest route optimization of dynamic JSP
5. Conclusion

Azzi A., Faccio M., Persona A., Sgarbossa F. (2012). Lot splitting scheduling procedure for makespan reduction and machine capacity increase in a hybrid flow shop with batch production. International Journal of Advanced Manufacturing Technology, Vol. 59, No. 5-8, pp. 775-786.

Calleja G., Pastor R. (2014). A dispatching algorithm for flexible job-shop scheduling with transfer batches: An industrial application. Production Planning & Control, Vol. 25, No. 2, pp. 93-109.

Fnaiech N., Fitouri C., Varnier C., Fnaiech F., Zerhouni N. (2015). A new heuristic method for solving joint job shop scheduling of production and maintenance. IfacPapersonline, Vol. 48, No. 3, pp. 1802-1808.

González M., Vela C., Varela R. (2015). Scatter search with path relinking for the flexible job shop scheduling problem. European Journal of Operational Research, Vol. 245, No. 1, pp. 35-45.

Hu R. S. (2015). A hybrid pso-ga algorithm for job shop scheduling in machine tool production. International Journal of Production Research, Vol. 53, No. 19, pp. 1-27.

Wang L., Wang S. Y., Liu M. (2013). A pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem. International Journal of Production Research, Vol. 51, No. 12, pp. 3574-3592.

Moradi E., Ghomi S. M. T. F., Zandieh M. (2011). Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem. Expert Systems with Applications, Vol. 38, No. 6, pp. 7169-7178.

Saravanan M., Haq A. N. (2010). A scatter search algorithm for scheduling optimisation of job shop problems. International Journal of Product Development, Vol. 10, No. 1-2, pp. 259-272.

Seidgar H., Zandieh M., Mahdavi I. (2016). Bi-objective optimization for integrating production and preventive maintenance scheduling in two-stage assembly flow shop problem. Journal of the Chinese Institute of Industrial Engineers, Vol. 33, No. 6, pp. 404-425.

Vinod V., Sridharan R. (2011). Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system. International Journal of Production Economics, Vol. 129, No. 1, pp. 127-146.

Zhai Y., Liu C., Chu W., Guo R., Liu C. (2014). A decomposition heuristics based on multi-bottleneck machines for large-scale job shop scheduling problems. Journal of Industrial Engineering & Management, Vol. 7, No. 5, pp. 1397-1414.

Zhang R., Chang P. C., Wu C. (2013). A hybrid genetic algorithm for the job shop scheduling problem with practical considerations for manufacturing costs: investigations motivated by vehicle production. International Journal of Production Economics, Vol. 145, No. 1, pp. 38-52.

Zhao C., Tang H. (2012). Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints. International Journal of Production Economics, Vol. 136, No. 1, pp. 131-136. Retrieved from

Zhao F., Shao Z., Wang J., Zhang C. (2016). A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problems. International Journal of Production Research, Vol. 54, No. 4, pp. 1-22.