An existence theorem for packing problems with implications for the computation of optimal machine schedules

Motivated by a job-shop problem we ask on which conditions n intervals v_i: with given lengths d_i , can be arranged non-overlapping on the real axis, so that every v_i is placed in a given frame f_i s_i ].We prove a necessary and sufficient criterion analogous to the “marriage theorem” but with an additional monotony in the ages. Using this criterion we can accelerate branch and bound algorithms for job-shop scheduling by fixing partial sequences. For n = 2, the approved pair-combinatorics by Carlier and Pinson results. To show how the method works for other n. we derive the complete triple-combinatorics (n = 3: five sufficient criterions, which are necessary as a whole)