Computer Science – Artificial Intelligence
Scientific paper
2011-09-30
Journal Of Artificial Intelligence Research, Volume 26, pages 247-287, 2006
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.2013
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.
Smith Sara F.
Streeter M. J.
No associations
LandOfFree
How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-236426