IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v43y2014icp96-107.html
   My bibliography  Save this article

A combined robot selection and scheduling problem for flow-shops with no-wait restrictions

Author

Listed:
  • Shabtay, Dvir
  • Arviv, Kfir
  • Stern, Helman
  • Edan, Yael

Abstract

This paper addresses a bicriteria no-wait flow-shop scheduling problem with multiple robots transferring jobs between pairs of consecutive machines. The robots share an identical track positioned alongside the machine transfer line. Each robot is assigned to a portion of the tract from which it performs job transfers between all reachable machines. We assume that job processing times are both machine and job independent, that jobs are not allowed to wait between two consecutive machines and that machine idle times are not allowed. We define a combined robot selection and scheduling problem (RSSP) for a set of Q non-identical robots characterized by different costs and job transfer and empty movement times. A solution to the RSSP problem is defined by (i) selecting a set of robots, (ii) assigning each robot to a portion of the track, and (iii) scheduling the robot moves. We define a robot schedule as feasible if all the jobs satisfy the no-wait condition and there are no machine idle times. The quality of the solutions are measured by two criteria (performance measures): makespan and robot selection cost. We study four different variations of the RSSP,one which is shown to be solvable in polynomial time while the other three turn out to be NP-hard. For the NP-hard, we show that a pseudo-polynomial time algorithm and a fully polynomial approximation scheme exists, and derive three important special cases which are solvable in polynomial time. The RSSP has aspects of robot selection, machine-robot assignment and robot movement scheduling. We believe this is the first time that this type of problem has been treated in the literature, and addresses a very important problem in multiple robotic systems operation. Our contribution lies in the formulation, methodology, algorithms for solution and complexity results which jointly treats all aspects of the problem simultaneously without the need to defer to heuristic decomposition methods.

