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: 
381158742@qq.com
Page: 
323-334
|
DOI: 
https://doi.org/10.3166/JESA.50.323-334
| |
Published: 
31 August 2017
| Citation

OPEN ACCESS

Abstract: 

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.

Keywords: 

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
  References

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. https://doi.org/10.1007/s00170-011-3525-x

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. https://doi.org/10.1080/09537287.2013.782846

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. https://doi.org/10.1016/j.ifacol.2015.06.348

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. https://doi.org/10.1016/j.ejor.2015.02.052

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. https://doi.org/10.1080/00207543.2014.994714

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. https://doi.org/10.1080/00207543.2012.752588

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. https://doi.org/10.1016/j.eswa.2010.12.043

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. https://doi.org/10.1504/IJPD.2010.029996

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. https://doi.org/10.1080/21681015.2016.1173599

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. https://doi.org/10.1016/j.ijpe.2010.08.017

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. https://doi.org/10.3926/jiem.1206

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. https://doi.org/10.1016/j.ijpe.2012.10.024

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 https://doi.org/10.1016/j.ijpe.2011.09.023

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. https://doi.org/10.1080/00207543.2015.1041575