CMU-CS-05-162
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-05-162

How the Landscape of Random Job Shop Scheduling Instances
Depends on the Ratio of Jobs to Machines

Matthew J. Streeter, Stephen F. Smith

August 2005

CMU-CS-05-162.ps
CMU-CS-05-162.pdf


Keywords: Job shop scheduling, big valley, easy-hard-easy pattern


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 approaching 0 and N/M approaching 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 gene rate 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.

34 pages


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu