{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:24:59Z","timestamp":1759667099087},"reference-count":0,"publisher":"AI Access Foundation","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["jair"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1613\/jair.2013","type":"journal-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T10:00:59Z","timestamp":1531389659000},"page":"247-287","source":"Crossref","is-referenced-by-count":15,"title":["How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines"],"prefix":"10.1613","volume":"26","author":[{"given":"M. J.","family":"Streeter","sequence":"first","affiliation":[]},{"given":"S. F.","family":"Smith","sequence":"additional","affiliation":[]}],"member":"16860","published-online":{"date-parts":[[2006,7,26]]},"container-title":["Journal of Artificial Intelligence Research"],"original-title":[],"link":[{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10458\/25070","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10458\/25071","content-type":"application\/postscript","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10458\/25070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T18:35:38Z","timestamp":1571942138000},"score":1,"resource":{"primary":{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/view\/10458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7,26]]},"references-count":0,"URL":"https:\/\/doi.org\/10.1613\/jair.2013","relation":{},"ISSN":["1076-9757"],"issn-type":[{"value":"1076-9757","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7,26]]}}}