How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines

Abstract: "We characterize the search landscape of random instances of the job shop scheduling problem (JSSP). 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 -> 0 and N/M -> [infinity] we provide analytical results, while for intermediate values of N/M we perform experiments. We prove that as N/M -> 0, backbone size approaches 100%, while as N/M -> [infinity] the backbone vanishes. In the process we show that as N/M -> 0 (resp. N/M -> [infinity]), simple priority rules almost surely generate an optimal schedule, suggesting a theoretical account of the '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 JSSP landscapes."