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

A new immune multi-agent system for the flexible job shop scheduling problem

Author

Listed:
  • Wei Xiong

    (University of Science and Technology Beijing
    North China University of Science and Technology)

  • Dongmei Fu

    (University of Science and Technology Beijing)

Abstract

Scheduling for the flexible job shop is very important and challenging in manufacturing field. Multi-agent-based approaches have been used to solve the flexible job shop scheduling problem (FJSP), in order to reduce complexity and cost, increase flexibility, and enhance robustness. However, the quality of solution obtained by the multi-agent approach is always worse than the centralized meta-heuristic algorithms. The immune system is a distributed and complicated information processing system, which can protect body from foreign antigens by immune responses. In this paper, we analyze the similarities between the FJSP and humoral immunity, which is one of the immune responses. Based on the similarities, we develop a new immune multi-agent scheduling system (NIMASS) to solve the FJSP with the objective of minimizing the maximal completion time (makespan). In order to acquire the higher-quality solution of the FJSP, we simulate humoral immunity to establish the architecture of NIMASS and the negotiation strategies of NIMASS, which are proposed for negotiation among agents. NIMASS was tested on different benchmark instances of the FJSP. In comparison with the multi-agent approaches and the centralized heuristic algorithms, the computational results indicate that NIMASS can effectively improve the quality of solution in very short time. And the computational time of NIMASS is superior to that of the centralized meta-heuristic algorithms, especially for the complex FJSPs. These results indicate that NIMASS can be very useful in applications that deal with real-time FJSPs.

Suggested Citation

  • 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.
  • Handle: RePEc:spr:joinma:v:29:y:2018:i:4:d:10.1007_s10845-015-1137-2
    DOI: 10.1007/s10845-015-1137-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10845-015-1137-2
    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-1137-2?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. 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.
    2. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, April.
    3. Egon Balas, 1969. "Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm," Operations Research, INFORMS, vol. 17(6), pages 941-957, December.
    4. Kacem, Imed & Hammadi, Slim & Borne, Pierre, 2002. "Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 60(3), pages 245-276.
    5. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    6. 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. Olumide Emmanuel Oluyisola & Swapnil Bhalla & Fabio Sgarbossa & Jan Ola Strandhagen, 2022. "Designing and developing smart production planning and control systems in the industry 4.0 era: a methodology and case study," Journal of Intelligent Manufacturing, Springer, vol. 33(1), pages 311-332, January.
    2. Tsegay Tesfay Mezgebe & Hind Bril El Haouzi & Guillaume Demesure & Remi Pannequin & Andre Thomas, 2020. "Multi-agent systems negotiation to deal with dynamic scheduling in disturbed industrial context," Journal of Intelligent Manufacturing, Springer, vol. 31(6), pages 1367-1382, August.
    3. 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.
    4. Anran Zhao & Peng Liu & Xiyu Gao & Guotai Huang & Xiuguang Yang & Yuan Ma & Zheyu Xie & Yunfeng Li, 2022. "Data-Mining-Based Real-Time Optimization of the Job Shop Scheduling Problem," Mathematics, MDPI, vol. 10(23), pages 1-30, December.
    5. Mohd. Shaaban Hussain & Mohammed Ali, 2019. "A Multi-agent Based Dynamic Scheduling of Flexible Manufacturing Systems," Global Journal of Flexible Systems Management, Springer;Global Institute of Flexible Systems Management, vol. 20(3), pages 267-290, September.
    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. Didden, Jeroen B.H.C. & Dang, Quang-Vinh & Adan, Ivo J.B.F., 2024. "Enhancing stability and robustness in online machine shop scheduling: A multi-agent system and negotiation-based approach for handling machine downtime in industry 4.0," European Journal of Operational Research, Elsevier, vol. 316(2), pages 569-583.
    8. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Julien Autuori & Faicel Hnaien & Farouk Yalaoui, 2016. "A mapping technique for better solution exploration: NSGA-II adaptation," Journal of Heuristics, Springer, vol. 22(1), pages 89-123, February.
    7. Wang, Sheng-yao & Wang, Ling & Liu, Min & Xu, Ye, 2013. "An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 145(1), pages 387-396.
    8. 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.
    9. 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.
    10. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    11. Dauzère-Pérès, Stéphane & Ding, Junwen & Shen, Liji & Tamssaouet, Karim, 2024. "The flexible job shop scheduling problem: A review," European Journal of Operational Research, Elsevier, vol. 314(2), pages 409-432.
    12. 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.
    13. Luscombe, Ruth & Kozan, Erhan, 2016. "Dynamic resource allocation to improve emergency department efficiency in real time," European Journal of Operational Research, Elsevier, vol. 255(2), pages 593-603.
    14. Chong Peng & Guanglin Wu & T Warren Liao & Hedong Wang, 2019. "Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem," PLOS ONE, Public Library of Science, vol. 14(9), pages 1-19, September.
    15. Selcuk Goren & Ihsan Sabuncuoglu & Utku Koc, 2012. "Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(1), pages 26-38, February.
    16. Valls, Vicente & Angeles Perez, M. & Sacramento Quintanilla, M., 1998. "A tabu search approach to machine scheduling," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 277-300, April.
    17. Hong-Sen Yan & Wen-Chao Li, 2017. "A multi-objective scheduling algorithm with self-evolutionary feature for job-shop-like knowledgeable manufacturing cell," Journal of Intelligent Manufacturing, Springer, vol. 28(2), pages 337-351, February.
    18. Yuri N. Sotskov, 2020. "Mixed Graph Colorings: A Historical Review," Mathematics, MDPI, vol. 8(3), pages 1-24, March.
    19. Jonas Harbering & Abhiram Ranade & Marie Schmidt & Oliver Sinnen, 2019. "Complexity, bounds and dynamic programming algorithms for single track train scheduling," Annals of Operations Research, Springer, vol. 273(1), pages 479-500, February.
    20. Abdelmaguid, Tamer F., 2015. "A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times," Applied Mathematics and Computation, Elsevier, vol. 260(C), pages 188-203.

    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:29:y:2018:i:4:d:10.1007_s10845-015-1137-2. 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.