OPUS 4 Latest Documents RSS FeedLatest documents
http://opus4.kobv.de/opus4-ubbayreuth/index/index/
Mon, 04 Apr 2011 09:21:55 +0200Mon, 04 Apr 2011 09:21:55 +0200A generalized job-shop problem with more than one resource demand per task
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/661
We study a generalized job-shop problem called the Laser Sharing Problem with fixed tours (LSP-T) where the tasks may need more than one resource simultaneously. This fact will be used to model possible collisions between industrial robots. For three robots we will show that the special case where only one resource is used by more than one robot is already NP-hard. This also implies that one machine scheduling with chained min delay precedence constraints is NP-hard for at least three chains. On the positive side, we present a polynomial algorithm for the two robot case and a pseudo-polynomial algorithm together with an FPTAS for an arbitrary but constant number of robots. This gives a sharp boundary of the complexity status for a constant number of robots.Joachim Schauer; Cornelius Schwarzpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/661Mon, 04 Apr 2011 09:21:55 +0200On the benefits of using NP-hard problems in Branch & Bound
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/417
We present a Brand-and-Bound (B&B) method using combinatorial bounds for solving makespan minimization problems with sequence dependent setup costs. As an application we present a laser source sharing problem arising in car manufacturing.Jörg Rambau; Cornelius Schwarzarticlehttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/417Wed, 15 Oct 2008 08:11:51 +0200