Machine scheduling instance generation by reverse engineering from instance space analysis
提出一种逆向实例生成方法，利用实例空间分析生成多样、可行且真实的机器调度实例，用于评估调度算法，在单机加权延迟、作业车间和串行批调度问题上验证了有效性。
The availability of a sufficiently large number of meaningful instances for a scheduling problem is of utmost importance for the evaluation of solution methods for the problem. This study introduces a novel method for machine scheduling instance generation, termed Reverse Instance Generation (RIG), leveraging Instance Space Analysis. This method aims to create diverse, feasible, and realistic instances by reverse engineering from the instance space. Unlike existing approaches that rely on iterative search methods, RIG utilizes a constructive approach, combining dimensionality reduction techniques and controlled instance generation. The approach addresses the challenges of instance diversity and reasonableness, ensuring unbiased and reproducible outcomes. The effectiveness of RIG is demonstrated on three different machine scheduling problems: the single-machine weighted tardiness problem, the job shop scheduling problem, and a complex serial batch scheduling problem. The results highlight the method's ability to cover gaps in the instance space while maintaining practicality and efficiency, paving the way for improved benchmarking and algorithm development.