Advent Challenge 8: Storage Cart Transport Planning!
JavaScript (ES7), 172 bytes
Returns an array of 0-indexed time frames.
a=&gt;(g=k=&gt;a.map((a,i)=&gt;[l=a.length+1,i,a,L=L&lt;l?l:L]).sort(([a],[b])=&gt;a-b).every(([,n,b],i)=&gt;b.every((c,t)=&gt;o[t+=A[n]=k/L**i%L|0]&amp;1&lt;&lt;c?0:o[t]|=1&lt;&lt;c),o=[],A=[])?A:g(k+1))(L=0)

NB: This can only work with labels in [0-31]. This is a JS limit, not a limit of the algorithm.
Test cases


let f =

a=&gt;(g=k=&gt;a.map((a,i)=&gt;[l=a.length+1,i,a,L=L&lt;l?l:L]).sort(([a],[b])=&gt;a-b).every(([,n,b],i)=&gt;b.every((c,t)=&gt;o[t+=A[n]=k/L**i%L|0]&amp;1&lt;&lt;c?0:o[t]|=1&lt;&lt;c),o=[],A=[])?A:g(k+1))(L=0)

console.log(JSON.stringify(f([[1, 2, 3], [4, 5, 6], [7, 8, 9]])))                   // -&gt; [0, 0, 0]
console.log(JSON.stringify(f([[1, 2, 3], [1, 2, 3]])))                              // -&gt; [0, 1] or [1, 0]
console.log(JSON.stringify(f([[1, 2, 3], [3, 2, 1]])))                              // -&gt; [0, 1] or [1, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4], [4, 3, 2, 1]])))                        // -&gt; [0, 0]
console.log(JSON.stringify(f([[1, 1, 1], [1, 1, 1]])))                              // -&gt; [0, 3] or [3, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4], [2, 4, 3, 1]])))                        // -&gt; [1, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4, 5, 6, 7], [2, 3, 3, 4], [5, 4, 3]])))    // -&gt; [0, 2, 3]
console.log(JSON.stringify(f([[1, 2, 3, 4, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5]]))) // -&gt; [1, 2, 0]



Commented
a =&gt; (                         // given a = array of tracks
  g = k =&gt;                     // g = recursive function taking k = counter
    a.map((t, i) =&gt; [          // map each track t in a to a new entry made of:
      l = t.length + 1,        //   - its length + 1 (l)
      i,                       //   - its original index in the input array
      t,                       //   - the original track data
      L = L &lt; l ? l : L        //   and update the maximum track length L
    ])                         // end of map()
    .sort(([a], [b]) =&gt;        // let's sort the tracks from shortest to longest
      a - b                    // so that solutions that attempt to delay short
    )                          // tracks are tried first
    .every(([, n, b],          // for each track b with an original position n,
                      i) =&gt;    // now appearing at position i:
      b.every((c, t) =&gt;        //   for each label c at position t in b:
        o[t += A[n] =          //     add to t the time frame A[n] corresponding
          k / L**i % L | 0     //     to this position (i) and this combination (k)
        ] &amp; 1 &lt;&lt; c ?           //     if the station c is already occupied at time t:
          0                    //       make every() fail
        :                      //     else:
          o[t] |= 1 &lt;&lt; c       //       mark the station c as occupied at time t
      ),                       //   end of inner every()
      o = [],                  //   start with: o = empty array (station bitmasks)
      A = []                   //               A = empty array (time frames)
    ) ?                        // end of outer every(); if successful:
      A                        //   return A
    :                          // else:
      g(k + 1)                 //   try the next combination
)(L = 0)                       // initial call to g() + initialization of L