Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Domino sequencing: Scheduling with state-based sequence-dependent setup times

 
: Diessel, Erik; Ackermann, Heiner

:
Fulltext ()

Operations research letters 47 (2019), No.4, pp.274-280
ISSN: 0167-6377
English
Journal Article, Electronic Publication
Fraunhofer ITWM ()
sequence-dependent setup time; job families; Eulerian extension problem; dynamic programming; fixed-parameter tractability

Abstract
We introduce the Domino Sequencing problem, a scheduling problem with special sequence-dependent setup times. For each job there are corresponding start and end states and . When job is scheduled immediately before job , a setup time of 1 is needed if . We present polynomial-time algorithms for various versions. When jobs are partitioned into families, we show that the problem becomes -hard and present a fixed-parameter tractable algorithm.

: http://publica.fraunhofer.de/documents/N-555318.html