IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v174y2016icp93-110.html
   My bibliography  Save this article

An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem

Author

Listed:
  • Li, Xinyu
  • Gao, Liang

Abstract

Flexible job shop scheduling problem (FJSP) which is an extension of the classical job shop scheduling problem is a very important problem in the modern manufacturing system. It allows an operation to be processed by any machine from a given set. It has been proved to be a NP-hard problem. In this paper, an effective hybrid algorithm (HA) which hybridizes the genetic algorithm (GA) and tabu search (TS) has been proposed for the FJSP with the objective to minimize the makespan. The GA which has powerful global searching ability is utilized to perform exploration, and TS which has good local searching ability is applied to perform exploitation. Therefore, the proposed HA has very good searching ability and can balance the intensification and diversification very well. In order to solve the FJSP effectively, effective encoding method, genetic operators and neighborhood structure are used in this method. Six famous benchmark instances (including 201 open problems) of FJSP have been used to evaluate the performance of the proposed HA. Comparisons among proposed HA and other state-of-the-art reported algorithms are also provided to show the effectiveness and efficiency of proposed method. The computational time of proposed HA also has been compared with other algorithms. The experimental results demonstrate that the proposed HA has achieved significant improvement for solving FJSP regardless of the solution accuracy and the computational time. And, the proposed method obtains the new best solutions for several benchmark problems.

