An industrial robot is to perform n tasks, Each task will be executed by exactly one of robot's m grabs. Precedence relations are given by a finite directed acyclic graph such that some tasks can be performed only after other tasks have been completed. The problem is to find a sequence of tasks which fits the precedence relations and minimizes the number of grab's changes, The problem is shown to be NP-hard and a polynomial algorithm for a special case including the two-grab-problem is presented.

Original languageEnglish
Pages (from-to)597-605
Number of pages9
JournalOptimization
Volume16
Issue number4
DOIs
StatePublished - 1 Jan 1985

    Research areas

  • Complexity, Directed graphs, Robot sequencing problem, Vertex packing problem

    Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

ID: 54298162