Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives

详细信息    查看全文

• 作者：K. Z. Gao ; P. N. Suganthan ; Q. K. Pan ; T. J. Chua…
• 关键词：Discrete harmony search ; Flexible job shop scheduling ; Local search ; Makespan ; Earliness ; Tardiness
• 刊名：Journal of Intelligent Manufacturing
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：27
• 期：2
• 页码：363-374
• 全文大小：1,023 KB
• 参考文献：Barnes, J. W., Chambers, J. B. (1996). Flexible job shop scheduling by tabu search. Graduate program in operations research and industrial engineering. The University of Texas at Austin; Technical Report Series: ORP96-09; http://​ww.​cs.​utexas.​edu/​users/​jbc/​ .
  Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157–183.CrossRef
  Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4), 369–375.CrossRef
  Dauzère-Pérès, S., & Paulli, J. (1997). An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research, 70(3), 281–306.CrossRef
  Demirkol, E., Mehta, S., & Uzsoy, R. (1998). Benchmark for shop scheduling problems. European Journal Operational Research, 109(1), 137–141.CrossRef
  Fattahi, P. (2009). A hybrid multi objective algorithm for flexible job shop scheduling. International Journal of Mathematical and Statistical Sciences, 1(1), 21–26.
  Gao, J., Sun, L., & Gen, M. (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers and Operations Research, 35(9), 2892–2907.CrossRef
  Gao, K. Z., Pan, Q. K., & Li, J. Q. (2011). Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion. International Journal of Advanced Manufacturing Technology, 56(5–8), 683–692.CrossRef
  Gao, K. Z., Pan, Q. K., Li, J. Q., et al. (2012). A hybrid harmony search algorithm for the no-wait flow shop scheduling problems. Asia-Pacific Journal of Operational Research, 29(2), 1250012.CrossRef
  Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flow hop and job shop scheduling. Mathematics of Operations Research, 1(2), 117–129.CrossRef
  Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm: Harmony search. Simulation, 76(2), 60–68.CrossRef
  Geem, Z. W. (2007). Optimal scheduling of multiple dam system using harmony search algorithm. LNCS, 4507, 316–323.
  Gen, M., & Cheng, R. (2000). Genetic algorithms & engineering optimization (pp. 1–30). NewYork: Wiley.
  Gholami, M., & Zandieh, M. (2009). Integrating simulation and genetic algorithm to scheduling a dynamic flexible job shop. Journal of Intelligent Manufacturing, 20(4), 481–498.CrossRef
  Jain, A. S., & Meeran, S. (1998). Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research, 113(2), 390–434.CrossRef
  Kacem, I., Hammadi, S., & Borne, P. (2002). Approach by localization and multi-objective evolutionary optimization for flexible job shop scheduling problems. IEEE Transaction on System, Man, and Cybernetics, Part C, 32(1), 1–13.CrossRef
  Lee, K. S., Geem, Z. W., Lee, S. H., & Bae, K. W. (2005). The harmony search heuristic algorithm for discrete structural optimization. Engineering Optimization, 37(7), 663–684.CrossRef
  Li, J., Pan, Q., & Liang, Y.-C. (2010). An effective hybrid tabu search algorithm for multi-objective flexible job shop scheduling problems. Computer & Industrial Engineering, 59(4), 647–662.CrossRef
  Li, J.-Q., Pan, Q.-K., Suganthan, P. N., & Chua, T. J. (2011a). A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 52(5–8), 683–697.
  Li, J.-Q., Pan, Q.-K., & Gao, K.-Z. (2011b). Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems. International Journal of Advanced Manufacturing Technology, 55(9–12), 1159–1169.CrossRef
  Liouane, N., Saad, I., Hammadi, S., & Borne, P. (2007). Ant systems & local search optimization for flexible job-shop scheduling production. International Journal of Computers, Communications & Control, 2(2), 174–184.CrossRef
  Mahdavi, M., Fesanghary, M., & Damangir, E. (2007). An improved harmony search algorithm for solving optimization problems. Applied Mathematics and Computation, 188(2), 1567–1579.CrossRef
  Mastrolilli, M., & Gambardella, L. M. (2000). Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling, 3(1), 3–20.CrossRef
  Omran, M. G. H., & Mahdavi, M. (2008). Global-best harmony search. Applied Mathematics and Computation, 198(2), 371–378.CrossRef
  Pan, Q. K., Suganthan, P. N., Liang, J. J., & Tasgetiren, M. F. (2011). A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem. Expert System with Application, 38(4), 3252–3259.CrossRef
  Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35(10), 3202–3212.CrossRef
  Pinedo, M. (2002). Scheduling theory, algorithms, and systems. Englewood Cliffs, NJ: Prentice-Hall.
  Scrich, C. R., Armentano, V. A., & Laguna, M. (2004). Tardiness minimization in a flexible job shop: A tabu search approach. Journal of Intelligent Manufacturing, 15(1), 103–115.CrossRef
  Vilcot, G., & Billaut, J.-C. (2011). A tabu search algorithm for solving a multi-criteria flexible job shop scheduling problem. International Journal of Production Research, 49(23), 6963–6980.CrossRef
  Wang, L., Pan, Q. K., & Tasgetiren, M. F. (2010). Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert System with Application, 37(12), 7929–7936.
  Wang, L., Zhou, G., Xu, Y., Wang, S., & Liu, M. (2012a). An effective artificial bee colony algorithm for the flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 60(1–4), 303–315.
  Wang, L., Zhou, G., Xu, Y., & Liu, M. (2012b). An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job shop scheduling. International Journal of Advanced Manufacturing Technology, 60(9–12), 1111–1123.CrossRef
  Wu, Z., & Weng, M. X. (2005). Multi-agent scheduling method with earliness and tardiness objectives in flexible job shops. IEEE Transactions on System, Man, and Cybernetics-Part B: Cybernetics, 35(2), 293–301.CrossRef
  Xia, W. J., & Wu, Z. M. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2), 409–425.CrossRef
  Xing, L. N., Chen, Y. W., & Yang, K. W. (2009a). An efficient search method for multi-objective flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 20(3), 283–293.CrossRef
  Xing, L. N., Chen, Y. W., & Yang, K. W. (2009b). Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling. Applied Soft Computing, 9(1), 362–376.CrossRef
  Yadav, P., Kumar, R., Panda, S. K., & Chang, C. S. (2011). An improved harmony search algorithm for optimal scheduling of the diesel generators in oil rig platforms. Energy Conversion Management, 52(2), 893–902.CrossRef
  Zhang, C. Y., Li, P. G., Guan, Z. L., & Rao, Y. Q. (2007). A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 34(11), 3229–3242.CrossRef
  Zhang, G. H., Shao, X. Y., Li, P. G., & Gao, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 56(4), 1309–1318.CrossRef
  Zhang, G., Gao, L., & Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert System with Application, 38(4), 3563–3573.CrossRef
  
