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

M. J. Streeter and S. F. Smith

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. For the limiting cases We also draw connections between our theoretical results and the big valley picture of JSP landscapes.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.