IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v260y2017i3p964-971.html
   My bibliography  Save this article

An efficient bicriteria algorithm for stable robotic flow shop scheduling

Author

Listed:
  • Che, Ada
  • Kats, Vladimir
  • Levner, Eugene

Abstract

We consider a flow shop for processing single type of parts serviced by a single robot. The robot transportation times are allowed to have small perturbations. We treat the robotic flow shop scheduling problem considering stability of its schedule where the robot route is fixed and the processing durations of parts are to be specified from given intervals. The stability radius of a schedule is defined as the largest quantity of variations in the transportation times within which the schedule can still be executed as expected. We consider the bicriteria optimization problem which consists of minimizing the cycle time and maximizing the stability radius. The objective is to handle the two criteria simultaneously, that is, to find their Pareto front. We propose a new strongly polynomial algorithm for finding the minimum cycle times for all possible values of stability radius with time complexity of O(m4), where m is the number of processing machines in the flow shop. This implies that we can find the entire Pareto front of the problem in O(m4) time.

Suggested Citation

  • Che, Ada & Kats, Vladimir & Levner, Eugene, 2017. "An efficient bicriteria algorithm for stable robotic flow shop scheduling," European Journal of Operational Research, Elsevier, vol. 260(3), pages 964-971.
    • Handle: RePEc:eee:ejores:v:260:y:2017:i:3:p:964-971
    DOI: 10.1016/j.ejor.2017.01.033
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717300681
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.01.033?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. Che, Ada & Feng, Jianguang & Chen, Haoxun & Chu, Chengbin, 2015. "Robust optimization for the cyclic hoist scheduling problem," European Journal of Operational Research, Elsevier, vol. 240(3), pages 627-636.
    2. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    3. Kats, Vladimir & Levner, Eugene, 2011. "A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times," European Journal of Operational Research, Elsevier, vol. 209(1), pages 51-56, February.
    4. Herroelen, Willy & Leus, Roel, 2005. "Project scheduling under uncertainty: Survey and research potentials," European Journal of Operational Research, Elsevier, vol. 165(2), pages 289-306, September.
    5. Janny M. Y. Leung & Guoqing Zhang & Xiaoguang Yang & Raymond Mak & Kokin Lam, 2004. "Optimal Cyclic Multi-Hoist Scheduling: A Mixed Integer Programming Approach," Operations Research, INFORMS, vol. 52(6), pages 965-976, December.
    6. Y N Sotskov & A Allahverdi & T-C Lai, 2004. "Flowshop scheduling problem to minimize total completion time with random and bounded processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(3), pages 277-286, 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. De Santis, Marianna & Grani, Giorgio & Palagi, Laura, 2020. "Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming," European Journal of Operational Research, Elsevier, vol. 283(1), pages 57-69.
    2. Delorme, Xavier & Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y., 2019. "Minimizing the number of workers in a paced mixed-model assembly line," European Journal of Operational Research, Elsevier, vol. 272(1), pages 188-194.
    3. Fatemi-Anaraki, Soroush & Tavakkoli-Moghaddam, Reza & Foumani, Mehdi & Vahedi-Nouri, Behdin, 2023. "Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches," Omega, Elsevier, vol. 115(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. Xin Li & Richard Y. K. Fung, 2016. "Optimal K-unit cycle scheduling of two-cluster tools with residency constraints and general robot moving times," Journal of Scheduling, Springer, vol. 19(2), pages 165-176, April.
    2. Che, Ada & Feng, Jianguang & Chen, Haoxun & Chu, Chengbin, 2015. "Robust optimization for the cyclic hoist scheduling problem," European Journal of Operational Research, Elsevier, vol. 240(3), pages 627-636.
    3. Hanen, Claire & Hanzalek, Zdenek, 2020. "Grouping tasks to save energy in a cyclic scheduling problem: A complexity study," European Journal of Operational Research, Elsevier, vol. 284(2), pages 445-459.
    4. Xiong, Jian & Leus, Roel & Yang, Zhenyu & Abbass, Hussein A., 2016. "Evolutionary multi-objective resource allocation and scheduling in the Chinese navigation satellite system project," European Journal of Operational Research, Elsevier, vol. 251(2), pages 662-675.
    5. Servranckx, Tom & Vanhoucke, Mario, 2019. "Strategies for project scheduling with alternative subgraphs under uncertainty: similar and dissimilar sets of schedules," European Journal of Operational Research, Elsevier, vol. 279(1), pages 38-53.
    6. Morteza Davari & Erik Demeulemeester, 2019. "The proactive and reactive resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 22(2), pages 211-237, April.
    7. Lamas, Patricio & Goycoolea, Marcos & Pagnoncelli, Bernardo & Newman, Alexandra, 2024. "A target-time-windows technique for project scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 314(2), pages 792-806.
    8. Briand, Cyril & La, H. Trung & Erschler, Jacques, 2006. "A new sufficient condition of optimality for the two-machine flowshop problem," European Journal of Operational Research, Elsevier, vol. 169(3), pages 712-722, March.
    9. Antonio J. Conejo & Nicholas G. Hall & Daniel Zhuoyu Long & Runhao Zhang, 2021. "Robust Capacity Planning for Project Management," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1533-1550, October.
    10. Zhu, Xia & Ruiz, Rubén & Li, Shiyu & Li, Xiaoping, 2017. "An effective heuristic for project scheduling with resource availability cost," European Journal of Operational Research, Elsevier, vol. 257(3), pages 746-762.
    11. Maxim A. Maron, 2018. "Diagnostics of Projects," European Research Studies Journal, European Research Studies Journal, vol. 0(1), pages 18-30.
    12. Shi Chen & Hau Lee, 2017. "Incentive Alignment and Coordination of Project Supply Chains," Management Science, INFORMS, vol. 63(4), pages 1011-1025, April.
    13. Allahverdi, Ali, 2006. "Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times," International Journal of Production Economics, Elsevier, vol. 103(1), pages 386-400, September.
    14. Berghman, Lotte & Leus, Roel, 2015. "Practical solutions for a dock assignment problem with trailer transportation," European Journal of Operational Research, Elsevier, vol. 246(3), pages 787-799.
    15. Van de Vonder, Stijn & Demeulemeester, Erik & Herroelen, Willy, 2008. "Proactive heuristic procedures for robust project scheduling: An experimental analysis," European Journal of Operational Research, Elsevier, vol. 189(3), pages 723-733, September.
    16. Idir Hamaz & Laurent Houssin & Sonia Cafieri, 2018. "A robust basic cyclic scheduling problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(3), pages 291-313, September.
    17. Karakaya, Sırma & Balcik, Burcu, 2024. "Developing a national pandemic vaccination calendar under supply uncertainty," Omega, Elsevier, vol. 124(C).
    18. Yagub Alipouri & Mohammad Hassan Sebt & Abdollah Ardeshir & Mohammad Hossein Fazel Zarandi, 2020. "A mixed-integer linear programming model for solving fuzzy stochastic resource constrained project scheduling problem," Operational Research, Springer, vol. 20(1), pages 197-217, March.
    19. Indranil R. Bardhan & Vish V. Krishnan & Shu Lin, 2007. "Project Performance and the Enabling Role of Information Technology: An Exploratory Study on the Role of Alignment," Manufacturing & Service Operations Management, INFORMS, vol. 9(4), pages 579-595, May.
    20. Majid Askarifard & Hamidreza Abbasianjahromi & Mehran Sepehri & Ehsanollah Zeighami, 2021. "A robust multi-objective optimization model for project scheduling considering risk and sustainable development criteria," Environment, Development and Sustainability: A Multidisciplinary Approach to the Theory and Practice of Sustainable Development, Springer, vol. 23(8), pages 11494-11524, August.

    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:ejores:v:260:y:2017:i:3:p:964-971. 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/eor .

    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.