Automatic Construction Method of Surrogate Evaluation Measures for Job Shop Scheduling

Job shop scheduling holds significant importance due to its relevance and impact on various industrial and manufacturing systems. Aiming at the job shop scheduling problem with random machine breakdowns, a multi-objective optimization model is established, which considers both the makespan and expected makespan delay simultaneously. Considering that the expected makespan delay cannot be calculated analytically, this paper proposes a symbolic regression-based construction method, which can automatically learn a surrogate evaluation measure. Then, a multi-objective evolutionary algorithm is proposed for solving this model, where the constructed surrogate evaluation measure is used to replace the expected makespan delay for fitness evaluation, to achieve rapid evaluation and efficient optimization. Finally, extensive simulation experiments are conducted on 40 benchmark problems of job shop scheduling, which verify the effectiveness of the proposed method and its advantages in computational efficiency.