Characterizing the Distribution of Low-Makespan Schedules in the Job Shop Scheduling Problem

Abstract

We characterize the search landscape of the job shop scheduling problem (JSSP), with a focus on schedules whose makespan is optimal or near-optimal. Building on previous work on the 'big valley' distribution of local optima, we use special branch and bound algorithms to examine in greater detail the extent to which JSSP search spaces conform to the intuitive picture conveyed by the words 'big valley'. We also examine how this changes as a function of the job:machine ratio. We find that for square JSSPs, low-makespan schedules are tightly clustered in a small region of the search space, and the size of this region decreases as the makespan gets closer to optimality. As the job:machine ratio increases beyond 1, however, low-makespan schedules become dispersed throughout the search space. We discuss the reasons for this and provide analytical results for two limiting cases. We close with an examination of neighborhood exactness in the JSSP, which illustrates some limitations of the big valley picture for JSSP landscapes.