Lower bounds for scheduling a single robot in a job-shop environment

DC FieldValueLanguage
dc.contributor.authorBrucker, P
dc.contributor.authorKnust, S
dc.date.accessioned2021-12-23T16:04:49Z-
dc.date.available2021-12-23T16:04:49Z-
dc.date.issued2002
dc.identifier.issn02545330
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/6616-
dc.description2nd International Workshop on the Integration of AI and OR Techniques on Constant Programming for Combinatorial Optimization Problems, PADERBORA, GERMANY, MAR, 2000
dc.description.abstractWe consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized. We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.
dc.language.isoen
dc.publisherKLUWER ACADEMIC PUBL
dc.relation.ispartofANNALS OF OPERATIONS RESEARCH
dc.subjectcolumn generation
dc.subjectconstraint propagation
dc.subjectlower bounds
dc.subjectOperations Research & Management Science
dc.subjectscheduling
dc.subjecttime-lags
dc.subjectTRAVELING SALESMAN PROBLEM
dc.subjecttraveling salesman problem with time windows
dc.titleLower bounds for scheduling a single robot in a job-shop environment
dc.typeconference paper
dc.identifier.doi10.1023/A:1021149204501
dc.identifier.isiISI:000179322100008
dc.description.volume115
dc.description.issue1-4
dc.description.startpage147
dc.description.endpage172
dc.publisher.placeVAN GODEWIJCKSTRAAT 30, 3311 GZ DORDRECHT, NETHERLANDS
dcterms.isPartOf.abbreviationAnn. Oper. Res.
crisitem.author.deptFB 06 - Mathematik/Informatik-
crisitem.author.deptidfb06-
crisitem.author.parentorgUniversität Osnabrück-
crisitem.author.netidKnSi808-
Show simple item record

Page view(s)

3
Last Week
1
Last month
0
checked on Apr 22, 2024

Google ScholarTM

Check

Altmetric