A Novel Differential Evolution Algorithm for TWET-NFSSP with SDSTs and RDs

Abstract:

A novel differential evolution (DE) algorithm, namely DE_TWET, is presented to deal with the no-wait flow-shop scheduling problem (NFSSP) with sequence-dependent setup times (SDSTs) and release dates (RDs). The criterion is to minimize a total weighted earliness/tardiness (TWET) cost function. The presented algorithm is a hybrid of DE, problem’s properties, and a special designed local search. In DE_TWET, DE is adopted to execute global search in the solution space, and the problem’s properties are utilized to give a speed-up evaluation method and construct the local search, and the special local search is designed to enhance the local search ability of DE. Experimental results and comparisons demonstrate the effectiveness and robustness of the presented algorithm.

• Periodical: Advanced Engineering Forum (Volumes 6-7)
• Pages: 748-756
• DOI: https://doi.org/10.4028/www.scientific.net/AEF.6-7.748
• Online since: September 2012
• Authors: Bin Qian, Hua Bing Zhou, Rong Hu, Li Ping Wu
• Keywords: Differential Evolution, No-Wait Flow-Shop Scheduling Problem, Sequence-Dependent Release Dates, Sequence-Dependent Setup Time, Special Local Search, Speed-up Method, Total Weighted Earliness/Tardiness

References

[1] W.H.M. Raaymakers, J.A. Hoogeveen, Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing, Eur. J. Oper. Res. 126(1) (2000) 131–151.

DOI: 10.1016/s0377-2217(99)00285-4

[2] F. Jin, S.J. Song, C. Wu, A simulated annealing algorithm for single machine scheduling problems with family setups, Comput. Oper. Res. 36(7) (2009) 2133-2138.

DOI: 10.1016/j.cor.2008.08.001

[3] M. Pinedo, Scheduling: Theory, Algorithms, and Systems, fourth ed., Springer, (2012).

[4] A. Allahverdi, C.T. Ng, T.C.E. Cheng, M.Y. Kovalyov, A survey of scheduling problems with setup times or costs, Eur. J. Oper. Res. 187(3) (2008) 985-1032.

DOI: 10.1016/j.ejor.2006.06.060

[5] R. Storn, K. Price, Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces, J. Glob. Optim. 11(4) (1997) 341–359.

[6] M.F. Tasgetiren, Y.C. Liang, M. Sevkli, G. Gencyilmaz, Differential evolution algorithm for permutation flowshop sequencing problem with makespan criterion, In Proceedings of 4th International Symposium on Intelligent Manufacturing Systems, Sakarya, Turkey, (2004).

DOI: 10.1016/j.ejor.2005.12.024

[7] G. Onwubolu, D. Davendra, Scheduling flow shops using differential evolution algorithm, Eur. J. Oper. Res. 171(2) (2006) 674–692.

DOI: 10.1016/j.ejor.2004.08.043

[8] B. Qian, L. Wang, R. Hu, D.X. Huang, X. Wang, A DE-based approach to no-wait flow-shop scheduling, Comput. Ind. Eng. 57(3) (2009) 787-805.

DOI: 10.1016/j.cie.2009.02.006

[9] L. Wang, Q.K. Pan, P.N. Suganthan, W.H. Wang, Y.M. Wang, A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems, Comput. Oper. Res. 37(3) (2010) 509-520.

DOI: 10.1016/j.cor.2008.12.004

[10] R. Hu, X.H. Meng, B. Qian, K. Li, A differential evolution approach for NTJ-NFSSP with SDSTs and RDs, Lecture Notes in Artificial Intelligence, 7390 (2012) 288-299.

DOI: 10.1007/978-3-642-31576-3_38

[11] B. Qian, L. Wang, R. Hu, W.L. Wang, D.X. Huang, X. Wang, A hybrid differential evolution for permutation flow-shop scheduling, Int. J. Adv. Manuf. Tech., 38(7-8) (2008) 757-777.

DOI: 10.1007/s00170-007-1115-8

[12] Information on http: /www. icsi. berkeley. edu/%7Estorn/code. html.

[13] R. Ruiz, T. Stützle, An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, Eur. J. Oper. Res. 187(3) (2008) 1143-1159.

DOI: 10.1016/j.ejor.2006.07.029