• 作者单位：K. Z. Gao (1) (2)
  P. N. Suganthan (1)
  Q. K. Pan (3)
  T. J. Chua (4)
  T. X. Cai (4)
  C. S. Chong (4)
  
  1. School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore , 639798, Singapore
  2. School of Computer, Liaocheng University, Liaocheng , 252000, People’s Republic of China
  3. State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang , 110819, People’s Republic of China
  4. Singapore Institute of Manufacturing Technology, Nanyang Drive, Singapore , 638075, Singapore
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Production and Logistics
  Manufacturing, Machines and Tools
  Automation and Robotics
  
• 出版者：Springer Netherlands
• ISSN：1572-8145

文摘

Flexible job-shop scheduling problem (FJSP) is a practically useful extension of the classical job shop scheduling problem. This paper proposes an effective discrete harmony search (DHS) algorithm to solve FJSP. The objectives are the weighted combination of two minimization criteria namely, the maximum of the completion time (Makespan) and the mean of earliness and tardiness. Firstly, we develop a new method for the initial machine assignment task. Some existing heuristics are also employed for initializing the harmony memory with discrete machine permutation for machine assignment and job permutation for operation sequencing. Secondly, we develop a new rule for the improvisation to produce a new harmony for FJSP incorporating machine assignment and operation sequencing. Thirdly, several local search methods are embedded to enhance the algorithm’s local exploitation ability. Finally, extensive computational experiments are carried out using well-known benchmark instances. Computational results and comparisons show the efficiency and effectiveness of the proposed DHS algorithm for solving the FJSP with weighted combination of two objectives.