A machine-order search space for job-shop scheduling problems

This paper proposes a methodology for real-time job-shop scheduling problems (JSSPs). It introduces a new classification of the scheduling methods for JSSPs with emphasis on the search methods and the significance of the search space. Subsequently, a machine-order search space is proposed as a new framework in which different single-machine scheduling algorithms and search methods can be incorporated to solve JSSPs. An optimization model relating makespan minimization and the proposed machine-order search space is also described. The proposed methodology finds an optimal solution by searching a proper machine order in the machine-order search space and scheduling the machines one by one in this order. Such an approach significantly reduces the size of the search space, and hence the computing efforts. As a result, scheduling of large JSSPs in real-time becomes practicable.