IDEAS home Printed from https://ideas.repec.org/a/spr/joinma/v34y2023i2d10.1007_s10845-021-01801-3.html
   My bibliography  Save this article

Scheduling of a class of partial routing FMS in uncertain environments with beam search

Author

Listed:
  • G. Cherif

    (Normandie Université)

  • E. Leclercq

    (Normandie Université)

  • D. Lefebvre

    (Normandie Université)

Abstract

In this paper, incremental computation of schedules for complex discrete event systems in an uncertain environment is studied. Uncertainties are assumed to occur due to uncontrollable events. A particular class of flexible manufacturing systems (FMSs) with partial precedence constraints is proposed where some operations are performed with total precedence constraints and others with full routing flexibility (namely partial routing FMSs). Interruptions may occur due to unavailability of resources and interruption of operations. Such interruptions may deviate the trajectory from the planed schedule. For the modeling of the partial routing FMS, a systematic multi-level formalism based on the hierarchical structuration of the operations is introduced. Then, the risk of deviation is integrated and a new cost function is defined accordingly. Finally, a modified beam search algorithm referred to as generation double filtered beam search algorithm that accelerates the convergence of the method is proposed. The new algorithm is based on a new filtering mechanism that uses the cost function to selectively explore the state space of Petri net model in order to find a control sequence from an initial state to a reference one with a trade-off between performance and robustness. Examples are used to illustrate the efficiency of the proposed scheduling approach.