Suggested Citation

  • Shabtay, Dvir & Arviv, Kfir & Stern, Helman & Edan, Yael, 2014. "A combined robot selection and scheduling problem for flow-shops with no-wait restrictions," Omega, Elsevier, vol. 43(C), pages 96-107.
    • Handle: RePEc:eee:jomega:v:43:y:2014:i:c:p:96-107
    DOI: 10.1016/j.omega.2013.07.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048313000698
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2013.07.001?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. Kalczynski, Pawel Jan & Kamburowski, Jerzy, 2007. "On no-wait and no-idle flow shops with makespan criterion," European Journal of Operational Research, Elsevier, vol. 178(3), pages 677-685, May.
    2. Nicholas G. Hall & Chelliah Sriskandarajah, 1996. "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process," Operations Research, INFORMS, vol. 44(3), pages 510-525, June.
    3. Vladimir Kats & Eugene Levner, 1997. "Minimizing the number of robots to meet a given cyclic schedule," Annals of Operations Research, Springer, vol. 69(0), pages 209-226, January.
    4. Che, Ada & Chu, Chengbin, 2009. "Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots," European Journal of Operational Research, Elsevier, vol. 199(1), pages 77-88, November.
    5. Agnetis, A., 2000. "Scheduling no-wait robotic cells with two and three machines," European Journal of Operational Research, Elsevier, vol. 123(2), pages 303-314, June.
    6. Nawaz, Muhammad & Enscore Jr, E Emory & Ham, Inyong, 1983. "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, Elsevier, vol. 11(1), pages 91-95.
    7. Pan, Quan-Ke & Wang, Ling, 2012. "Effective heuristics for the blocking flowshop scheduling problem with makespan minimization," Omega, Elsevier, vol. 40(2), pages 218-229, April.
    8. Refael Hassin, 1992. "Approximation Schemes for the Restricted Shortest Path Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 36-42, February.
    9. Aldowaisan, Tariq & Allahverdi, Ali, 2004. "New heuristics for m-machine no-wait flowshop to minimize total completion time," Omega, Elsevier, vol. 32(5), pages 345-352, October.
    10. Mosheiov, Gur & Oron, Daniel, 2005. "A note on flow-shop and job-shop batch scheduling with identical processing-time jobs," European Journal of Operational Research, Elsevier, vol. 161(1), pages 285-291, February.
    11. Ruiz, Rubén & Maroto, Concepciøn & Alcaraz, Javier, 2006. "Two new robust genetic algorithms for the flowshop scheduling problem," Omega, Elsevier, vol. 34(5), pages 461-476, October.
    12. Che, Ada & Chu, Chengbin & Levner, Eugene, 2003. "A polynomial algorithm for 2-degree cyclic robot scheduling," European Journal of Operational Research, Elsevier, vol. 145(1), pages 31-44, February.
    13. Levner, Eugene & Kats, Vladimir & Levit, Vadim E., 1997. "An improved algorithm for cyclic flowshop scheduling in a robotic cell," European Journal of Operational Research, Elsevier, vol. 97(3), pages 500-508, March.
    14. Mauro Dell'Amico, 1996. "Shop Problems With Two Machines and Time Lags," Operations Research, INFORMS, vol. 44(5), pages 777-787, October.
    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. Dolgui, Alexandre & Kovalev, Sergey & Pesch, Erwin, 2015. "Approximate solution of a profit maximization constrained virtual business planning problem," Omega, Elsevier, vol. 57(PB), pages 212-216.
    2. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    3. Pan, Quan-Ke & Wang, Ling & Li, Jun-Qing & Duan, Jun-Hua, 2014. "A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation," Omega, Elsevier, vol. 45(C), pages 42-56.
    4. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    5. Oron, Daniel & Shabtay, Dvir & Steiner, George, 2015. "Single machine scheduling with two competing agents and equal job processing times," European Journal of Operational Research, Elsevier, vol. 244(1), pages 86-99.
    6. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    7. 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).
    8. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.

    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. 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.
    2. Neil Geismar, H. & Dawande, Milind & Sriskandarajah, Chelliah, 2005. "Approximation algorithms for k-unit cyclic solutions in robotic cells," European Journal of Operational Research, Elsevier, vol. 162(2), pages 291-309, April.
    3. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    4. Kats, Vladimir & Levner, Eugene, 2018. "On the existence of dominating 6-cyclic schedules in four-machine robotic cells," European Journal of Operational Research, Elsevier, vol. 268(2), pages 755-759.
    5. Che, Ada & Chu, Chengbin, 2009. "Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots," European Journal of Operational Research, Elsevier, vol. 199(1), pages 77-88, November.
    6. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.
    7. Joaquín Bautista-Valhondo & Rocío Alfaro-Pozo, 2020. "Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types," 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. 28(1), pages 5-23, March.
    8. Pan, Quan-Ke & Ruiz, Rubén, 2014. "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem," Omega, Elsevier, vol. 44(C), pages 41-50.
    9. 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.
    10. 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).
    11. Bagchi, Tapan P. & Gupta, Jatinder N.D. & Sriskandarajah, Chelliah, 2006. "A review of TSP based approaches for flowshop scheduling," European Journal of Operational Research, Elsevier, vol. 169(3), pages 816-854, March.
    12. Drobouchevitch, Inna G. & Neil Geismar, H. & Sriskandarajah, Chelliah, 2010. "Throughput optimization in robotic cells with input and output machine buffers: A comparative study of two key models," European Journal of Operational Research, Elsevier, vol. 206(3), pages 623-633, November.
    13. Pan, Quan-Ke & Wang, Ling, 2012. "Effective heuristics for the blocking flowshop scheduling problem with makespan minimization," Omega, Elsevier, vol. 40(2), pages 218-229, April.
    14. Carlier, Jacques & Haouari, Mohamed & Kharbeche, Mohamed & Moukrim, Aziz, 2010. "An optimization-based heuristic for the robotic cell problem," European Journal of Operational Research, Elsevier, vol. 202(3), pages 636-645, May.
    15. Milind Dawande & Michael Pinedo & Chelliah Sriskandarajah, 2009. "Multiple Part-Type Production in Robotic Cells: Equivalence of Two Real-World Models," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 210-228, February.
    16. Xuemei Qi & Hongtao Wang & Haihong Zhu & Ji Zhang & Fulong Chen & Jie Yang, 2016. "Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4957-4972, August.
    17. Che, Ada & Chabrol, Michelle & Gourgand, Michel & Wang, Yuan, 2012. "Scheduling multiple robots in a no-wait re-entrant robotic flowshop," International Journal of Production Economics, Elsevier, vol. 135(1), pages 199-208.
    18. Marcelo Seido Nagano & Adriano Seiko Komesu & Hugo Hissashi Miyata, 2019. "An evolutionary clustering search for the total tardiness blocking flow shop problem," Journal of Intelligent Manufacturing, Springer, vol. 30(4), pages 1843-1857, April.
    19. Barry B. & Quim Castellà & Angel A. & Helena Ramalhinho Lourenco & Manuel Mateo, 2012. "ILS-ESP: An Efficient, Simple, and Parameter-Free Algorithm for Solving the Permutation Flow-Shop Problem," Working Papers 636, Barcelona School of Economics.
    20. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).

    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:jomega:v:43:y:2014:i:c:p:96-107. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.