  We characterize the search landscape of random instances of the job shop
scheduling problem (JSP). Specifically, we investigate how the expected values
of (1) backbone size, (2) distance between near-optimal schedules, and (3)
makespan of random schedules vary as a function of the job to machine ratio
(N/M). For the limiting cases N/M approaches 0 and N/M approaches infinity we
provide analytical results, while for intermediate values of N/M we perform
experiments. We prove that as N/M approaches 0, backbone size approaches 100%,
while as N/M approaches infinity the backbone vanishes. In the process we show
that as N/M approaches 0 (resp. N/M approaches infinity), simple priority rules
almost surely generate an optimal schedule, providing theoretical evidence of
an "easy-hard-easy" pattern of typical-case instance difficulty in job shop
scheduling. We also draw connections between our theoretical results and the
"big valley" picture of JSP landscapes.
