IDEAS home Printed from https://ideas.repec.org/a/spr/joinma/v28y2017i6d10.1007_s10845-015-1060-6.html
   My bibliography  Save this article

An elitist quantum-inspired evolutionary algorithm for the flexible job-shop scheduling problem

Author

Listed:
  • Xiuli Wu

    (University of Science and Technology Beijing)

  • Shaomin Wu

    (University of Kent)

Abstract

The flexible job shop scheduling problem (FJSP) is vital to manufacturers especially in today’s constantly changing environment. It is a strongly NP-hard problem and therefore metaheuristics or heuristics are usually pursued to solve it. Most of the existing metaheuristics and heuristics, however, have low efficiency in convergence speed. To overcome this drawback, this paper develops an elitist quantum-inspired evolutionary algorithm. The algorithm aims to minimise the maximum completion time (makespan). It performs a global search with the quantum-inspired evolutionary algorithm and a local search with a method that is inspired by the motion mechanism of the electrons around atomic nucleuses. Three novel algorithms are proposed and their effect on the whole search is discussed. The elitist strategy is adopted to prevent the optimal solution from being destroyed during the evolutionary process. The results show that the proposed algorithm outperforms the best-known algorithms for FJSPs on most of the FJSP benchmarks.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joinma:v:28:y:2017:i:6:d:10.1007_s10845-015-1060-6
    DOI: 10.1007/s10845-015-1060-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10845-015-1060-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10845-015-1060-6?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. 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.
    2. Loukil, T. & Teghem, J. & Tuyttens, D., 2005. "Solving multi-objective production scheduling problems using metaheuristics," European Journal of Operational Research, Elsevier, vol. 161(1), pages 42-61, February.
    3. 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.
    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. Xiuli Wu & Junjian Peng & Xiao Xiao & Shaomin Wu, 2021. "An effective approach for the dual-resource flexible job shop scheduling problem considering loading and unloading," Journal of Intelligent Manufacturing, Springer, vol. 32(3), pages 707-728, March.
    2. Yingli Li & Jiahai Wang & Zhengwei Liu, 2022. "A simple two-agent system for multi-objective flexible job-shop scheduling," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 42-64, January.
    3. Gregory A. Kasapidis & Dimitris C. Paraskevopoulos & Panagiotis P. Repoussis & Christos D. Tarantilis, 2021. "Flexible Job Shop Scheduling Problems with Arbitrary Precedence Graphs," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4044-4068, November.
    4. 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.
    5. Xiuli Wu & Xianli Shen & Qi Cui, 2018. "Multi-Objective Flexible Flow Shop Scheduling Problem Considering Variable Processing Time due to Renewable Energy," Sustainability, MDPI, vol. 10(3), pages 1-30, March.
    6. Du, Mengyu & Li, Yan-Fu, 2020. "An investigation of new local search strategies in memetic algorithm for redundancy allocation in multi-state series-parallel systems," Reliability Engineering and System Safety, Elsevier, vol. 195(C).

    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. Loukil, Taicir & Teghem, Jacques & Fortemps, Philippe, 2007. "A multi-objective production scheduling case study solved by simulated annealing," European Journal of Operational Research, Elsevier, vol. 179(3), pages 709-722, June.
    2. 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.
    3. 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.
    4. 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.
    5. Shen, Liji & Buscher, Udo, 2012. "Solving the serial batching problem in job shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 14-26.
    6. 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.
    7. Balasubramanian, Hari & Fowler, John & Keha, Ahmet & Pfund, Michele, 2009. "Scheduling interfering job sets on parallel machines," European Journal of Operational Research, Elsevier, vol. 199(1), pages 55-67, November.
    8. 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.
    9. 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.
    10. Alvarez-Valdes, R. & Fuertes, A. & Tamarit, J. M. & Gimenez, G. & Ramos, R., 2005. "A heuristic to schedule flexible job-shop in a glass factory," European Journal of Operational Research, Elsevier, vol. 165(2), pages 525-534, September.
    11. Pham, Dinh-Nguyen & Klinkert, Andreas, 2008. "Surgical case scheduling as a generalized job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1011-1025, March.
    12. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    13. Rahman Torba & Stéphane Dauzère-Pérès & Claude Yugma & Cédric Gallais & Juliette Pouzet, 2024. "Solving a real-life multi-skill resource-constrained multi-project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 69-114, July.
    14. Tamssaouet, Karim & Dauzère-Pérès, Stéphane, 2023. "A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 311(2), pages 455-471.
    15. Geiger, Martin Josef, 2007. "On operators and search space topology in multi-objective flow shop scheduling," European Journal of Operational Research, Elsevier, vol. 181(1), pages 195-206, August.
    16. Gregory A. Kasapidis & Dimitris C. Paraskevopoulos & Panagiotis P. Repoussis & Christos D. Tarantilis, 2021. "Flexible Job Shop Scheduling Problems with Arbitrary Precedence Graphs," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4044-4068, November.
    17. 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.
    18. Shen, Liji & Dauzère-Pérès, Stéphane & Maecker, Söhnke, 2023. "Energy cost efficient scheduling in flexible job-shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 310(3), pages 992-1016.
    19. 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.
    20. Luo, Hao & Du, Bing & Huang, George Q. & Chen, Huaping & Li, Xiaolin, 2013. "Hybrid flow shop scheduling considering machine electricity consumption cost," International Journal of Production Economics, Elsevier, vol. 146(2), pages 423-439.

    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:spr:joinma:v:28:y:2017:i:6:d:10.1007_s10845-015-1060-6. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.