IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i21p4063-d959914.html
   My bibliography  Save this article

Equilibrium Optimizer and Slime Mould Algorithm with Variable Neighborhood Search for Job Shop Scheduling Problem

Author

Listed:
  • Yuanfei Wei

    (Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, Bangi 43600, Selangor, Malaysia
    Xiangsihu College, Guangxi University for Nationalities, Nanning 530225, China)

  • Zalinda Othman

    (Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, Bangi 43600, Selangor, Malaysia)

  • Kauthar Mohd Daud

    (Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, Bangi 43600, Selangor, Malaysia)

  • Shihong Yin

    (College of Artificial Intelligence, Guangxi University for Nationalities, Nanning 530006, China
    Guangxi Key Laboratories of Hybrid Computation and IC Design Analysis, Nanning 530006, China)

  • Qifang Luo

    (Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, Bangi 43600, Selangor, Malaysia
    Xiangsihu College, Guangxi University for Nationalities, Nanning 530225, China)

  • Yongquan Zhou

    (Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, Bangi 43600, Selangor, Malaysia
    Xiangsihu College, Guangxi University for Nationalities, Nanning 530225, China)

Abstract

Job Shop Scheduling Problem (JSSP) is a well-known NP-hard combinatorial optimization problem. In recent years, many scholars have proposed various metaheuristic algorithms to solve JSSP, playing an important role in solving small-scale JSSP. However, when the size of the problem increases, the algorithms usually take too much time to converge. In this paper, we propose a hybrid algorithm, namely EOSMA, which mixes the update strategy of Equilibrium Optimizer (EO) into Slime Mould Algorithm (SMA), adding Centroid Opposition-based Computation (COBC) in some iterations. The hybridization of EO with SMA makes a better balance between exploration and exploitation. The addition of COBC strengthens the exploration and exploitation, increases the diversity of the population, improves the convergence speed and convergence accuracy, and avoids falling into local optimum. In order to solve discrete problems efficiently, a Sort-Order-Index (SOI)-based coding method is proposed. In order to solve JSSP more efficiently, a neighbor search strategy based on a two-point exchange is added to the iterative process of EOSMA to improve the exploitation capability of EOSMA to solve JSSP. Then, it is utilized to solve 82 JSSP benchmark instances; its performance is evaluated compared to that of EO, Marine Predators Algorithm (MPA), Aquila Optimizer (AO), Bald Eagle Search (BES), and SMA. The experimental results and statistical analysis show that the proposed EOSMA outperforms other competing algorithms.

Suggested Citation

  • Yuanfei Wei & Zalinda Othman & Kauthar Mohd Daud & Shihong Yin & Qifang Luo & Yongquan Zhou, 2022. "Equilibrium Optimizer and Slime Mould Algorithm with Variable Neighborhood Search for Job Shop Scheduling Problem," Mathematics, MDPI, vol. 10(21), pages 1-20, November.
  • Handle: RePEc:gam:jmathe:v:10:y:2022:i:21:p:4063-:d:959914
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/21/4063/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/10/21/4063/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Kanhua Yu & Lili Liu & Zhe Chen, 2021. "An Improved Slime Mould Algorithm for Demand Estimation of Urban Water Resources," Mathematics, MDPI, vol. 9(12), pages 1-26, June.
    2. Liu, Yun & Heidari, Ali Asghar & Ye, Xiaojia & Liang, Guoxi & Chen, Huiling & He, Caitou, 2021. "Boosting slime mould algorithm for parameter identification of photovoltaic models," Energy, Elsevier, vol. 234(C).
    3. Thi-Kien Dao & Tien-Szu Pan & Trong-The Nguyen & Jeng-Shyang Pan, 2018. "Parallel bat algorithm for optimizing makespan in job shop scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 29(2), pages 451-462, February.
    4. Robert H. Storer & S. David Wu & Renzo Vaccari, 1992. "New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling," Management Science, INFORMS, vol. 38(10), pages 1495-1509, October.
    5. Jing Zhang & Wanliang Wang & Xinli Xu, 2017. "A hybrid discrete particle swarm optimization for dual-resource constrained job shop scheduling with resource flexibility," Journal of Intelligent Manufacturing, Springer, vol. 28(8), pages 1961-1972, December.
    6. 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.
    7. Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    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. 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.

    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. Ganesan, Viswanath Kumar & Sivakumar, Appa Iyer, 2006. "Scheduling in static jobshops for minimizing mean flowtime subject to minimum total deviation of job completion times," International Journal of Production Economics, Elsevier, vol. 103(2), pages 633-647, October.
    2. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    3. 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.
    4. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    5. T. C. E. Cheng & Bo Peng & Zhipeng Lü, 2016. "A hybrid evolutionary algorithm to solve the job shop scheduling problem," Annals of Operations Research, Springer, vol. 242(2), pages 223-237, July.
    6. 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.
    7. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    8. Ramalhinho Lourenco, Helena, 1996. "Sevast'yanov's algorithm for the flow-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 91(1), pages 176-189, May.
    9. Bierwirth, C. & Kuhpfahl, J., 2017. "Extended GRASP for the job shop scheduling problem with total weighted tardiness objective," European Journal of Operational Research, Elsevier, vol. 261(3), pages 835-848.
    10. Steinhofel, K. & Albrecht, A. & Wong, C. K., 1999. "Two simulated annealing-based heuristics for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 118(3), pages 524-548, November.
    11. Edzard Weber & Anselm Tiefenbacher & Norbert Gronau, 2019. "Need for Standardization and Systematization of Test Data for Job-Shop Scheduling," Data, MDPI, vol. 4(1), pages 1-21, February.
    12. Mattfeld, Dirk C. & Bierwirth, Christian, 2004. "An efficient genetic algorithm for job shop scheduling with tardiness objectives," European Journal of Operational Research, Elsevier, vol. 155(3), pages 616-630, June.
    13. Slim Abid & Ali M. El-Rifaie & Mostafa Elshahed & Ahmed R. Ginidi & Abdullah M. Shaheen & Ghareeb Moustafa & Mohamed A. Tolba, 2023. "Development of Slime Mold Optimizer with Application for Tuning Cascaded PD-PI Controller to Enhance Frequency Stability in Power Systems," Mathematics, MDPI, vol. 11(8), pages 1-32, April.
    14. 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.
    15. Diarmuid Grimes & Emmanuel Hebrard, 2015. "Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 268-284, May.
    16. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    17. G I Zobolas & C D Tarantilis & G Ioannou, 2009. "A hybrid evolutionary algorithm for the job shop scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(2), pages 221-235, February.
    18. Guinet, Alain & Legrand, Marie, 1998. "Reduction of job-shop problems to flow-shop problems with precedence constraints," European Journal of Operational Research, Elsevier, vol. 109(1), pages 96-110, August.
    19. Ricardo Pérez-Rodríguez, 2024. "A Radial Memetic Algorithm to Resolve the No-Wait Job-Shop Scheduling Problem," Mathematics, MDPI, vol. 12(21), pages 1-15, October.
    20. Andrzej Bożek, 2020. "Energy Cost-Efficient Task Positioning in Manufacturing Systems," Energies, MDPI, vol. 13(19), pages 1-21, September.

    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:gam:jmathe:v:10:y:2022:i:21:p:4063-:d:959914. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.