Domino sequencing: Scheduling with state-based sequence-dependent setup times
2019
Abstract We introduce the Domino Sequencing problem , a scheduling problem with special sequence-dependent setup times. For each job j there are corresponding start and end states a j and b j . When job j is scheduled immediately before job k , a setup time of 1 is needed if b j ≠ a k . We present polynomial-time algorithms for various versions. When jobs are partitioned into families, we show that the problem becomes NP -hard and present a fixed-parameter tractable algorithm.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
23
References
3
Citations
NaN
KQI