Suggested Citation

  • Li, Xinyu & Gao, Liang, 2016. "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 174(C), pages 93-110.
    • Handle: RePEc:eee:proeco:v:174:y:2016:i:c:p:93-110
    DOI: 10.1016/j.ijpe.2016.01.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527316000177
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2016.01.016?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Baykasoglu, Adil & ÖzbakIr, Lale, 2010. "Analyzing the effect of dispatching rules on the scheduling performance through grammar based flexible scheduling system," International Journal of Production Economics, Elsevier, vol. 124(2), pages 369-381, April.
    2. Seebacher, Gottfried & Winkler, Herwig, 2014. "Evaluating flexibility in discrete manufacturing based on performance and efficiency," International Journal of Production Economics, Elsevier, vol. 153(C), pages 340-351.
    3. Xiong, Jian & Xing, Li-ning & Chen, Ying-wu, 2013. "Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns," International Journal of Production Economics, Elsevier, vol. 141(1), pages 112-126.
    4. Huang, Rong-Hwa & Yang, Chang-Lin & Cheng, Wei-Che, 2013. "Flexible job shop scheduling with due window—a two-pheromone ant colony approach," International Journal of Production Economics, Elsevier, vol. 141(2), pages 685-697.
    5. Ho, Nhu Binh & Tay, Joc Cing & Lai, Edmund M.-K., 2007. "An effective architecture for learning and evolving flexible job-shop schedules," European Journal of Operational Research, Elsevier, vol. 179(2), pages 316-333, June.
    6. Stéphane Dauzère-Pérès & Jan Paulli, 1997. "An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search," Annals of Operations Research, Springer, vol. 70(0), pages 281-306, April.
    7. Wang, Xiuli & Cheng, T.C.E., 2015. "A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint," International Journal of Production Economics, Elsevier, vol. 161(C), pages 74-82.
    8. Torabi, S.A. & Karimi, B. & Fatemi Ghomi, S.M.T., 2005. "The common cycle economic lot scheduling in flexible job shops: The finite horizon case," International Journal of Production Economics, Elsevier, vol. 97(1), pages 52-65, July.
    9. Paulli, Jan, 1995. "A hierarchical approach for the FMS scheduling problem," European Journal of Operational Research, Elsevier, vol. 86(1), pages 32-42, October.
    10. De Giovanni, L. & Pezzella, F., 2010. "An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem," European Journal of Operational Research, Elsevier, vol. 200(2), pages 395-408, January.
    11. Liou, Cheng-Dar & Hsieh, Yi-Chih, 2015. "A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times," International Journal of Production Economics, Elsevier, vol. 170(PA), pages 258-267.
    12. Chiang, Tsung-Che & Lin, Hsiao-Jou, 2013. "A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling," International Journal of Production Economics, Elsevier, vol. 141(1), pages 87-98.
    13. Rossi, Andrea, 2014. "Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships," International Journal of Production Economics, Elsevier, vol. 153(C), pages 253-267.
    14. Moslehi, Ghasem & Mahnam, Mehdi, 2011. "A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search," International Journal of Production Economics, Elsevier, vol. 129(1), pages 14-22, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. YoungSu Yun & Anudari Chuluunsukh & Mitsuo Gen, 2020. "Sustainable Closed-Loop Supply Chain Design Problem: A Hybrid Genetic Algorithm Approach," Mathematics, MDPI, vol. 8(1), pages 1-19, January.
    2. Seyed Mahdi Homayouni & Dalila B. M. M. Fontes, 2021. "Production and transport scheduling in flexible job shop manufacturing systems," Journal of Global Optimization, Springer, vol. 79(2), pages 463-502, February.
    3. Lu Sun & Lin Lin & Haojie Li & Mitsuo Gen, 2019. "Cooperative Co-Evolution Algorithm with an MRF-Based Decomposition Strategy for Stochastic Flexible Job Shop Scheduling," Mathematics, MDPI, vol. 7(4), pages 1-20, March.
    4. Leilei Meng & Biao Zhang & Kaizhou Gao & Peng Duan, 2022. "An MILP Model for Energy-Conscious Flexible Job Shop Problem with Transportation and Sequence-Dependent Setup Times," Sustainability, MDPI, vol. 15(1), pages 1-14, December.
    5. Dung-Ying Lin & Tzu-Yun Huang, 2021. "A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem," Mathematics, MDPI, vol. 9(7), pages 1-20, April.
    6. Lunardi, Willian T. & Birgin, Ernesto G. & Ronconi, Débora P. & Voos, Holger, 2021. "Metaheuristics for the online printing shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 293(2), pages 419-441.
    7. Teeradech Laisupannawong & Boonyarit Intiyot & Chawalit Jeenanunta, 2021. "Mixed-Integer Linear Programming Model and Heuristic for Short-Term Scheduling of Pressing Process in Multi-Layer Printed Circuit Board Manufacturing," Mathematics, MDPI, vol. 9(6), pages 1-25, March.
    8. Ahmadi, Sobhan & Akgunduz, Ali, 2023. "Airport operations with electric-powered towing alternatives under stochastic conditions," Journal of Air Transport Management, Elsevier, vol. 109(C).
    9. Xianbo Xiang & Caoyang Yu & He Xu & Stuart X. Zhu, 2018. "Optimization of Heterogeneous Container Loading Problem with Adaptive Genetic Algorithm," Complexity, Hindawi, vol. 2018, pages 1-12, November.
    10. Xiaoqiu Shi & Wei Long & Yanyan Li & Dingshan Deng, 2020. "Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems," PLOS ONE, Public Library of Science, vol. 15(5), pages 1-23, May.
    11. Fei Luan & Zongyan Cai & Shuqiang Wu & Shi Qiang Liu & Yixin He, 2019. "Optimizing the Low-Carbon Flexible Job Shop Scheduling Problem with Discrete Whale Optimization Algorithm," Mathematics, MDPI, vol. 7(8), pages 1-17, August.
    12. Jian Zhang & Guofu Ding & Yisheng Zou & Shengfeng Qin & Jianlin Fu, 2019. "Review of job shop scheduling research and its new perspectives under Industry 4.0," Journal of Intelligent Manufacturing, Springer, vol. 30(4), pages 1809-1830, April.
    13. Ivan Lorencin & Nikola Anđelić & Vedran Mrzljak & Zlatan Car, 2019. "Genetic Algorithm Approach to Design of Multi-Layer Perceptron for Combined Cycle Power Plant Electrical Power Output Estimation," Energies, MDPI, vol. 12(22), pages 1-26, November.
    14. Qihao Liu & Xinyu Li & Liang Gao, 2021. "Mathematical modeling and a hybrid evolutionary algorithm for process planning," Journal of Intelligent Manufacturing, Springer, vol. 32(3), pages 781-797, March.
    15. Lihui Zhang & Riletu Ge & Jianxue Chai, 2019. "Prediction of China’s Energy Consumption Based on Robust Principal Component Analysis and PSO-LSSVM Optimized by the Tabu Search Algorithm," Energies, MDPI, vol. 12(1), pages 1-19, January.
    16. Hyun Cheol Lee & Chunghun Ha, 2019. "Sustainable Integrated Process Planning and Scheduling Optimization Using a Genetic Algorithm with an Integrated Chromosome Representation," Sustainability, MDPI, vol. 11(2), pages 1-23, January.
    17. An, Youjun & Chen, Xiaohui & Hu, Jiawen & Zhang, Lin & Li, Yinghe & Jiang, Junwei, 2022. "Joint optimization of preventive maintenance and production rescheduling with new machine insertion and processing speed selection," Reliability Engineering and System Safety, Elsevier, vol. 220(C).
    18. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R & M. Calle, 2020. "Scheduling a dual-resource flexible job shop with makespan and due date-related criteria," Annals of Operations Research, Springer, vol. 291(1), pages 5-35, August.
    19. Braune, Roland & Benda, Frank & Doerner, Karl F. & Hartl, Richard F., 2022. "A genetic programming learning approach to generate dispatching rules for flexible shop scheduling problems," International Journal of Production Economics, Elsevier, vol. 243(C).
    20. Xuan Jing & Xifan Yao & Min Liu & Jiajun Zhou, 2024. "Multi-agent reinforcement learning based on graph convolutional network for flexible job shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 35(1), pages 75-93, January.
    21. Mohamed Habib Zahmani & Baghdad Atmani, 2021. "Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation," Journal of Scheduling, Springer, vol. 24(2), pages 175-196, April.
    22. Alejandro Vital-Soto & Mohammed Fazle Baki & Ahmed Azab, 2023. "A multi-objective mathematical model and evolutionary algorithm for the dual-resource flexible job-shop scheduling problem with sequencing flexibility," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 626-668, September.
    23. Husam Suleiman, 2022. "A Cost-Aware Framework for QoS-Based and Energy-Efficient Scheduling in Cloud–Fog Computing," Future Internet, MDPI, vol. 14(11), pages 1-21, November.
    24. Fei Luan & Zongyan Cai & Shuqiang Wu & Tianhua Jiang & Fukang Li & Jia Yang, 2019. "Improved Whale Algorithm for Solving the Flexible Job Shop Scheduling Problem," Mathematics, MDPI, vol. 7(5), pages 1-14, April.
    25. Zhe Zhang & Xiaoling Song & Huijun Huang & Yong Yin & Benjamin Lev, 2022. "Scheduling problem in seru production system considering DeJong’s learning effect and job splitting," Annals of Operations Research, Springer, vol. 312(2), pages 1119-1141, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alper Türkyılmaz & Özlem Şenvar & İrem Ünal & Serol Bulkan, 2020. "A research survey: heuristic approaches for solving multi objective flexible job shop problems," Journal of Intelligent Manufacturing, Springer, vol. 31(8), pages 1949-1983, December.
    2. Nicolás Álvarez-Gil & Rafael Rosillo & David de la Fuente & Raúl Pino, 2021. "A discrete firefly algorithm for solving the flexible job-shop scheduling problem in a make-to-order manufacturing system," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(4), pages 1353-1374, December.
    3. Yiyi Xu & M’hammed Sahnoun & Fouad Ben Abdelaziz & David Baudry, 2022. "A simulated multi-objective model for flexible job shop transportation scheduling," Annals of Operations Research, Springer, vol. 311(2), pages 899-920, April.
    4. Vilcot, Geoffrey & Billaut, Jean-Charles, 2008. "A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 190(2), pages 398-411, October.
    5. Shen, Liji & Dauzère-Pérès, Stéphane & Neufeld, Janis S., 2018. "Solving the flexible job shop scheduling problem with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 265(2), pages 503-516.
    6. Zhang, Sicheng & Li, Xiang & Zhang, Bowen & Wang, Shouyang, 2020. "Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system," European Journal of Operational Research, Elsevier, vol. 283(2), pages 441-460.
    7. Kumar, V.N.S.A. & Kumar, V. & Brady, M. & Garza-Reyes, Jose Arturo & Simpson, M., 2017. "Resolving forward-reverse logistics multi-period model using evolutionary algorithms," International Journal of Production Economics, Elsevier, vol. 183(PB), pages 458-469.
    8. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R & M. Calle, 2020. "Scheduling a dual-resource flexible job shop with makespan and due date-related criteria," Annals of Operations Research, Springer, vol. 291(1), pages 5-35, August.
    9. Liang Tang & Zhihong Jin & Xuwei Qin & Ke Jing, 2019. "Supply chain scheduling in a collaborative manufacturing mode: model construction and algorithm design," Annals of Operations Research, Springer, vol. 275(2), pages 685-714, April.
    10. Guiliang Gong & Raymond Chiong & Qianwang Deng & Qiang Luo, 2020. "A memetic algorithm for multi-objective distributed production scheduling: minimizing the makespan and total energy consumption," Journal of Intelligent Manufacturing, Springer, vol. 31(6), pages 1443-1466, August.
    11. Po-Hsiang Lu & Muh-Cherng Wu & Hao Tan & Yong-Han Peng & Chen-Fu Chen, 2018. "A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 29(1), pages 19-34, January.
    12. Wei Xiong & Dongmei Fu, 2018. "A new immune multi-agent system for the flexible job shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 29(4), pages 857-873, April.
    13. Choo Jun Tan & Siew Chin Neoh & Chee Peng Lim & Samer Hanoun & Wai Peng Wong & Chu Kong Loo & Li Zhang & Saeid Nahavandi, 2019. "Application of an evolutionary algorithm-based ensemble model to job-shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 30(2), pages 879-890, February.
    14. Hao-Chin Chang & Tung-Kuan Liu, 2017. "Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms," Journal of Intelligent Manufacturing, Springer, vol. 28(8), pages 1973-1986, December.
    15. Xiuli Wu & Shaomin Wu, 2017. "An elitist quantum-inspired evolutionary algorithm for the flexible job-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 28(6), pages 1441-1457, August.
    16. Dauzere-Peres, S. & Roux, W. & Lasserre, J. B., 1998. "Multi-resource shop scheduling with resource flexibility," European Journal of Operational Research, Elsevier, vol. 107(2), pages 289-305, June.
    17. Li Zhou & Zhuoning Chen & Shaoping Chen, 2018. "An effective detailed operation scheduling in MES based on hybrid genetic algorithm," Journal of Intelligent Manufacturing, Springer, vol. 29(1), pages 135-153, January.
    18. Alejandro Vital-Soto & Mohammed Fazle Baki & Ahmed Azab, 2023. "A multi-objective mathematical model and evolutionary algorithm for the dual-resource flexible job-shop scheduling problem with sequencing flexibility," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 626-668, September.
    19. Miguel A. Fernández Pérez & Fernanda M. P. Raupp, 2016. "A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 409-416, April.
    20. Chiang, Tsung-Che & Lin, Hsiao-Jou, 2013. "A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling," International Journal of Production Economics, Elsevier, vol. 141(1), pages 87-98.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:proeco:v:174:y:2016:i:c:p:93-110. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.