TY - JOUR

T1 - The Robot Sequencing Problem

T2 - Polynomial Algorithm and Complexity

AU - Richtee, K.

PY - 1985/1/1

Y1 - 1985/1/1

N2 - 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.

AB - 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.

KW - Complexity

KW - Directed graphs

KW - Robot sequencing problem

KW - Vertex packing problem

UR - http://www.scopus.com/inward/record.url?scp=84972957308&partnerID=8YFLogxK

U2 - 10.1080/02331938508843054

DO - 10.1080/02331938508843054

M3 - Article

AN - SCOPUS:84972957308

VL - 16

SP - 597

EP - 605

JO - Optimization

JF - Optimization

SN - 0233-1934

IS - 4

ER -