In the first part of this paper we show that the Shortest Common Super
string problem is NP-complete even if all strings are of the simple fo
rm 10(p)10(q), p,q is an element of N. This result closes the gap left
between the polynomial cases where all strings are of the form 0(p)10
(q) or all strings are of the form 10(p)1 and NP-complete cases when s
trings have a more complicated structure. In the second part of the pa
per we use the above result to investigate the complexity of 2-machine
flow-shop and open-shop problems with machines that have to coordinat
e 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.