๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Shortest common superstrings and scheduling with coordinated starting times

โœ Scribed by Martin Middendorf

Book ID
104326345
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
639 KB
Volume
191
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

In the first part of this paper we show that the Shortest Common Superstring problem is NP-complete even if all strings are of the simple form 10plOq, p,q E N. This result closes the gap left between the polynomial cases where all strings are of the form Op104 or all strings are of the form lop1 and NP-complete cases when strings have a more complicated structure. In the second part of the paper we use the above result to investigate the complexity of 2-machine flow-shop and open-shop problems with machines that have to coordinate their starting times, i.e. when one machine starts an operation the other machine also starts an operation or has to be idle at that time.

๐Ÿ“œ SIMILAR VOLUMES

Continuous-time shortest path problems w
Continuous-time shortest path problems with stopping and starting costs
โœ A.B. Philpott; A.I. Mees ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 344 KB

We describe a general solution method for the problem of finding the shortest path between two vertices of a graph in which each edge has some transit time, costs can vary with time, and stopping and parking (with corresponding costs) are allowed at the vertices.