Skip to main content
SpringerLink
Log in

Transforming part-sequencing problems in a robotic cell into a GTSP

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

Abstract

This paper shows how to solve two-part sequencing problems in a three-machine robotic cell so as to minimize the cycle time. We start dealing with cycles whose associated part-sequencing problems do not have the structure of a travelling salesman problem (TSP). The idea behind our approach is to modify the waiting time formula and formulate the closely related modified problem as a generalized travelling salesman problem (GTSP). The other cycles to be tackled are those that have a TSP structure for their associated part-sequencing problem. The existence of common states between these cycles allows us to mix and mould all of them into a GTSP. The solution procedures, designed for both cycle classes, are merged into a single heuristic and evaluated. The computational results provided prove the efficiency of the approaches.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4

Similar content being viewed by others

References

  • Aneja YP and Kamoun H (1999). Scheduling of parts and robot activities in a two-machine robotic cell . Comput Opns Res 26: 297–312.

    Article  Google Scholar 

  • Applegate D, Bixby R, Chvatal V, and Cook W (1998). On the solution of traveling salesman problems. Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians, 645. CONCORDE TSP solver is available at www.keck.caam.rice.edu/concorde.html, accessed 1 July 2008.

  • Chen H, Chu C and Proth JM (1997). Sequencing of parts in robotic cells . Int J Flex Manuf Sys 9: 81–104.

    Article  Google Scholar 

  • Christofides N (1976). Worst-case analysis of a new heuristic for the traveling salesman problem. Management Science Research Report 388 Carnegie Mellon University, Pittsburgh.

  • Crama Y and Van de Klundert J (1997). Cyclic scheduling of identical parts in a robotic cell . Opns Res 45: 952–965.

    Article  Google Scholar 

  • Crama Y, Kats V, Van de Klundert J and Levner E (2000). Cyclic scheduling in robotic flowshops . Ann Opns Res 96: 97–124.

    Article  Google Scholar 

  • Dawande M, Geismar HN, Sethi SP and Sriskandarajah C (2005). Sequencing and scheduling in robotic cells: Recent developments . J Sched 8: 387–426.

    Article  Google Scholar 

  • Dror M and Haouari M (2000). Generalized Steiner problems and other variants . J Comb Optim 4: 415–436.

    Article  Google Scholar 

  • Dror M, Laporte G and Louveaux FV (1993). Vehicle routing with stochastic demands and restricted failures . Z Opns Res 37: 273–283.

    Google Scholar 

  • Fischetti M, Salazar JJ and Toth P (1995). The symmetric generalized traveling salesman polytope . Networks 26: 113–123.

    Article  Google Scholar 

  • Fischetti M, Salazar JJ and Toth P (1997). A branch-and-cut algorithm for the symmetric generalized traveling salesman problem . Opns Res 45: 378–394.

    Article  Google Scholar 

  • Gilmore PC and Gomory RE (1964). Sequencing a one state-variable machine: A solvable case of the traveling salesman problem . Opns Res 12: 655–679.

    Article  Google Scholar 

  • Hall NG, Kamoun H and Sriskandarajah C (1997). Scheduling in robotic cells: classification, two and three-machine cells . Opns Res 45: 421–439.

    Article  Google Scholar 

  • Hall NG, Kamoun H and Sriskandarajah C (1998). Scheduling in robotic cells: Complexity and steady state analysis . Eur J Opl Res 109: 43–65.

    Article  Google Scholar 

  • Helsgaun K (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic . Euro J Opl Res 126: 106–130.

    Article  Google Scholar 

  • Henry-Labordere AL (1969). The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem . RAIRO B2: 43–49.

    Google Scholar 

  • Kamoun H, Hall NG and Sriskandarjah C (1999). Scheduling in robotic cells: Heuristics and cell design . Opns Res 47: 821–835.

    Article  Google Scholar 

  • Laporte G (1988). Location routing problems . In: Golden BL and Assad AA (eds). Vehicle Routing: Methods and Studies. North-Holland: Amsterdam, pp. 163–197.

    Google Scholar 

  • Laporte G, Asef-Vaziri A, Sriskandarajah C (1995). Some applications of the generalized traveling salesman problem. Working paper CRT95-59, Centre de Recherche sur les Transports, Université de Montréal.

  • Laporte G, Asef-Vaziri A and Sriskandarajah C (1996). Some applications of the generalized travelling salesman problem . J Opl Res Soc 47: 1461–1467.

    Article  Google Scholar 

  • Laporte G and Nobert Y (1983). Generalized traveling salesman problem through n-sets of nodes—An integer programming approach . Inf INFOR 21(1): 61–75.

    Google Scholar 

  • Logendran R and Sriskandarajah C (1996). Sequencing of robot activities and parts in two-machine robotic cells . Int J Prod Res 34: 3447–3463.

    Article  Google Scholar 

  • Noon CE (1988). The generalized traveling salesman problem. PhD thesis, University of Michigan, USA.

  • Noon Ch and Bean JC (1991). A Lagrangian based approach for the asymmetric generalized traveling salesman problem . Opns Res 39: 623–632.

    Article  Google Scholar 

  • Saksena JP (1970). Mathematical model of scheduling clients through welfare agencies . CORS J 8: 185–200.

    Google Scholar 

  • Sethi SP, Sriskandarajah C, Sorger G and Kubiak W (1992). Sequencing of parts and robot moves in a robotic cell . Int J Flex Manuf Sys 4: 331–358.

    Article  Google Scholar 

  • Sriskandarajah C, Hall NG and Kamoun H (1998). Scheduling large robotic cells without buffers . Ann Opns Res 76: 287–321.

    Article  Google Scholar 

  • Srivastava SS, Kumar S, Garg RC and Sen P (1969). Generalized traveling salesman problem through n sets of nodes . CORS J 7: 97–101.

    Google Scholar 

Download references

Acknowledgements

We are grateful to Professor Chadlia Mohsen, for her assistance throughout the progress of this work.

Author information

Authors and Affiliations

  1. University of Sfax, Sfax, Tunisia

    W Zahrouni & H Kamoun

Authors
  1. W Zahrouni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H Kamoun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to H Kamoun.

Appendices

Appendix

The four distances, defining the GTSP and associated with the four ways to move from the common states C 1 σ(i) or C 2 σ(i) while the cell is processing the part P σ(i), to the common states C 1 σ(i+1) or C 2 σ(i+1) while the cell is processing the part P σ(i+1), are as follows: illustration

figure a

Appendix A. Moving from the common state C 1 σ(i) to the next common state C 1 σ(i+1)

The duration of the transition between the two common states when it is done through:

  • The cycle S 1:

  • The cycle S 4:

  • The cycle S 5:

Let d σ(i)σ(i+1) 1 represent the period of time needed to switch from the common state of C 1 while M 2 is processing the part P σ(i) to the following common state of C 1 while M 2 is processing the part P σ(i+1) using cycles S 1, S 4 or S 5. This period d σ(i)σ(i+1) 1 represents the distance from C 1 σ(i) to C 1 σ(i+1) in the GTSP where

Appendix B. Moving from the common state C 2 σ(i) to the next common state C 2 σ(i+1)

The duration of the transition between the two common states when it is done through:

  • The cycle S 1:

  • The cycle S 3:

  • The cycle S 4:

Let d σ(i)σ(i+1) 2 represents the period of time needed to switch from the common state of C 2 while M 3 is processing the part P σ(i) to the following common state of C 2 while M 3 is processing the part P σ(i+1) using cycles S 1, S 3 or S 4. This period d σ(i)σ(i+1) 2 represents the distance from C 2 σ(i) to C 2 σ(i+1) in the GTSP where

Appendix C. Moving from the common state C 1 σ(i) to the next common state C 2 σ(i+1)

The duration of the transition between the two common states when it is done through:

  • The cycle S 1:

  • The cycle S 4:

Let d σ(i)σ(i+1) 3 represent the period of time needed to switch from the common state of C 1 while M 2 is processing the part P σ(i) to the following common state of C 2 while M 3 is processing the part P σ(i+1) using either cycles S 1 or S 4. This period d σ(i)σ(i+1) 3 represents the distance from C 1 σ(i) to C 2 σ(i+1) in the GTSP where

Appendix D. Moving from the common state C 2 σ(i) to the next common state C 1 σ(i+1)

The duration of the transition between the two common states when it is done through:

  • The cycle S 1:

  • The cycle S 4:

Let d σ(i)σ(i+1) 4 represent the period of time needed to switch from the common state of C 2 while M 3 is processing the part P σ(i) to the following common state of C 1 while M 2 is processing the part P σ(i+1) using either cycles S 1 or S 4. This period d σ(i)σ(i+1) 4 represents the distance from C 2 σ(i) to C 1 σ(i+1) in the GTSP where

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zahrouni, W., Kamoun, H. Transforming part-sequencing problems in a robotic cell into a GTSP. J Oper Res Soc 62, 114–123 (2011). https://doi.org/10.1057/jors.2009.158

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.158

Keywords

Search

Navigation