Suggested Citation

  • G. Cherif & E. Leclercq & D. Lefebvre, 2023. "Scheduling of a class of partial routing FMS in uncertain environments with beam search," Journal of Intelligent Manufacturing, Springer, vol. 34(2), pages 493-514, February.
    • Handle: RePEc:spr:joinma:v:34:y:2023:i:2:d:10.1007_s10845-021-01801-3
    DOI: 10.1007/s10845-021-01801-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10845-021-01801-3
    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-021-01801-3?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. Sabuncuoglu, I. & Bayiz, M., 1999. "Job shop scheduling with beam search," European Journal of Operational Research, Elsevier, vol. 118(2), pages 390-412, October.
    2. Carlier, Jacques & Rebai, Ismail, 1996. "Two branch and bound algorithms for the permutation flow shop problem," European Journal of Operational Research, Elsevier, vol. 90(2), pages 238-251, April.
    3. S. Zhang & T. N. Wong, 2018. "Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 585-601, March.
    4. Wei Wang & Yingguang Li & Lingling Huang, 2018. "Rule and branch-and-bound algorithm based sequencing of machining features for process planning of complex parts," Journal of Intelligent Manufacturing, Springer, vol. 29(6), pages 1329-1336, August.
    5. Lei He & Mathijs Weerdt & Neil Yorke-Smith, 2020. "Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm," Journal of Intelligent Manufacturing, Springer, vol. 31(4), pages 1051-1078, April.
    6. 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.
    7. James T. Lin & Chun-Chih Chiu, 2018. "A hybrid particle swarm optimization with local search for stochastic resource allocation problem," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 481-495, March.
    8. Libin Han & Keyi Xing & Xiao Chen & Fuli Xiong, 2018. "A Petri net-based particle swarm optimization approach for scheduling deadlock-prone flexible manufacturing systems," Journal of Intelligent Manufacturing, Springer, vol. 29(5), pages 1083-1096, June.
    9. Dariush Khezrimotlagh & Yao Chen, 2018. "The Optimization Approach," International Series in Operations Research & Management Science, in: Decision Making and Performance Evaluation Using Data Envelopment Analysis, chapter 0, pages 107-134, Springer.
    10. Gmys, Jan & Mezmaz, Mohand & Melab, Nouredine & Tuyttens, Daniel, 2020. "A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 814-833.
    Full references (including those not matched with items on IDEAS)

    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. Libralesso, Luc & Focke, Pablo Andres & Secardin, Aurélien & Jost, Vincent, 2022. "Iterative beam search algorithms for the permutation flowshop," European Journal of Operational Research, Elsevier, vol. 301(1), pages 217-234.
    2. 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.
    3. Xinnian Wang & Keyi Xing & Chao-Bo Yan & Mengchu Zhou, 2019. "A Novel MOEA/D for Multiobjective Scheduling of Flexible Manufacturing Systems," Complexity, Hindawi, vol. 2019, pages 1-14, June.
    4. Wattana Viriyasitavat & Li Xu & Zhuming Bi & Assadaporn Sapsomboon, 2020. "Blockchain-based business process management (BPM) framework for service composition in industry 4.0," Journal of Intelligent Manufacturing, Springer, vol. 31(7), pages 1737-1748, October.
    5. Jiaxing Wang & Sibin Gao & Zhejun Tang & Dapeng Tan & Bin Cao & Jing Fan, 2023. "A context-aware recommendation system for improving manufacturing process modeling," Journal of Intelligent Manufacturing, Springer, vol. 34(3), pages 1347-1368, March.
    6. Olivier Ploton & Vincent T’kindt, 2023. "Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using Inclusion–Exclusion," Journal of Scheduling, Springer, vol. 26(2), pages 137-145, April.
    7. Cosmena Mahapatra & Ashish Payal & Meenu Chopra, 2020. "Swarm intelligence based centralized clustering: a novel solution," Journal of Intelligent Manufacturing, Springer, vol. 31(8), pages 1877-1888, December.
    8. Yiying Zhang & Aining Chi, 2023. "Group teaching optimization algorithm with information sharing for numerical optimization and engineering optimization," Journal of Intelligent Manufacturing, Springer, vol. 34(4), pages 1547-1571, April.
    9. Wang, Yongli & Wang, Yudong & Huang, Yujing & Yang, Jiale & Ma, Yuze & Yu, Haiyang & Zeng, Ming & Zhang, Fuwei & Zhang, Yanfu, 2019. "Operation optimization of regional integrated energy system based on the modeling of electricity-thermal-natural gas network," Applied Energy, Elsevier, vol. 251(C), pages 1-1.
    10. Yang, Lin & Pang, Shujiang & Wang, Xiaoyan & Du, Yi & Huang, Jieyu & Melching, Charles S., 2021. "Optimal allocation of best management practices based on receiving water capacity constraints," Agricultural Water Management, Elsevier, vol. 258(C).
    11. Wu, Jiansong & Zhang, Linlin & Bai, Yiping & Reniers, Genserik, 2022. "A safety investment optimization model for power grid enterprises based on System Dynamics and Bayesian network theory," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    12. Xu, Xiangdong & Qu, Kai & Chen, Anthony & Yang, Chao, 2021. "A new day-to-day dynamic network vulnerability analysis approach with Weibit-based route adjustment process," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 153(C).
    13. Wang, Yongli & Li, Jiapu & Wang, Shuo & Yang, Jiale & Qi, Chengyuan & Guo, Hongzhen & Liu, Ximei & Zhang, Hongqing, 2020. "Operational optimization of wastewater reuse integrated energy system," Energy, Elsevier, vol. 200(C).
    14. Changyu Zhou & Guohe Huang & Jiapei Chen, 2019. "A Type-2 Fuzzy Chance-Constrained Fractional Integrated Modeling Method for Energy System Management of Uncertainties and Risks," Energies, MDPI, vol. 12(13), pages 1-21, June.
    15. Hu, Lin & Hu, Xiaosong & Che, Yunhong & Feng, Fei & Lin, Xianke & Zhang, Zhiyong, 2020. "Reliable state of charge estimation of battery packs using fuzzy adaptive federated filtering," Applied Energy, Elsevier, vol. 262(C).
    16. Binzi Xu & Kai Xu & Baolin Fei & Dengchao Huang & Liang Tao & Yan Wang, 2024. "Automatic Design of Energy-Efficient Dispatching Rules for Multi-Objective Dynamic Flexible Job Shop Scheduling Based on Dual Feature Weight Sets," Mathematics, MDPI, vol. 12(10), pages 1-24, May.
    17. Hao, Ran & Lu, Tianguang & Ai, Qian & Wang, Zhe & Wang, Xiaolong, 2020. "Distributed online learning and dynamic robust standby dispatch for networked microgrids," Applied Energy, Elsevier, vol. 274(C).
    18. Yuhong Shuai & Liming Yao, 2021. "Adjustable Robust Optimization for Multi-Period Water Allocation in Droughts Under Uncertainty," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 35(12), pages 4043-4065, September.
    19. Yinhe Bu & Xingping Zhang, 2021. "On the Way to Integrate Increasing Shares of Variable Renewables in China: Experience from Flexibility Modification and Deep Peak Regulation Ancillary Service Market Based on MILP-UC Programming," Sustainability, MDPI, vol. 13(5), pages 1-22, February.
    20. Donovin D. Lewis & Aron Patrick & Evan S. Jones & Rosemary E. Alden & Abdullah Al Hadi & Malcolm D. McCulloch & Dan M. Ionel, 2023. "Decarbonization Analysis for Thermal Generation and Regionally Integrated Large-Scale Renewables Based on Minutely Optimal Dispatch with a Kentucky Case Study," Energies, MDPI, vol. 16(4), pages 1-23, February.

    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:34:y:2023:i:2:d:10.1007_s10845-021-01801-3. 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.