How the Landscape of Random Job Shop Scheduling Instances Depends on the
  Ratio of Jobs to Machines
  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.
