A Hybrid Approach Based on Artificial Neural Network (ANN) and Differential Evolution (DE) for Job-Shop Scheduling Problem

Abstract:

In this paper, we proposed a new hybrid approach, combining ANN and DE(Differential Evolution), for job-shop scheduling. Job-shop scheduling can be decomposed into a constraint satisfactory part and an optimization part for a specified scheduling objective. For this, an NN and DE-based hybrid scheduling approach is proposed in this paper. First, several specific types of neuron are designed to describe these processing constraints, detecting whether constraints are satisfied and resolving the conflicts by their feedback adjustments. Constructed with these neurons, the constraint neural network (CNN) can generate a feasible solution for the JSSP. CNN here corresponds to the constraint satisfactory part. A gradient search algorithm can be applied to guide CNN operations if an optimal solution needs to be found at a fixed sequence. For sequence optimization, a DE is employed. Through many simulation experiments and practical applica¬tions, it is shown that the approach can be used to model real production scheduling problems and to efficiently find an optimal solution. The hybrid approach is an ideal combination of the constraint analysis and the optimization scheduling method.

• Periodical: Applied Mechanics and Materials (Volumes 26-28)
• Pages: 754-757
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.26-28.754
• Online since: June 2010
• Authors: Fu Qing Zhao, Jian Hua Zou, Ya Hong Yang
• Keywords: Artificial Neural Network (ANN), Constraint Neural Network, Differential Evolution (DE), Job Shop Scheduling

References

[1] Chen, A.L., Yang, G.K. 1 , Wu, Z.M. Production scheduling optimization algorithm for the hot rolling processes. International Journal of Production Research, 46(7): 1955-1973, (2008).

DOI: 10.1080/00207540600988048

[2] Kang, S.G., Choi, S.H. Multi-agent based beam search for intelligent production planning and scheduling, International Journal of Production Research 48(11): 3319-3353, (2010).

DOI: 10.1080/00207540902810502

[3] Nasseri, M., Asghari, K., Abedini, M.J. Optimized scenario for rainfall forecasting using genetic algorithm coupled with artificial neural network. Expert Systems with Applications, 35(3) : 1415-1421, (2008).

DOI: 10.1016/j.eswa.2007.08.033

[4] Yang, H., Shao, H. Distortion-oriented welding path optimization based on elastic net method and genetic algorithm. Journal of Materials Processing Technology, 209(9): 4407-4412, (2009).

DOI: 10.1016/j.jmatprotec.2008.11.019

[5] Atighehchian, Arezoo, Bijari, Mehdi, Tarkesh, Hamed. A novel hybrid algorithm for scheduling steel-making continuous casting production. Computers and Operations Research, 36(8): 2450-2461, (2009).

DOI: 10.1016/j.cor.2008.10.010

[6] Fonseca, Daniel J.; Navaresse, Daniel. Artificial neural networks for job shop simulation. Advanced Engineering Informatics. 2002, 16(4), 241-246.

DOI: 10.1016/s1474-0346(03)00005-3

[7] Raaymakers, W.H.M.; Weijters, A.J.M.M. Makespan estimation in batch process industries: A comparison between regression analysis and neural networks. European Journal of Operational Research , 2003, 145 (1): 14-30.

DOI: 10.1016/s0377-2217(02)00173-x

[8] Omran, Mahamed G.H., Engelbrecht, Andries P. 2 , Salman, Ayed3. Bare bones differential evolution. European Journal of Operational Research, 196(1): 128-139, (2008).

DOI: 10.1016/j.ejor.2008.02.035

[9] Ali, M.M. Differential evolution with preferential crossover. European Journal of Operational Research, 181(3): 1137-1147, (2007).

DOI: 10.1016/j.ejor.2005.06.077

[10] Kaelo, P., Ali, M.M. Differential evolution algorithms using hybrid mutation. Computational Optimization and Applications, 37(2): 231-246, (2007).

DOI: 10.1007/s10589-007-9014-3

[11] Wang, Yong-Jun, Zhang, Jiang-She, Zhang, Gai-Ying. A dynamic clustering based differential evolution algorithm for global optimization. European Journal of Operational Research, 183(1): 56-73, (2007).

DOI: 10.1016/j.ejor.2006.10.053

[12] Muth, & Thompson, G. L. (1963). Industrial scheduling, Englewood Cliffs, NJ: Prentice Hall.